discrete-math

[tidal tulip]

ok i see

is j also fixed in (d) in the below pic

or is it looping

i assume this is looping

and in general how do i tell if it's fixed or looping

[pale epoch]

it has to be fixed, same as k

well, starting and end points have to be fixed

and in this case it starts at j and goes to k

[tidal tulip]

let's say j=2, k=10, then what tells you about this set up it loops through B1,B2,..B10, as opposed to be fixed like the initial problem (c) i asked about of j=9, B9 ∩ B10

[pale epoch]

a, b and c are just special cases of d

if j=2 and k=10 it loops through B_2, B_3, ..., B_10

no B_1

[tidal tulip]

ok i think i see why (c) in example 1.17 doesn't loop, it's because the index starts at j and ends at j+1

whereas 1.16 says start at j and end at k

where k>=j

[pale epoch]

k could be j+1, then its similar to the other one

[tidal tulip]

ok i see

(d) in 1.16 where j=8, k=10 would be: B8 ∪ B9 ∪ B10 = {8,9} ∪ {9,10} ∪ {10,11} = {8,9,10,11}

so have to pay attention to start/end indices

that helps me clear it up much more now

ty

i seen online someone comment in a math thread, "that isn't a proof by contradiction but a proof by negation" -- what then is the difference between a proof by negation and a proof by contradiction?

[pale epoch]

if you have double negation elimination, there is no difference

[tidal tulip]

ok

[pale epoch]

someone doing constructive mathematics might differentiate

[tidal tulip]

like if you want to prove P->Q, then you assume P and ~Q and show you get Q ? is this how contradiction works

[pale epoch]

this is contradiction, yes

but to prove $\neg P$ you can assume $P$ and show that it leads to absurdity (i am trying to avoid the word contradiction), then someone might want to call this "proof by negation"

[vital dew]

Lochverstärker

[pale epoch]

this is just how you prove the negation of a statement

[tidal tulip]

ok i see

[pale epoch]

contradiction on the other hand is when you want to prove $P$, assume $\neg P$ and show it leads to absurdity

[vital dew]

Lochverstärker

[pale epoch]

technically it leads to $\neg (\neg P)$ only

[vital dew]

Lochverstärker

[pale epoch]

so you need LEM or at least double negation eliminiation, to actually derive P

[tidal tulip]

LEM?

oh

least double negation

(i dont know what that is unless its a reference to ~~P = P)

[pale epoch]

law of excluded middle

[tidal tulip]

oh. P or Q

[pale epoch]

not P or P

this proves not not P = P

but it's a bit stronger in general i think

[tidal tulip]

ok i see

[hushed iron]

For this question i found out that n >= 4 for this inequality to be true but im confused on how i would prove my claim with mathematical induction.

i can share what i did so far if that helps

[quaint star]

Suppose it is true for n, i.e. 3n^2 + 2 <= n^4. Then we want to prove that 3(n+1)^2 + 2 <= (n+1)^4

[hushed iron]

yah i did that

[quaint star]

Okay

Expand the LHS and apply the inequality you assumed

[hushed iron]

wait why ^2

you mean ^3

[quaint star]

I did

My bad

[hushed iron]

3x^3+9x^2+9x+5

this is what i get when i expan left side

[quaint star]

Now expand the RHS too so you have an idea of what you have to compare it to

[hushed iron]

i did this

i get confused when i need to use my inductive hypothesis

[quaint star]

Yes, now 4k^3 + 2 <= k^4. So then you need to show that 9k^2 + 9k + 3 <= 4k^3 + 6k^2 + 4k + 1.

Because then adding the two inequalities gives you what you want

To prove that inequality, you just have to use that k >= 4

[hushed iron]

do i get rid of k^4?

on right side

[quaint star]

We don't get rid of it. It's just that we already have that 3k^3 + 2 <= k^4. So we only need to show that the rest of the LHS <= the rest of the RHS

[hushed iron]

where did we get 4k^3?

[quaint star]

I meant 3

So like 3k^3 + 9k^2 + 9k + 5 = (3k^3 + 2) + 9k^2 + 9k + 3 <= k^4 + 9k^2 + 9k + 3, and now we need to show this is <= k^4 + 4k^3 + 6k^2 + 4k + 1

[hushed iron]

(3k^2 + 2) + 9k^2 + 9k + 3 <= k^4 + 9k^2 + 9k + 3 how did we get this?

[quaint star]

Applying the induction hypothesis

[hushed iron]

3k^3 + 9k^2 + 9k + 5 = (3k^2 + 2) + 9k^2 + 9k + 3 is this were u use I.H

[quaint star]

No

I just rewrote it

To isolate 3k^2 + 2

And then I apply IH

I split 5 up as 2 + 3, and then grouped 3k^2 and 2

[hushed iron]

3k^3 into this (3k^2 + 2) im sorta confused on how u did this

sorry for taking up ur time

[quaint star]

See how I had + 5 at the end originally

Then I had + 3 at the end

That's because of the 2

Oh

I typod the k^3 again

It should have been 3k^3 + 2

[hushed iron]

ok so its (3k^3+2) + 9k^2+9k+3 <= k^4 + 9k^2 + 9k + 3

and this is by I.H

[quaint star]

Yes

[hushed iron]

u basically plugged k^4 where (3k^3+2) was

[quaint star]

Yes

[hushed iron]

(3k^3+2) + 9k^2+9k+3 <= k^4 + 9k^2 + 9k + 3 what is the next step from here?

do i plug in some k value > 4 or do i need to find that k must be >= 4 from the inequality we just formed

[quaint star]

Just use that k >= 4

By plugging it into the RHS

[hushed iron]

so like plug in 4 into right side

[quaint star]

Yes

[hushed iron]

i get 439

[quaint star]

Not quite

Kind of just apply it "once" to each term

So k^3 >= 4k^2

Like that

[hushed iron]

so you mean like (3(4)^3+2) <= (4)^4

[quaint star]

No

LHS <= k^4 + 9k^2 + 9k + 3
RHS = k^4 + 4k^3 + 6k^2 + 4k+ 1
If we compare

Now if we compare, we see that the RHS has an extra k in each term

So we can use k >= 4

For example, 4k^3 >= 16k^2 >= 9k^2

And do the same for the other terms

[hushed iron]

ik we got 4k^3 from rhs eqn and 9k^2 from the eqn above but where did we get 16k^2

[quaint star]

I said 4k^3 >= 16k^2 since k >= 4

Then 16k^2 >= 9k^2 , so we get that 4k^3 >= 9k^2

[hushed iron]

how did we get 16K^2

[quaint star]

4k^3 = 4k^2(k) >= 4k^2(4) = 16k^2

I am applying k >= 4 to one of the ks

[hushed iron]

6k^2 >= 24k>= 9k is this it for the other terms?

[quaint star]

@hushed iron yeah

And also 4k + 1 >= 3

[hushed iron]

you mean 6k?

[hushed iron]

also what do you mean that there is an extra k in each term?

[quaint star]

I meant that we have k^3 vs k^2, k^2 vs k, so there is an extra factor of k

[hushed iron]

so we are multiplying it by 4 to have the same k exponent

like 9k^2 <= 16k^2

[quaint star]

Yeah

[hushed iron]

but why do we do that?

is it to just confrim the each term on the right is bigger than or eqaul to the term on the left?

[quaint star]

We need a way to compare the two expressions

And this happens to work out nicely

Because all the corresponding terms will have a larger coefficient if we do it this way

[hushed iron]

so we are allowed to plug in 4 for one of the k

so you have
k^4 <= k^4
9k^2<= 16k^2 = 4k^3
9k <= 24k = 6k^2
3 <= 6k+1

instead of making them same exponent couldnt we just say 9k^2 <= 4k^3

and 9k <= 6k^2

when k>=4

[quaint star]

Not =

16k^2 <= 4k^3

Since 4 <= k

[hushed iron]

ok so i cant just say 9k^2 <= 4k^3

[quaint star]

That's false

Ah

Well, we are saying that, but you have to explain why it's true

[hushed iron]

couldnt u explain it by plugging in a k value >= 4

for each term comparison

[quaint star]

You want to show it's true for an arbitrary value of k

Not a specific one

Plugging in k = 6 and showing its true, doesn't mean that it will be true for k = 11 or k = 15 or whatever

[hushed iron]

in this step u are multiplying it by 4

[quaint star]

Yes

[hushed iron]

why are we allowed to do that

[quaint star]

But I am not saying k = 4

We are trying to show it is true for k >= 4

So we are just using the fact that k >= 4

I am not choosing a specific value of k

[hushed iron]

im sorry im a little confused

[quaint star]

I can tell, but I'm not really sure how to explain it

If I want to show something is true for all n >= 5

Let's say

n^2 - 4 >= 0 for n >= 5

I can't just plug in n = 8

And say that because it's true for n = 8, then it's true for n >= 5

But I can use the fact that n >= 5 is true

And say that n^2 - 4 >= 25 - 4 = 21 >= 0 for all n >= 5

So I don't choose a specific value of n

I am just using the property that all the n values we are considering have, i.e. n >= 5

[hushed iron]

in this case because you know that n<-5 is true we can put in 5 for n

but didnt u just show that it work for n=5

[quaint star]

No

I didn't put in n = 5

I used that n >= 5

If n >= 5 then n^2 >= 25

[hushed iron]

oh ic

[quaint star]

That's what I was doing in the proof too

I didn't put in k = 4

I used that k >= 4

[hushed iron]

after comparing the term with the assumption that k>=4 is true then the proof is done?

and we confirmed that k>=4 is true

[weary tiger]

anyone know the answer

<@&286206848099549185>

[shadow grove]

How do I calculate the number of ways to get a number by addition with a given set of numbers?

E.g

I want to calculate all the ways to achieve 5, with the numbers {1,2,3}

One way I have thought of is to calculate the number of ways to get the numbers before 5.

So f.eks 3 = {1,2}

{3,2}=5 -> {{1,2},2} =5?

• also, is there an object like a list, that cares about the amount of times an element in it appears, but not the order?

Because, the problem with using lists for this is that {1,1,2,1} = {1,2}

And with tuples

(1,1,2,1) \neq (1,2,1,1)

[pearl fern]

A multiset is such an object, but it doesn’t behave as seamlessly as sets and tuples

[plain ridge]

The number of integers from 1000 to 9000 inclusive. How many are divisible by 7? I did 9000/7 aprox= 1285.71

I rounded down, but the solution is to round up. Is there a reason for this?

But in this case: from 1 to 10 inclusive divisible by 7. 9/7 aprox= 1.28.

I would round down because i know that only 7 works for that situation

[ornate cliff]

Is this a simple graph? I don’t think it is because it contains a cycle from path 3, 4, 5, 3. Unless I’m misunderstanding the word cycle?

Oh wait nvm. I was confusing the term loop and cycle. It is a simple graph.

[stray reef]

a graph that contains no cycles is called acyclic

just for future reference

@ornate cliff

[ornate cliff]

Thank you!

[icy gyro]

Let A be the set of all non-empty subsets of {1,2,…,10} and let g be the following function. g:A→A defined by g(X)=X∪{1,2}

would g be defined as a surjective function(onto)?

[stray reef]

what do you mean by 'defined as' a surjective function?

did you mean to ask "would g be a surjective function"?

[icy gyro]

yes

[stray reef]

ok, and do you think g is surjective or not surjective?

[icy gyro]

surjective is what i think

[stray reef]

you would be wrong

there is no set X such that g(X) = {3} for example

[icy gyro]

ohh I completely overlooked that

thanks

[mystic elbow]

Hi

Can anyone please check the answers

Q3 and q4

Ping me too

<@&286206848099549185>

[storm drum]

I need either to prove it or disprove it.
“For every sets of A,B this equation is true.”

do i need to prove it or to disprove it?
And how?

[stray reef]

what's that slash?

[storm drum]

Difference

[stray reef]

so it's a backslash going the wrong way, ok

[ornate cliff]

Does question 6C only want me to calculate Warshall’s Algorithm from 0W to 1W or from 0W to 5W?

I wasn’t sure if I should only compute to round 1 or all the way to round 5 of matrices (as shown in the example below).

[mystic elbow]

Anyone?

[cerulean wind]

try some examples with some small sets

[haughty garden]

3.1, 3.2 and 3.4 are correct. 3.3 should be surjective but not injective. Every element in the codomain is mapped by at least one element.

For q4, suppose you have n men and n women and you are tasked to fill up a committee of n people. On the one hand, you can do this in C(2n, n) ways. On the other hand, you can do this by first finding the number of ways to choose i men and then choose the remaining n - i women. To capture all possible combinations, you take the sum of C(n, i) * C(n, n - i)

[cerulean wind]

alternatively, we have that
$$F:\bigsqcup_{i=0}^n\big(\mathcal{P}(\mathbb{N}n,i)\times\mathcal{P}(\mathbb{N}{2n}\setminus\mathbb{N}n, n-i)\big)\to \mathcal{P}(\mathbb{N}{2n},n)$$
given by $F(A,B) =A\sqcup B$ is a bijection, where $\mathcal{P}(S,k)$ is the set of $k$ element subsets of a finite set $S$ and $\mathbb{N}_m={1,…,m}$ for any natural number $m$.

[haughty garden]

Hmmm I’m not sure whether that’s a combinatorial proof

[vital dew]

c squared

[haughty garden]

At least I haven’t seen such an argument like that from a combinatorial class :0

[cerulean wind]

just using a bijection?

i’ll admit this is overly complicated, but still a proof

[haughty garden]

I’ve seen bijective arguments in real analysis but not combinatorics, but a proof is a proof so allgs haha

[cerulean wind]

combinatorial proofs, at least the way i’ve seen them, are either like the one u presented or bijective proofs

[haughty garden]

Ahh okay, fair enough

[cerulean wind]

i should start at 0, not 1

[plain sky]

How many distinct symbols are needed in base twelve?

<@&286206848099549185>

[coarse cave]

anyone know the specifics of tail recursion?

[flint lintel]

should i take linear algebra before discrete math?

[mystic elbow]

How to find a number of ways to chose i men and remaining women?

@haughty garden also the calculations i did is wrong?

[haughty garden]

It's not a combinatorial proof

You arbitrarily choose the number of men -- there are $n$ men and you choose $i$ of them which gives you $C(n, i)$. The remaining $n - i$ places are filled up by women which gives you $C(n, n - i)$. So to fill up a committee of $n$ people with $i$ men and $n - i$ women, you have $C(n, i) \cdot C(n, n - i)$ different ways. Then vary $i$ from 0 to $n$ to get the desired result [ \sum_{i = 0}^n \binom{n}{i} \binom{n}{n - i} = \binom{2n}{n}.]

[vital dew]

opengangs

[mystic elbow]

This is the final answer u say?

[coarse cave]

could anyone solve this proof please?

[mystic elbow]

@haughty garden

[mystic elbow]

Got it now thank u so much

[hoary cloak]

so im trying to prove a theorem on graphs: which is that we can find a basis for a graph G's cut space using bonds E(v) such that v is in the spanning tree of G

idk if this is true, i just need to find a basis for the cut space using the bonds

that's the answer i got to

oh yea i made a mistake

i assumed that E(v_i) which are part of the basis couldn't be represented as a combination of the others

nvm then, i'll just leave this here 😅

[storm pond]

Why the relation R = { (a,a),(b,c),(c,d),(d,d)} on X ={a,b,c,d} is not transitive?
Ans: (b,c) and (c,b) ∈ R, (b,b)∉ R

May I know that am I correct?

[stray reef]

(c,b) is not in R, so no you aren't correct

you can say that (b,c) and (c,d) are in R, and (b,d) isn't

[storm pond]

i got what u meant, actually there was a typo in relation R but suppose to be (c,b) not (c,d) sorry for that mistake. Thank you for your reply anyway.

How about this question given R = {(1,2),(2,3),(1,3)} is this a transitive ?
Ans from me: Transitive, (1,2) and (2,3) ∈ R, (1,3)∈R

May I know that am I correct?

[grave totem]

it is correct

[storm pond]

hello ryzaki, do you mind that i pm u please?

My lecturer taught me using an alternative way to find transitive relation

But if i used this method to solve the question R={(1,2),(2,3),(1,3)} , the answer will be not transitive

[grave totem]

it's Ryuzaki

also what's$\otimes$?

[vital dew]

Ryuzaki

[storm pond]

let me show u an example

may i know which is correct ?

I am sorry to bother you and tagging u.

[grave totem]

show me the workout for this

[storm pond]

ok wait a min

btw it is a boolean product

[grave totem]

and what did your teacher say? pretty sure = is not a criteria for transitivity

= holds if it's a equivalence relation

https://math.stackexchange.com/questions/228898/how-to-check-whether-a-relation-is-transitive-from-the-matrix-representation

last paragraph

[storm pond]

Ok thank you very much. I will try to understand it.

[slow jewel]

aNY IDEAS

[weary solstice]

@slow jewel if they just want you to construct a graph, right away you know it will need to have all vertices even degree because it's Eulerian. So as far as I can tell, you just want to play around with graphs with all vertices even degree until you find one that's not Hamiltonian or semi-Hamiltonian. As a hint, there's a way you can stitch together two 4-cycles to make a graph with your required properties.

[slow jewel]

hmmmmm

ill come back to it

thanks for the hint

[tulip stirrup]

Could anyone explain help explain this?

[stray reef]

call the adjacency matrix of your graph A. do you know what the entries of A^2, A^3, etc. represent?

[tulip stirrup]

I believe so, it's a grid representation of a graph?

[stray reef]

no, that doesn't answer my question.

let me be more concrete.

say we have a graph whose adjacency matrix is $A$. the $(2,4)$ entry of $A^3$ represents something concrete about the graph. what does it represent?

[vital dew]

Ann

[tulip stirrup]

It represents the vertex which two lines meet I believe

[stray reef]

no

not even close

[tulip stirrup]

Ok, sorry for wasting your time. I think I'll go watch some more videos. Thanks anyways.

[stray reef]

...i was not done but ok

[tulip stirrup]

It's alright. I think I need to build a better understanding on my own time to get proper help.

[next sail]

Anyone here know about euler cycles?

👀

[small kayak]

I have done the proof for the closed formula for the fibonacci numbers; however, the final result is not correct. Can somebody please point out what are the mistakes that i have in my proof ? Thanks

[keen python]

Basically all sequences in analysis are infinite 👀

No

It's just to say n -> infinity is fine

There, no

n is never "equal" to infinity

But sequences can be infinitely long, so n can tend to it

[weary tiger]

Jeello

PLEASE y'alllll

Help your guy Ronald with a congruences riddle that's keeping him awake

Z is a group made up of 213 peeps with A, B and C belonging to Z. 48 belong to A, 71 belong to B and 94 belong to C.
If two people from the same group meet, nothing will change.
If two people from two different groups meet, they will convince each other that they have made the wrong choice and join the third group.

How can I show that group Z will never unite using the congruence of relation modulo n?

I've found that it's modulo 3 already, BUT HOW CAN I MODEL THIS SITUATION MATHEMATICALLy?

Notably, how CAN WE STUDY THE EVOLUTION OF THE GROUP MATHEMATICALLY?

[stray reef]

is it REALLY NECESSARY TO SHOUT LIKE THAT? @weary tiger

[haughty thicket]

WHATS 1+1

WHATS 1+1

5??

[hazy pine]

@haughty thicket do not troll topic channels.

[limber lava]

Hey guys, I am having trouble with this problem:

What are the odds of at least b occurrences of m consecutive heads in n coin flips? The occurrences cannot overlap.

[limber lava]

Example: What are the odds of at least 1 occurrence of 2 consecutive heads in 3 coin flips?
Solution would be 0,375 because 3 of 8 permutations fit: HHH, THH, HHT
If we asked for 2 occurrences instead of 1, the answer would be 0, because HHH does not count as "2 separate occurrences of 2 consecutive heads"

[weary tiger]

Oh boy here we go with induction: $5^n + 9 < 6^n, n \geq 2$. I've proved a base case (n = 2), but having difficulty finishing the inductive step. So far I have $5^{n + 1} + 9 < 6^{n + 1} = 5^n \cdot 5 + 9 < 6 \cdot 6^n$

[vital dew]

8106

[weary tiger]

I thought maybe rewriting the inequality as $5^n < 6^n - 9$, then during the inductive step, doing $5^{n + 1} < ... = 5 \cdot 5^n < 5 \cdot (6^n - 9)$, but don't think that's valid.

[vital dew]

8106

[weary tiger]

Then if you just divide by 5, you get the original inequality which as assumed to be true: $\frac{5 \cdot 5^n}{5} < \frac{5 \cdot (6^n - 9)}{5} = 5^n < 6^n - 9$

[vital dew]

8106

[tidal tulip]

is (b) written out like this: (A1 ∩ A2) ∪ (A2 ∩ A3) ∪ (A3 ∩ A4) ∪ (A4 ∩ A5) ∪ (A5 ∩ A6)

where you do the inner then the outer for the union/intersection evaluations

[weary tiger]

yes

[tidal tulip]

thanks!

[knotty cypress]

can someone explain this to me please

[weary tiger]

When is implication false?

if you have, lets say a -> b

when is it false?

[knotty cypress]

when a is true & b is false

[weary tiger]

yes

so in this case you know that RvS is false and ((P andQ)vR) is true

when is RvS false?

[knotty cypress]

ooh i understand now, so P & q are true, R&s is false?

[weary tiger]

yep

[knotty cypress]

ok thanks!

[limber lava]

I posted my question here now: https://math.stackexchange.com/questions/4309047/expected-value-for-non-overlapping-consecutive-heads-in-biased-coin-flips

[weary tiger]

anyone?

[gritty pumice]

since 5 < 6

LHS * 5 < RHS * 6

so we know $5^{n-1} + 9 < 6^{n-1}$

[vital dew]

Lsfhv

[gritty pumice]

$\Rightarrow 5^n + 9<5^n + 45 < 6^n$

[vital dew]

Lsfhv

[weary tiger]

Hmm I sort of follow

Yeah it makes sense

[gritty pumice]

awesome

[weary tiger]

That's much simpler than mine haha

Thanks for the help 🙂

[gritty pumice]

yw : )

[scenic pecan]

Can someone explain how to get 3 spanning trees? I only managed to get 1

this is the spanning tree i came up with

[weary solstice]

@scenic pecan The one you came up with is using RS, so make sure the spanning tree you create excludes both RS and UT. The left side of your graph is good, but drop edge RS and play around with the other edges between P, Q, R, S and you'll get 3 spanning trees.

[scarlet zephyr]

Hey guys! I have a bit of a conundrum. So given $O$ as being the asymptotic upper bound for a given function $g(n)$, and $O(g(n))$ being defined as:$\newline$

$O(g(n)) = { f(n):$ there exist positive constants $c$ and $n_{0}$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_{0} }\newline$

And $Ω$ being the asymptotic lower bound for a given function $g(n)$ and $Ω(g(n))$ being defined as:$\newline$

$Ω(g(n)) = { f(n):$ there exist positive constants $c$ and $n_{0}$ such that $0 \leq cg(n) \leq f(n)$ for all $n \geq n_{0} }\newline$

And the questions specifically are:$\newline$
1) $f(n) = O(g(n))$ implies $2^{f(n)} = O(2^{g(n)})\newline$
2) $f(n) = O(g(n))$ implies $g(n) = Ω(f(n))$ (this is transpose symmetry, but I'm not exactly sure how to prove it outside of the below assumptions)$\newline$

For the first, I reckon I can use induction to prove that. Is there any way to simplify $2^{f(n)} = O(2^{g(n)})$ further? I haven't done anything with powers and logarithms since high school.$\newline$

For the second, I'm having some difficulty with it. Is there anything simply stopping me from using induction and simplifying to $O(g(n)) = Ω(f(n))$? I don't quite fully grasp the concept of asymptotic bounds yet. Are there any special properties or mathematical laws that stop me from doing so?$\newline$

For both, is there anything simply stopping me from defining my base case as $f(n) = 1$ and $cg(n) = 1$ (with $c = 1$) for solving with induction?

[vital dew]

Foxify

[weary tiger]

i smell british, using those commas instead of decimals

[tawny trout]

hi, is there a sum-of-products expansion for when "F(x,y) = 1"

[stray reef]

...you can write $$\forall x [x \in L \to (...) \land x \notin L \to (...)]$$ i guess

[vital dew]

Ann

[stray reef]

sure

[limber lava]

German

[stray reef]

(p&q) v (!p&q) simplifies to just q

[slate burrow]

and do i use that to decide if p -> q is true?

[stray reef]

yes

[slate burrow]

so then basically i just compare q to
F T
T T in out original statement and decide from there

[haughty garden]

(A -> B) -> B being true does not necessarily imply that A -> B is true, you can certainly have (A -> B) being false and the implication is still true

[slate burrow]

I understand that but how can I prove that using a truth table?

[weary tiger]

do a table for (A->B)->B and for A->B

if there's a entry where the first one is true but the second isn't

then truth of the former doesn't imply the latter...

assuming it's true means consider only the lines where (A->B)->B is true

[slate burrow]

And according to this truth table we can not conclude that A->B is true

[weary tiger]

just fucking say what you need help with

dont ask to ask

just ask

oh

its alright

so what you need help with?

um also 12 year old is not allowed in discord

i dont know

and i dont care honestly

just ask your question

what about that

7h³+3h+2h³ is a polynomial

theres no answer to it

so the question is to simplify it

do you know the distributive property?

do you see how to use it there?

then use it

youre welcome, also #prealg-and-algebra might be better channel for you

[vast cradle]

can someone explain what steps are taken with distributive property

oh i get it nvm

[weary tiger]

how do I solve the recurrence relation $T(n)=[ \begin{cases}
1 & n = 0 \
2 & n = 1 \
T(n-1)+T(n-2) & n > 1
\end{cases}
]$ using a characteristic polynomial?

[vital dew]

jswatj
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[weary tiger]

I found the roots

to be

$x = \frac{1\pm \sqrt{5}}{2}$

[vital dew]

jswatj

[obtuse lance]

once you have the roots, call them a and b, then the final solution is $$T(n)=Aa^n+Bb^n$$ then use your conditions at n=0 and n=1 to solve for A and B

[vital dew]

Merosity

[weary tiger]

Yeah

it was unsolvable

[obtuse lance]

it's solvable

[weary tiger]

I got $1=a+b$ and $2=a\left(\frac{1+ \sqrt{5}}{2}\right) + b\left(\frac{1- \sqrt{5}}{2}\right)$

[vital dew]

jswatj

[obtuse lance]

good, one way is to solve for a in the first equation and plug it into the second then solve for b

once you have b, then you know a=1-b so you're done

[weary tiger]

Ohhh

i got it

wow its really messy

[obtuse lance]

yeah, I would rather leave them with symbols and not plug in personally lol

or only plug in at the very end

[pine iris]

So I have 7 distinct colours to form 3 bracelets

I have {7 3}*3! different ways to make the 3 bracelets

where {7 3} are the stirling numbers of second specie

But I wonder if I could repeat the colours in the bracelets what would change

[weary tiger]

I need help with these, I suck at counting proofs and need help on how to approach them

my thinking for (a) is that theres {1}, {1, 2} etc. which all contain 1 but that as far as i am on that

[tidal tulip]

can a collection of subsets of A be pairwise disjoint if this collection is just the empty set, since the empty set would be a subset of A and its vacuously true that any two subsets of this collection is the empty set?

[weary tiger]

i have no clue

[stray reef]

yes, a collection of no sets at all would be pairwise disjoint. this is a vacuous truth.

[tidal tulip]

@stray reef ok ty

[signal shard]

Well, how many subsets of A are there in general? (And having figured that out, can you modify the argument?)

[weary tiger]

@signal shard I found out it was $2^{n-1}$ subsets but now my problem is how do I write that out in a proof/solution?

[vital dew]

Keanan

[haughty garden]

imagine fixing the element 1 into your set, the other elements can be chosen to either be in the set or out of the set

[weary tiger]

What do you mean?

[haughty garden]

The standard proof (omitting the fact that 1 has to be in your set) is as follows: For each element, either the element is in your subset or it is not. Each of these is independently chosen. Thus you have 2^n number of subsets for a set of n elements. You can modify this by assuming that each of the subsets contain the element 1; however, this just amounts to finding the number of subsets of {2, 3, ..., n}

Another way to put it: you restrict the choice of element 1 to always be an element in your subsets

[weary tiger]

Oh okay I think I get it

I was a bit confused when you said "either the element is in or not"

[haughty garden]

Ah, hopefully I clarified it

[weary tiger]

Ah shit sorry I'm afraid I still don't quite understand, what I get is if you fix 1 that you can make subsets of your choosing which must contain 1. Because of this we now have 2^(n-1) subsets of a set with n-1 elements

[haughty garden]

yep

you've basically translated the problem from number of subsets from {1, 2, ..., n} to number of subsets from {2, 3, ..., n}

[weary tiger]

Okay

Thanks for your help I appreciate it @haughty garden

[alpine agate]

Hi I have a question involving counting and graph theory. I'm working with a complete graph K_16, and am trying to figure out how many subgraphs of things we can have. If anyone wants to try them with me let me know! First question asks "How many subgraphs of K_10 can be found in K_16"

[stray reef]

you mean how many subgraphs iso to K_10 can be found in K_16?

[alpine agate]

It didn't really reference isomorphism but I would imagine

[stray reef]

then is this not just 16C10 lol

[alpine agate]

for this one thats what i was thinking

My next question would be for paths of length 10 (P_10)

I was thinking 16P10 because you're basically choosing one less everytime

And paths can't really end where they start

[stray reef]

yes

[alpine agate]

And what about cycles (C_12), would that also be 16C12?

I can only think you just choose 12 vertices and then you connect them cyclically and call it a day

Would that be accurate or am I forgetting something

[stray reef]

cycles... no

that'd be 16P12/12 i think

[alpine agate]

Would that be because the vertices are indistinguishable?

i'm not sure if i follow entirely why that is

[stray reef]

it's because cycles don't have start or end points

so for a cycle that goes through the vertices 1-10 in order you could instead start at 7 to get 7-8-9-10-1-2-3-4-5-6-7

and it'd be the same cycle

[alpine agate]

So the 16P12 is for selecting the paths, however we can also consider it a cycle as long as we get rid of the overcount

I dont think i worded it right but i think I gotcha

My final one is the bipartite graph K_6,8
not at all sure how to think about this one

[stray reef]

what are you looking for in that

[alpine agate]

whatda mean

[stray reef]

what do you want to count

[alpine agate]

Oh, the amount of possible subgraphs K_6,8 in K_16

[stray reef]

ah.

[alpine agate]

I was thinking if you choose say 6 of the 16 vertices and another 8 vertices you put them opposite each other, and you have a bipartite lookalike graph

[stray reef]

wouldn't you just need to pick 6 vertices for one part and 8 for the other

and just only take the edges you need

so that

[alpine agate]

I wasn't too sure about the count

[stray reef]

so that's 16!/(6! 8! 2!)

[alpine agate]

Oh I see, I was thinking you choose the possible edges so I had like 48C8*40C6

but i guess you dont even need to think about the edges, the vertices work too?

[weary tiger]

Okay so for (a) I showed that f is injective given $a\neq 0$ and (d) I showed that f is surjective using each case for a. I'm stuck on (b) and (c). For (b) I could use the fact that f is injective but i don't know how to show $a\neq 0$ directly anyway.

[vital dew]

Keanan

[haughty garden]

It might be easier to look at the contrapositive

If a = 0, then f is not one to one

[weary tiger]

would I do the same for (c) do you think?

[haughty garden]

Yeah I don’t see why not

[weary tiger]

(b) seemed straightforward to prove but I'm stuck on (c)

I split it up into 2 cases but I don't know what to do with the fact that a=/1 shows that f(x) = y and likewise for a=/-1

[tall oxide]

what does modulo means in sets? for ex. (Set A)/(a R b)

[stray reef]

can you show the whole question/problem/whatever

as-is it's not clear

[tall oxide]

A modulo R: A/R { [a] | a ∈ A }

[stray reef]

...i said show the whole thing not type it out poorly

but it seems like you've just written out the definition of A/R

as the set of all equivalence classes of A under R, where R is an equivalence relation

[stray reef]

yeah so why didn't you write out the :=

[tall oxide]

I still don't get it let's say we have (a,b) ∈ R = { (1,2), (2,1) (1,1) }

if [1] = {2,1} then what's A/R ?

Im sorry Im not fond of definitions. I digest infos thru examples.

[stray reef]

R = { (1,2), (2,1) (1,1) }
this is not an equivalence relation

and you didn't say what A is either

if you want examples:
let A be a deck of cards and let R be the relation defined as 'x R y iff x and y are the same suit', then A/R will be {hearts, spades, diamonds, clubs}

[mystic elbow]

Hi

Is this correct answer? Ping me too

[reef tapir]

Can I have some help

[weary solstice]

One way is to use Kruskal's algorithm to find the minimum spanning tree. You pick the edge of least weight, and then you continue to choose edges in the graph of the least weight at each step as long as they don't create a cycle, until you have a spanning tree. The spanning tree you get is the minimum spanning tree.

Then just add up the edge weights and you have the answer

[mystic elbow]

Anyone?

Ping me too

[stray reef]

do you still need help with this

[tidal mica]

Does anyone have any idea about this?

I can't really find a pattern ;-;

[plain ridge]

I got 2(n!)^2

[obtuse lance]

yeah that's correct @plain ridge

[plain ridge]

I first did P(n,n) where n = n men and r = n women. multiplied that by P(n,n), where n = n women and r = n men. Doesn't the two permutations already account for the two ways to arrange men and women alternatively?

[obtuse lance]

no, cause you could start with a man or a woman when you line them up

so that's what's doubling them up

for instance, there are 2!^2 ways to do BGBG and 2!^2 ways to do GBGB, so there are 2*(2!)^2 ways in all to arrange them

[plain ridge]

hm its a little fuzzy still, i'll reread the text

[obtuse lance]

I think of it in layers, there are two ways to arrange men and women alternating depending on whether you start with a man or a woman

the second layer is within the group of men alone there are n! ways to arrange them, similarly for the women

[plain ridge]

oh i see you can arrange the men in n! ways in WM

and vice versa

[plain ridge]

Is there a way to do a with permutations and combinations? I know there is a way with counting.

I tried doing C(26,6) * P(6,1)

[fierce osprey]

this basically asks- given the universe omega, what is the cardinality of the set on the bottom

can anyone tell me if I'm right in thinking that it's 3 because that's the number of possible subsets of {a, b}?

I'm thinking that the symmetric difference of Z and another set being equal to Z must mean that Z is a subset of the other one, and thus a subset {a, b}

[weary tiger]

Assume Z△{a,b}=Z.
If a∈Z then a∈Z∩{a,b} => a∉Z△{a,b}=Z, contradiction.
So a∉Z, same logic works for b∉Z.
Therefore Z⊆{c,d}.
{c}△{a,b} = {a,b,c} which is not equal to {c}.
Same logic for {d}.
{c,d}△{a,b}=Omega which is not equal to {c,d}.
So if Z exists, it has to be the empty set.
Ø△{a,b}={a,b} which doesn't equal Ø.
So there is no such Z.
=> The cardinality is 0.
Q.E.D.

I feel like I have a mistake somewhere, so please check me.

[marble pivot]

not sure if this is the right place but my textbook says this

If P(A|B) = P(A), then we can say events A and B are independent.

but they gave this formula

[vital dew]

abs_0

[marble pivot]

?

[haughty garden]

You’re thinking of mutually exclusive, not independence

[marble pivot]

oh

so far I've been thinking of the "event space" and all that as a Venn Diagram

Can you do that with independent events?

Cause like, the only way for P(A | B) = P(A) is if P(A cap B) = P(A) * P(B)

[haughty garden]

Precisely

[marble pivot]

oh oh oh

that makes sense

but is there some analogous concept for multiplicaiton in Venn Diagrams

cause the formula P(A or B) = P(A) + P(B) - P(A cap B) makes sense if you're counting elements of A and B, and then you subtract off what you counted twice (the intersection)

[haughty garden]

A good way to think about independence is to say: the probability of choosing A does not change even if I know that B has already been chosen. So conditioning on B does not affect the probability

[marble pivot]

Ah

Is there some way to think about independence in terms of set theory/venn diagrams/etc?

(for example, mutually exclusive means A and B don't overlap)

[haughty garden]

Think of drawing up A and B overlapping. You might want to think of the probabilities as picking a point inside the event space. The part where they overlap is A and B. So, if you look at the definition, we want the probability of A given B to be equal to the probability of A. The probability of A given B is the probability that you pick a point inside A that is also inside B. In other words, you already know that B has been chosen so your entire sample space has shifted to looking at the event space B. This is why you have P(A and B) / P(B). You just check that this probability is the same as if I were to pick a point inside A to start with

[polar vault]

does anyone know what {on | on} is in game theory
would it be on* or would the * be obsolete and make it just on

[fierce osprey]

Oh yea I see what you mean.. I got the idea of a symmetric difference mixed up with something else

That’s not the answer I would have expected, but it only makes sense

[marble pivot]

Yeah, that formula makes sense, but the idea of P(A|B) = P(A) doesn’t

That makes it seem like B is the universal set

I’m thinking of P(A | B) as |A cap B|/|B|

But if that’s equal to |A|/|U|, then like

Oh I guess I can’t think of it this way since it’s now in terms of ratios rather than sets

[proven silo]

But imagine A is the event it rains tommorow and B is the event you get a head from a coin toss

Would the probabilty of A happening change if given I tossed a head on a coin flip?

No so since they are independent we have P(A|B)=P(A)

[weary tiger]

Same...

[proven silo]

But you have P(A|B)=P(A and B)/P(B). From definition of independence we have P(A and B)=P(A) * P(B), so P(A|B)=P(A)

[marble pivot]

Wait wait hold up

I don’t even understand what we’re dealing with here

Can we deal with any of this purely in terms of set theory?

I understand, intuitively, that independent events have P(A|B) = P(A)

[proven silo]

I just did

[marble pivot]

Oh I guess that works haha yeah

So then, what exactly is probability?

We have all these definitions of P(A or B), P(A | B), etc in terms of P(A) and P(B)

But what is P(A) itself?

[proven silo]

What? Probability of A happening

[marble pivot]

Yeah

Is there a formalization of probability in set theory?

I guess that’s what I’m asking

[proven silo]

If you want probability formalized learn measure theory first

[marble pivot]

Ok

Is that hard? What are the prerequisites for measure theory?

From Wikipedia it looks a bit like topology in terms of difficulty

[proven silo]

Like some analysis and linear algebra needed for measure theory

[shy lagoon]

anybody know how to approach answering this question?

[weary tiger]

how many functions are possible from set a to set B where set mods.lua set is am and modulus Set B is an

n

mod m mod n

[prime parcel]

How can you generalize the sequence

And is this a test?

[shy lagoon]

No, its a practice for finals i got.
But i think i got an idea of what to do from a classmate

[prime parcel]

If you know nth term of sequence then you can solve it

[rotund delta]

Anyone here understand how to prove recursive algorithms through strong induction?

[stray reef]

can you say that again but less incomprehensible?

maybe send a picture

[weary tiger]

Oh let it go i got that

I was in a real hurry

[mystic elbow]

Can anyone please check?

Ping me too

[tall oxide]

Is the elements of this equivalence class equal to a-b where a≡b(mod m) and
a-b = mk + r ?

oops and r is the remainder

[gray cipher]

hello, can someone help me for the proof?

[prime parcel]

Find x^(l+1)

[gray cipher]

How?

Kinda stucked, didnt get any idea

[prime parcel]

If $\textcolor{red}{\sigma (x^l) = 1+x+x²+...+x^l \Rightarrow x\sigma (x^{l}) = x+x²+...+x^l+x^{l+1} = \sigma (x^{l+1}) -1}$

Wait

[vital dew]

it's Sam

[prime parcel]

Does this help? @gray cipher

[gray cipher]

Where is "x - 1" ?

[prime parcel]

You have to $x\sigma (x^l) - \sigma(x^l)$

[vital dew]

it's Sam

[gray cipher]

Alright

[prime parcel]

What will be RHS?

[halcyon storm]

what?

[prime parcel]

https://tenor.com/view/no-idea-gif-9066665

[halcyon storm]

what does RHS mean?

[prime parcel]

Right hand side

[gray cipher]

and then?

[prime parcel]

What's that equal to?

[gray cipher]

Im confused 😦 , still didnt get it

[prime parcel]

Np

Check this

[vital dew]

it's Sam

[gray cipher]

Dang

[gray cipher]

So, thats how it works, thank you so much

[mystic elbow]

Hii

Can anyone please help

3.3

Ping me too

[halcyon storm]

how did u get this?

[prime parcel]

x(1+x+x²+...+x^l) = x+x²+x³+...+x^(l+1)

[halcyon storm]

oh okay thank you

[weary tiger]

are you defining sigma to be the sum of all powers of x?

that is crazy

[mystic elbow]

Anyone 3.3 f how to do

[mystic elbow]

<@&286206848099549185>

[steady kernel]

I think this goes to #probability-statistics

[mystic elbow]

It’s discrete maths tho😅

Topic probability

But sure I’ll post it there

[rotund delta]

There are n friends that are palnning to visit you between day 1 to day D. You only have one guestroom so you can only have one friend stay at a time. If invited, friend i would arrive on a_i and depart on day d_i

You would like to invite a subset of your friends such that exactly one friend is staying with you every day from Day 1 to day D

define a graph where certain paths in this graph correspond exactly to subsets of friends we could invite to say that exactly one friend is staying with you every day from day 1 to day D.

ex:

Alex = [1,4]
Arthur = [1,3]
Max = [3,5]
Mike = [4,7]
Peter = [5,7]
Rey = [7,9]
Russ = [4,8]
Tyler = [8,9]
Yong = [7,8]

One solution would be
Arthur, Mike, Tyler

such that D = 9

[paper sluice]

Why is the number of different subsets of a finite set, S, 2^#S?

[rotund delta]

you asking me to explain to you?

[paper sluice]

If possible, yes.

Cause I don't understand the explanation given by the teacher

This is what is said

And the explanations on google are even more complicated

[rotund delta]

Since you must only decided whether a_i is an element of the subset S, it is implying that it is a binary choice

this mean it is 2^(|S|)

so, let S = [1, 2, 3, 4]

then the number of subsets is 2^4

which is 16

1

2

3

4

1, 2

1, 3

1, 4

2, 3

2, 4

3, 4

1, 2, 3

1, 3, 4

[copper rock]

Question about finding the coefficients of an expansion using the trinomial formula. So I know the process you have to go through with each value having a positive exponent, but what happens when one of your values has a negative exponent? ie finding the coefficients of x^y in an expansion where x has a negative exponent. Hopefully I am asking this properly

[rotund delta]

2, 3, 4

1, 2, 4

[paper sluice]

ohh ok thank you, i think i get it, so it's '2' cause choice 1. a_i is not in subset S or choice 2. a_i is in subset S.

[rotund delta]

1, 2, 3, 4

and i think the last one is the empty set

{}

yeah.....

[paper sluice]

ok thank you for explaining :D, i understant it now

[weary tiger]

Does anyone know how to solve problems like this with chinese remainder thm? Studying for upcoming exam but lecturer never showed any harder examples than x congruent mod b questions.

Idk how to deal with the +2, that confuses me.

video tips is also appreciated!!

[obtuse lance]

just subtract 2 from both sides

[weary tiger]

ohh you can do that?

[obtuse lance]

solve for x basically like you would a regular equation

there are some caveats but yes

division is the only thing you really need to watch out for

[weary tiger]

damn, I have been banging my head against a wall for 2 hours trying to find anything to understand how to do it

but the last one will be -1?

[obtuse lance]

yeah, there's a lot you need to know to know how to manipulate these correctly

[weary tiger]

can i just turn it into x = 2 mod 3 by adding 3?

[obtuse lance]

yeah you can

[weary tiger]

thank you

truly

[obtuse lance]

another way to think of it is to add 1 to both sides since 3=0 mod 3

it's not too serious

[weary tiger]

yeah my lecturer barely explains anything

but the exam is stupidly hard compared to what he teaches

going through previous exams as practice and I feel like I didnt learn anything to tackle these problems

I rabbled too much xD. Thanks man for clearing up

[obtuse lance]

you're welcome

do you know how to get inverses?

for small numbers you can mostly just guess and check

[weary tiger]

yeah euclid

[obtuse lance]

ok good

[weary tiger]

it'll be mostly guesses it seems but 1 part will require inverse through euclid it seems.

[iron summit]

F is a closed set, if U intersects F is open in F, then U is open

[cerulean wind]

what about it? are u trying to determine whether it’s true or false or something?

[iron summit]

trying to prove

[cerulean wind]

what have u got so far?

[iron summit]

if $x\in U\cap F$, this mean there is a $r>0$ such that $d(x,y)<r$ for all $y\in U$

[vital dew]

亜城木 夢叶

[cerulean wind]

the only thing that u can say is that d(x,y) < r for all y in U intersect F

the claim u are trying to prove is false

[iron summit]

oh

[cerulean wind]

take F = [0,1] as a subset of the real numbers

see if u can come up with an example of a set U so that U intersect F is open in F but U is not open as a subset of R

[iron summit]

a discrete set?

[cerulean wind]

a discrete set in R will still be discrete in any subset of R, so that won’t help

[gray cipher]

The result of the simplification of the ¬(¬p ^ q) ^ (pvq)) statement is

kinda confusing me

[halcyon storm]

what is if x,y ∈R then ¬[ ∀x∃y,[(x-y>3)→(x>y)]] is...
How do I answer this?

[gray cipher]

<@&286206848099549185>

[keen python]

What do you have so far

[keen python]

If the logical statement works then you'd answer true, if not false. It relies on showing either the statement is always true, or if you can exhibit a counterexample. Then, notice the "not" at the front flipping your final answer.

[gray cipher]

make it iinto simple statement

But I dunno either it is p or \neg p

[keen python]

Well can you show me what you did lol

[gray cipher]

Im not sure tho

[keen python]

Then how do we know it's p or not p

You should use all the laws for reducing this, start with distributing the not on the far left to (not p ^ q) using DeMorgan's Law

[covert rampart]

What proof for this?

[cerulean wind]

contradiction

[tribal brook]

I dont understand

[vital quiver]

n=28

[tribal brook]

How??

[gray cipher]

https://media.discordapp.net/attachments/898807242407677982/911877855032512552/unknown.png

[gray cipher]

I dont get it

[slate marsh]

Basically find how many natural numbers less than or equal to 100 are divisible by 3

Then of course for each number that is divisible by 3 multiple times count it the according number of times: count 9 (which is 3^2) two times, 27 (which is 3^3) three times

That should be n?

[tribal brook]

Ahh I can imagine it

[weary tiger]

hi, why when we put k+1 here it becomes 2k+1 and not 2k?

[strong hare]

dude

imagine, adding 1 to every term of the sequence

what you get?

a square series

@weary tiger Are you here?

[weary tiger]

yeah 1 sec

let me look at it again

yeah but then we add 2 not 1

i thought all we had to do was replace k with (k+1)

[strong hare]

dude, you know even number and odd number formula?

[weary tiger]

yeah

[strong hare]

tell it

[weary tiger]

2n-1

i know it would be wrong if we make it 2k

[strong hare]

Well, it is actually 2n +/- 1

[weary tiger]

if we make it 2k we dont get odd number

[strong hare]

yep

[weary tiger]

but thats what we have to do

we have to change it k+1

[strong hare]

but look it in another way

when you add 1 to every term

it becomes, 2n+2, 2n

[weary tiger]

ahhh right

i get it now

ya ya i got it

[strong hare]

either way, by mod 2 of both of the values, it will become an even

[weary tiger]

thanks a lot

[strong hare]

That's my task here basically

🤣

[wind tulip]

How do i make a nontransitive relation transitive? Do i just add the elements?

[cerulean wind]

you could add the right elements or remove the elements that are giving you issues

is this a part of a bigger problem or?

[wind tulip]

Well i have 10 pairs of elements as a relation i dont know if thats a big problem or not, my task was to find R^-1, R^2, R^3, R+ and R*

i did everything except transitive closure

and transitive reflexive closure

i know that transitive reflexive is pretty easy as i just need to make main diagonal of matrices have 1 on it, but transitive closure is giving me a problem

my english is pretty bad sorry

[cerulean wind]

for transitive closure, you need to find the smallest transitive set containing R

so you need to figure out a way to add in the least amount of ordered pairs to R to make it a transitive relation

same idea with transitive-reflexive closure. just add in the least amount of ordered pairs to make the relation transitive and reflexive

[wind tulip]

Okay will try

thank you 🙂

[paper sluice]

Could anyone explain this in more dumb terms for me?

Why is the initial assumption ceiling(n/m) -1 items?

And why the total number of objects is not more than m(ceiling(n/m) -1)

[proven silo]

Missing some context don’t you think?

Like idk the original statement we are trying to prove?

[paper sluice]

omg thank you, that's why i was confused, for some reason the question wasn't there, had to go find it

Q: If we have 11 letters to place in 10 pigeonhole boxes, we can put 1 letter in each pigeonhole with one leftover so at least one pigeonhole must have two letters.

I still don't get it haha :')

i guess it's ceiling(n/m) -1 cause the -1 represents the leftover

[proven silo]

So suppose for contradiction that all boxes have at most 1 item

1=ceiling(11/10)-1

Then the total amount of items can’t be more than 10 * 1=10

You can stop there and say 10<11 which is a contradiction, since we said we had 11 items

[paper sluice]

I get this, but where does the formula, ceiling(n/m) -1, come from?

and same for m(ceiling(n/m) -1)

[proven silo]

Nothing special about it (and no reason to even use/know it)

2nd one they just multiply by amount of boxes

[paper sluice]

oh ok, thank you

[paper sluice]

why?

or no reason to know that either?

[proven silo]

m boxes and at most x (here 1) items in each

So there are at most x+x+…+x=m * x items

[paper sluice]

i get it thankss

that makes the rest of the question make sense now

thank you for your help :D

[proven silo]

Np

[weary tiger]

Hey guys can someone explain why this became like that?

shouldnt it have been 2 - 1/(k+1) ?

would appreciate been stuck on this for an hour! tag me if you can help 🙌

nvm i got it

[quaint star]

No, you are using S(k) there not S(k+1)

[paper sluice]

is it permutations without repetitions? so 6!/(6-3)! = 216?

[quaint star]

You are only replacing 1 +1/4 +... + 1/k^2, without the 1/(k+1)^2, which is the LHS of S(k)

@weary tiger

Oh

You said you got it

And I didn't read

[weary tiger]

yea thanks a lot

[quaint star]

No

[paper sluice]

with repetition then?

or not even permutation

[quaint star]

Actually, it is 216,

,w 6!/3!

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Lunasong#7197

[quaint star]

But what you wrote does not equal 216

[paper sluice]

oh what

i guess i typed it wrong in the calculator

[quaint star]

But the correct answer is 216

[paper sluice]

6^3?

[quaint star]

You do not use permutations here, because you can repeat outcomes

Yeah it is 6^3

[paper sluice]

so what do you use?

[quaint star]

6^3

[paper sluice]

where does that come from tho? isnt that permutations with repetitions?

but you said not to use permutations?

[quaint star]

I guess it is, yes. I just don't usually call it permutations.

[paper sluice]

oh ok thank you

i dont rly know how to tell whether its permutation/combinations with/without repetitions

when answering a question

do you have any way that i can tell the diff?

[quaint star]

Well, if you throw a die and get a 3, the next time you throw it, can you get 3 again?

If yes, you can have repetition

[stray reef]

no obviously not, once you've rolled a 3 on your die the 3 face disappears forever and any attempts to bring it back will make the universe implode on itself

[quaint star]

:kekw:

Fuck

[stray reef]

tfw no kekw

[paper sluice]

wait what

[quaint star]

[quaint star]

.

[paper sluice]

so is it 216?

[quaint star]

Yes

I thought we already established that. I am now explaining why there is repetition

Because you don't remove the possibility of getting a 3 just because you got a 3 the first time

If you did, I could make a lot of money playing dice games

[paper sluice]

oh just kinda got confused when the joke was made lmao

[paper sluice]

tru, ty

but when im answering a question the obvious just doesnt come to me at first :')

[quaint star]

It happens. Sometimes it is explicitly given. Like if you draw balls from a bag, they tell you if they put the ball back after drawing it or not. Othertimes you just have to think about whether outcomes are removed or can be repeated.

[paper sluice]

ok thank you, ill have to try reading the question more carefully :)

thanks for your help :D

[quaint star]

👍

[paper sluice]

Slides for context

But i am wondering how they get from the formula for combinations without repetition to the formula for combinations with repetition?

How does n! turn into (r+n-1)!?

And r!(n-r)! into r!(n-1)!?

I dont get their explanation

[dim swallow]

Can somebody help me with this?
How many possibilities are there to color 23 balls of different sizes so that 9 are red, 5 are black, 4 are blue, 4 are green and one is white?
I did it as a permutation of a multiset but im not sure that this is correct if the size of the balls matters

[quaint star]

Choose 9 to colour as red, then choose 5 to colour as black, then choose 4 to colour as blue, then choose 4 to colour as green, then choose 1 to colour as white

[hidden mantle]

I have a kind of path finding problem.
I have a n number of 2d points,destinations, and problem is generating an efficient connection between all of them, minimizing the length of road used to connect all destinations and minimizing the travel length between any 2 points.
Only straight and 45° diagonal roads are allowed (so only in 8 directions). switching between them is allowed.
Ive been approaching it as a graph problem where its a uniform grid and every vertex(in a grid) is connected to its adjacent and diagonals but i could not find a solution for this kind of path making problem. Ive been trying to think of it as a modification of a path finding problem between 2 points but im stuck on finding a way to transform that into multi destinations all connected to each other.
It would be great if anyone knows of a solution or just knows what this kind of problem would be called so i can read on it.

[tidal tulip]

What does the {A_p} p in P notation mean in the below? Would it mean something like this: Let's say A={1,2,3,4,5} and P={1,2,3} , A_1 = {1,2,}, A_2={3,4}, A_3={5} then {A_p} p in P is the set of elements: A_1, A_2, A_3, eg {A_p} p in P = {A_1, A_2, A_3} -- is that what its saying notation wise?

[tidal tulip]

<@&286206848099549185>

[hidden mantle]

here is an example of what i mean for the outcome but this is not an actual solution

[north dust]

What do you guys think of Catalan numbers?

[weary tiger]

muy buenos

[cerulean wind]

every time i see a C with a subscript n i gag

[weary tiger]

I think that's nearly the Euclidean Traveling Salesperson Problem (TSP)!

[hidden mantle]

i dont think it is. ive looked into it more and i think its a all-pairs shortest path problem but also takes into account trying to reuse edges as much as possible

[weary tiger]

key word nearly :P

[hidden mantle]

fair enough

[weary tiger]

sounds cool though

[hidden mantle]

ikr, its for a minecraft project

[tidal tulip]

can anyone confirm this understanding is correct

[lunar halo]

Yeh, just split your set into disjoint subsets, and then they also label them by things from a set P

[tidal tulip]

@lunar halo thanks!

[analog vapor]

anyone here who can quick tutor us if ure free rn

need help w the topic cuz ive got no idea what im studying rn in university lol

[weary tiger]

Guys I dont get strong induction

I am reading from a book but every example is so different from the last

its like we use a different thing for every problem

I dont get it...

[tidal tulip]

i want to make sure i understand the def of partitions, a partition S of a set A is defined as a set of subsets of A of vs just subsets of A, correct?

eg if A={1,2,3,45} then S={{1,2,3,4,5}} is a partition but X={1,2,3,4,5} is not

[proven silo]

A partiton of a set, A, is a set of non-empty subsets of A such that every element a in A is in exactly 1 of the subsets.

Yes S in your example is the trivial partition

[proven silo]

Strong induction is just you assume true for n<=k instead of just n=k

Only difference

[weary tiger]

Yeah I know it sounds simple

but like there is a different method you have to use for each problem

[proven silo]

Wdym

[weary tiger]

uhhh 1 sec

https://math.stackexchange.com/questions/833746/complete-induction-proof-that-every-n-1-can-be-written-as-a-product-of-prime

https://math.stackexchange.com/questions/1043891/prove-that-every-amount-of-postage-of-12-cents-or-more-can-be-formed-using-just/1043917#:~:text=3-,Prove that every amount of postage of 12 cents or,cent and 5-cent stamps.&text=Using the inductive hypothesis%2C we,cent and 5-cent stamps.

These are 2 simple problems

but their solution is so much different

[proven silo]

Not sure what you expect. You expect every single proof to follow the exact same idea?

[weary tiger]

Yeah idk, its hard for me 😦

[tidal tulip]

and X isn’t a partition because it isn’t a set of subsets, it’s just a subset, is that correct?

[stray reef]

i mean, mathematical reasoning is not intended to be simple. there will always be something your brain just has to happen upon. a key idea that ties the proof together.

[weary tiger]

hmmm okay

I will keep practicing and see what happens

[tidal tulip]

Could someone confirm my reasoning for X not being a partition because it’s not a set of subsets of A is correct?

[stray reef]

yes

assuming you meant to type A = {1,2,3,4,5} that is

and not {1, 2, 3, 45}, which is also a valid but different set

[paper sluice]

For i, I got n = r! as n = r
For ii, I'm confused, but maybe it's r = f^-1(n)?

[tidal tulip]

@stray reef Thanks! Yeah, I meant A={1,2,3,4,5}

[stray reef]

n = r! as n = r

what does this mean

[peak plank]

can anyone help me with the below mentioned question. i'm really confused with thus one.

The following Boolean function is given:

f (a, b, c, d) = ((a + b) ↔ c) d + ((ab) ⊕ c) d 0
where a ↔ b = ab + a 0 b 0 (equivalence) and a ⊕ b = a 0 b + ab 0 (antivalence). Do a total of four
perform various Shannon expansions by adding the function f for each of the four variables
(not recursively) develop. What did you notice?

[paper sluice]

cause im thinking its permutations with no repetitions, and cause there are r lower cases and r numbers, i thought r = n so n = r!?

is that right?

[shadow grove]

What does the smallest common multipla have to do with the exclusion inclusion principle?

I've seen it used to determine the third term on the right hand side, but I don't see why it has to be the (for lack of a better word in English) common-set of the two?
|A cup B| = |A| + |B| - |A cap B|

I understand that scm(a,b) is the set containing all of the common values of all multiples of A and all multiples of B.

But in one assignment I was given, the teacher used scm(a,b) in place of |A cap B|, here is the assignment:

We have the set T = {1,2,....,180} and the numbers a = 6 and b = 9.

Here the set of all numbers that has a as a divisior A has the size |A| = 30

And |B| = 20.

Combined, using the inclusion and exclusion principle we get, that

|A cup B| = |A|+|B|-|A cap B|.

Here my teacher used scm(a,b) = |A cap B|.

My question here is; surely scm(a,b) is bigger than |A cap B|.

Where |A cap B| simply is the set of numbers between 1 and 180 that are divisible by 9 and 6, while scm(a,b) is the set of ALL integers, that are divisible by 9 and 6...?

Please tag me, as I get no notifs 🙂

[haughty gull]

can anyone solve this? Consider a tournament between N teams, each team playing each of the other teams. Let’s call team i a k-winner if there is a group of k-many teams that were each beaten by team i. Other teams may have beaten team i, but there is at least a group of size k that was roundly beaten by i.

Question: Bound the probability that there exists a k-winner in a tournament of size N?

[stray reef]

no, you're way off

first off where in the problem does it say symbols can't repeat within a label

[paper sluice]

It said distinct so I thought

[stray reef]

distinct LABELS

[paper sluice]

Oh distinct products?

[stray reef]

the LABELS themselves are distinct

[paper sluice]

Ok yh I misread

[stray reef]

and second why does your answer not even involve the numbers 26 or 10

[paper sluice]

I saw distinct so automatically assumed

[paper sluice]

Ohhhh

I didn't think that deeply....

26 letters and 10 numbers

Urgh I'm dumb thank you for pointing it out

I gotta go but can we continue this off another time?

I'll try it again when I have time

Thanks see ya

[stray reef]

...i guess

[lilac delta]

can i have some help with this? Recurrence Formula A certain divide-and-conquer algorithm works by dividing the input of size “n” unto four parts, each of size n/4, recursively solves each of them, and combines them to the final answer. The divide and combine steps take O(n) time.

i dont understand why d equals to 1

[paper sluice]

1i) ⌊10^6/(26^r * 10^r)⌉ - not really sure what they meant by the function of r but I used pigeonhole principle

[lilac delta]

Do i have to keep going for T(n-4)… etc?

<@&286206848099549185>

[jaunty trout]

Good discrete maths textbook for beginners?

Or other type of resource, though I prefer a textbook

[tacit wharf]

Would someone be willing to double check my work? I set this up as $f\left(n\right)=f\left(n-1\right)+2f\left(n-2\right)+3f\left(n-5\right)+f\left(n-10\right)$ but I'm not sure if that holds up and our lecture had no examples of word problems

[vital dew]

Ironsolute

[shadow grove]

If I have a congruency equation (Where == is the congruency symbol, not the equality symbol).

a == 43(mod 23)

And I can manipulate it into the equation

a == 20 + 23*1 (mod 23), indicating that a == 20 (mod 23)

What is the difference between a == 20 (mod 23) and a = 20?

I have the rule that says a == a (mod n) is true.

If I set a = 20 -> 20 == 20 (mod n) must then also be true, no? So there is no difference?

[deft dock]

does anyone know what the 3rd notation is??

ive never see a^c

how would u even evaluate that to true or false

[shadow grove]

This really is a long shot; But in my discrete mathematics courses, we use the ^ (wedge) to mean "and"...?

[deft dock]

interesting; ig the && also means and then likely. thanks

[north dust]

I took two hours to prove something regarding Catalan numbers, ahhh

[signal shard]

Might be an XOR. I'm assuming "!" is "not", "&&" is "and", and "||" is or

[prime parcel]

a = 20 (mod 23) means a= 23k+20 for some k=0,1,2,....

[stray reef]

k ∈ Z, not necessarily positive :p

[prime parcel]

True that

[weary tiger]

Isn’t the equal sign supposed to be 3 lines

[paper sluice]

1i) ⌈10^6/(26^r * 10^r)⌉ - not really sure what they meant by the function of r but I used pigeonhole principle

[gritty pumice]

rosen discrete math

[stray reef]

it means that you should have a formula that gives the number they want, expressed in terms of r

also you have not done what 1i asks for

[paper sluice]

is it n = 26^r * 10^r

then for part ii, r = log_260(n)

[stray reef]

yes precisely

[north dust]

Ahh, I feel that it's going to be tedious to prove that a binomial coefficient is a integer, AHH

[paper sluice]

ok thank you :D. Also for part iii, is it r = log_260(1,000,000) = 2.48... = 3?

[stray reef]

r ≥ log_260(1,000,000)

r ≥ 2.48...

so the min value of r is 3

[paper sluice]

oh right, didnt include the inequality

thank you!!

[jaunty trout]

Thanks!

[shadow grove]

Say I have defined some binary predicate P(x,y) with intepretation F_R with Dom(F_R) = \doubleR.

Say it is always true in F_R.

Now say it is not so in F_L with Dom(F_L) = \doubleL.

Is P(x,y) a model in F_R and a countermodel in F_L?

If not, how would I articulate that P(x,y) is always true in F_R, but it is false in F_L?

[fierce drift]

any good youtubers to learn prob theory?

[past burrow]

is this right?

[stray reef]

you switch your notation in parts b-d for seemingly no reason

why f(n) and not a_n?

(c) should have a(n+1) = a(n) + 2n

and (d) should have a(n+1) = a(n) + 2n + 1

[past burrow]

my bad idek why i did that lol