discrete-math

[weary tiger]

So where did you get the 14 from

[haughty garden]

We can think about how many ways to divide the books into two groups

Imagine a line of 5 books.
B B B B B
To ensure that there is at least one book in each group, we can divide the line into two groups in the following ways.

B | B B B B
B B | B B B
B B B | B B
B B B B | B

Can you see where the 14 comes from when we extend this to 15 books

[weary tiger]

I'm just gonna accept thay I will not get it LOL

[haughty garden]

What part do you not get?

[weary tiger]

for example

I mean

if were to put 1 book on shelf 1 and 14 on shelf two

how could you calculuate this

[gritty pumice]

Ahh right my bad

[weary tiger]

what is 14?

[gritty pumice]

😅

[weary tiger]

like 15! is n

what is 14 exactly?

[gritty pumice]

14 ways we can arrange

[haughty garden]

Pick a random book to be on shelf 1. Then arrange the rest. You get 15 * 14! = 15!

[weary tiger]

there are 14 ways we can arrange the books? so what is 15!

yeah that true

[gritty pumice]

Becuz 15 books

[weary tiger]

but the answer is 15! * 14

[haughty garden]

That's when we run through every combination of k books on one shelf and 15 - k books on the other

In the case where k = 2, we choose two books to sit on shelf 1. We have C(15, 2) different ways of doing so since we don't care about the order in which we choose those books. Then we arrange the two books in 2! ways. The rest can be arranged in 13! ways. This gives us: C(15, 2) * 2! * 13! = 15!

In fact, you can generalise to $k$ books. Choose $k$ books arbitrarily to sit on shelf 1. Arrange them. Then arrange the remaining $15 - k$ books. This gives you [ C(15, k) \cdot k! \cdot (15 - k)! = \frac{15!}{k! \cdot (15 - k)!} \cdot k! \cdot (15 - k)! = 15!] arrangements

[vital dew]

opengangs

[weary tiger]

ok

[haughty garden]

Then you run $k$ from 1 to 14 to give you the required answer of [ \sum_{k = 1}^{14} 15! = 15! \times 14]

[vital dew]

opengangs

[gritty pumice]

U also gotta consider the way there are arranges on the shelf, book1, book2 is different arrangement from book2, book1, that’s where 15 factorial comes from, you have 15 books

[weary tiger]

@gritty pumice I got it @haughty garden thank you

[amber minnow]

https://math.stackexchange.com/a/729592/538409

Does the expression in the addendum seem correct?

Should we be able to simplify this as

$$\frac {(n+k-1)!}{n!(k-1)!}$$

[vital dew]

Finitely Many Bananas

[amber minnow]

I don't understand why they used the gamma function in their expression when simple factorials would have sufficed

[weary tiger]

how can I prove this?

[haughty garden]

\begin{align*}
\frac{n + 1}{n + 1 - r} P(n, r) &= \frac{(n + 1)n!}{(n + 1 - r)(n - r)!} \
&= \frac{(n + 1)!}{[(n - r) + 1](n - r)!} \
&= \frac{(n + 1)!}{(n - r + 1)!} \
&= \frac{(n + 1)!}{[(n + 1) - r]!} \
&= P(n + 1, r)
\end{align*}

[vital dew]

opengangs

[stray reef]

to summarize, one way to do this is simply by bashing.

[steady meadow]

Hey, i tried to prove the following statement is tranzetive, did i do it right?

<@&286206848099549185>

[final cliff]

Shouldn't transitivity here follow almost immediately from the fact that multiplication is commutative?

ab=ba and all that jazz.

Oh shit I'm dumb lmao

Why am I mixing up transitivity and symmetry lol.

[steady meadow]

lol

[stray reef]

why not rephrase the relation as "a R b iff ab is odd" before continuing?

that way it's clear that it's equivalent to "a R b iff both a and b are odd", which makes transitivity obvious

unless, of course, your teacher forbids such trickery

[steady meadow]

I need to show transitivity like this: aRb and bRc -> aRc

[stray reef]

so your teacher explicitly forbids any arguments to be made before working through the definition of transitivity?

[final cliff]

You can always show off to the side aRb iff a,b are both odd.

[stray reef]

it sounds like they're explicitly banned from doing so tho.

[final cliff]

I see.

Maybe they could still do it after assuming aRb and bRc?

[steady meadow]

I guess so lol

[stray reef]

that didn't sound like a very confident "yes she forbids it"

[steady meadow]

This is how i should do it, in this pattern

[final cliff]

You see how if either a or b is even that ab is even so aRb won't be true right?

And how if a and b are odd that ab is odd so aRb will be true?

[steady meadow]

Yea i see

but i need to work according a pettern

[final cliff]

So then you can just prove whatever bits you need from the equivalence Ann is suggesting in the proof format you're trying to use.

[tidal mica]

How should I solve this? Topic is : calculus of finite differences

[olive wren]

(First off, hi)
Try expanding the sum?

Into like two sums

[weary tiger]

hi

@tidal mica hu

Hi

You undriended me

Wow

[olive wren]

So you get:
[ \sum_{k=1}^{10} s(k+1) - \sum_{k=1}^{10} s(k) = \sum_{k=2}^{11} s(k) - \sum_{k=1}^{10} s(k) = s(11) - s(1) ]

[vital dew]

Slurp

[olive wren]

(For the last step, take out any elements of the sum that aren’t in both sums, and the rest will cancel out)

[tidal mica]

Uuuuuu I didn't think of that 😆

Thank thank thank it's clear and ez

[olive wren]

Np gl!

[weary tiger]

[amber minnow]

Question: how many ways can I write an element $r$ as a sum of $k$ elements of $\mathbb{Z}/(p^n-1)\mathbb{Z}$.

[vital dew]

Finitely Many Bananas

[amber minnow]

repetitions allowed, but 1+2=2+1 should be counted as the same

Once you choose the first k-1, the last one is determined by that

So I think it should be $\frac{(p^n-1)^{k-1}}{k!}$

[vital dew]

Finitely Many Bananas

[amber minnow]

Where the k! comes from accounting for reordering

Does this seem correct?

[weary tiger]

how many ways we can arrange the word ESTATE so all the vowels are adjacent?

My thought process was 3 * 4!/2! * 2!

why is this wrong

[haughty garden]

Group the vowels together to form a single “letter”. Then you’re just arranging (EAE)STT which can be done in 4! / 2! ways. Then you need to look at all the ways EAE can permute among themselves which is done in 3! / 2! = 3 ways.

It seems like you’ve double counted by treating either the E’s or T’s as separate letters or something

[haughty garden]

That might overcount some non-solutions since you can choose out of a list of p^n - 1 elements. Take p = 2, n = 3 so you’re working under Z/7Z. If you want to write 5 as a sum of 3 integers, then you have {(0, 0, 5), (0, 1, 4), (0, 2, 3), (1, 1, 3), (1, 2, 2)} solutions since any other solution is just a permutation of this solution set. But your claim states that there are 7^2 / 3! ≈ 8 solutions

(I might also just be missing some solutions because I’m doing this on a whim)

[amber minnow]

6+1+5 is a solution

Because we're working under mod 7 remember

[haughty garden]

Oh yep

I’ll think about this a bit more once I’m home

[amber minnow]

Yeah there's something definitely wrong with my answe because 6 does not divide 49

[amber minnow]

Did you get a chance to look at it?

I think an explicit formula for this would be pretty hard/ possibly only recursively defined

I think my formula should at least be an upper bound

[amber minnow]

Can someone verify this?

[haughty garden]

An explicit formula is quite difficult for this problem I think

[weary tiger]

I'm only struggling with E

4 13 4
3 1 2

that's my answer but it's wrong

3 out of 4 aces, 1 of 13 cards that's repated twice so 2 out of 4 suits

is this wrong?

[haughty garden]

if you've chosen three aces, you can't get a pair ace

Choose 3 out of the 4 aces.
To pick a pair, you choose the card value. Since 3 aces have been chosen, you can't get a pair ace anymore. Therefore, you only have 12 choices to choose 1. Then you choose two out of the four suits

[weary tiger]

yeah that completley makes sense

damn I missed that small detail

because there will be 1 ace left so we can't get 2 pair

thank you

[haughty garden]

no worries! 🙂

[weary tiger]

are combinations confusing or

I'm just dumb? lol

I really feel like I'm not programmed for it

[haughty garden]

you're not the only one, it takes some time to get used to it

[weary tiger]

i feel you

[haughty garden]

it's a very different field to, say, calculus

[weary tiger]

oh yeah...

calculus is a joke god dman

the funny part that these things are so tivial

in comparison to the complicated calculus problems

yet they are 10x harder lmao

[haughty garden]

yeah, combinatorial problems are easy to formulate a question but they can be really difficult to answer (simply because you have a lot of things to consider)

[weary tiger]

I try to break every porblem

[haughty garden]

I find that it's hard because there's so little to actually write down as opposed to calculus or linear algebra where, at the very least, you can write a formula down and hope it leads somewhere

[weary tiger]

to a case

hmmm I see

well wish me luck I'm not even math major but I'm taking discrete math next sum for fun!

so we will see if I will regret it or not haha

[haughty garden]

haha good luck! Feel free to ask some more questions if you get stuck again 🙂

[weary tiger]

thanks

[compact slate]

I have large sets and need to compute |A - B - C - D - E - ...|

the only efficient operation is the set intersection. How can I do that?

the problem is somewhat simplified if I apply the intersection to B, C, ... first, making all of them subsets of A that I want to subtract.

|A - B| = |A| - |B|
|A - B - C| = |A| - (|B| + |C| - |B ∩ C|)

it's easy to see that when working with subsets of A, then we're actually subtracting the size of the union

but I'm not sure how to compute the size of the union of N sets

|X ∪ Y| = |X| + |Y| - |X ∩ Y|
|X ∪ Y ∪ Z| = |X ∪ Y| + |Z| - |Z ∩ (X ∪ Y)|

because at some point it seems to require computing the actual union and as I've said, I can't do that efficiently in this case

|X ∪ Y ∪ Z| = |X ∪ Y| + |Z| - |Z ∩ (X ∪ Y)|
|X ∪ Y ∪ Z| = |X ∪ Y| + |Z| - |(Z ∩ X) ∪ (Z ∩ Y)|
|X ∪ Y ∪ Z| = |X ∪ Y| + |Z| - (|Z ∩ X| + |Z ∩ Y| - |X ∩ Y ∩ Z|)
|X ∪ Y ∪ Z| = |X| + |Y| + |Z| - |X ∩ Y| - |Z ∩ X| - |Z ∩ Y| + |X ∩ Y ∩ Z|

ok I think I got it

not sure how to express it as a sum yet

|X ∪ Y ∪ Z ∪ W| = |X ∪ Y ∪ Z| + |W| - |W ∩ (X ∪ Y ∪ Z)|
                = |X ∪ Y ∪ Z| + |W| - |(W ∩ X) ∪ (W ∩ Y) ∪ (W ∩ Z)|

and I guess we have the formula for the union size of three elements already so a recursive definition is possible here

|X_1 ∪ ... ∪ X_n| = |X_1 ∪ ... ∪ X_n-1| + |X_n| - |(X_1 ∩ X_n) ∪ ... ∪ (X_n-1 ∩ X_n)|

[rugged karma]

I need to build incidence matrix of oriented graph.
But on some sources, end of vertex is -1, and on others end of vertex is 1. Why is that?

[pure terrace]

Anybody really familiar with the Collatz Conjecture and think they could help me figure out if I've found a new pattern in the gaps between orbital lengths?

Here is a small write up. Forgive me if posting links is not allowed, feel free to remove. https://www.reddit.com/r/Collatz/comments/rpfka9/interesting_fractallike_structure_found_within/

[stray reef]

what do you mean by "end of vertex"

do you mean "end of edge"?

[stray reef]

x1 is an edge

not a vertex

vertices are the things you labeled 1-5

[rugged karma]

then, edge

[stray reef]

anyway, whether beginning gets 1 and end gets -1 or vice versa is a matter of convention

[weary tiger]

I'm having hartd time understanding the logic here

if one of p1 and p2 and p3... and pn is false

doesn't that make the entire statment false?

how is the implication p -> q is true if one of the premises is wrong? shouldn't

[rugged karma]

ty

[coral parcel]

What does the dagger in the first line mean?

[coral parcel]

Assuming we can ignore the dagger: If one of p1 ... pn is false, then the conjunction is false. However, that conjunction is to the left of an implication sign, so that being false makes the implication true. (Because F->T and F->F both make T).

[weary tiger]

how does this apply to this statment then

if 3+4=12 then 3+2=6

shouldn't this be a false statment?

since p is false

and q is false

[coral parcel]

"False -> False" is true.

[weary tiger]

ahh!

if my premise that p is false

[coral parcel]

Whether this can be written as "if ... then" is a subject I have strong opinions on, but that doesn't apply to your quote because it uses -> rather than "if ... then".

[weary tiger]

and my conclusion is false

then the implication is true!

i guess that's proper

I was under the impression

that the implication is false

if p -> q and q is false

regardless of p

that's not right?

[coral parcel]

Sorry, I can't parse that. Are you saying

If "p -> q" and "q" are both false
then what?

[prime parcel]

Troposphere

[patent fulcrum]

Hey there. Are R^R and R equivalent? maybe you can give a hint how I can make up a solution?

R^N ~ R I think because if we encode R as a set of sequences of 1 and 0 we can represent each real number as an infinite set of infinite subsequences which can represent N -> R function

But I can't say the same about R^R

[stray reef]

R^R is at least as big as 2^R

if by "equivalent" you mean "same cardinality"

[patent fulcrum]

By equivalent I mean the existence of bijection between the two

[patent fulcrum]

Of course, but is 2 ^ R equivalent to R then

And "at least as big" but is 2^R as big as R^R?

[stray reef]

|2^R| > |R|

|2^A| > |A| always

[patent fulcrum]

Ah that makes sense

Indeed

Thanks

[quaint ermine]

There's some way to obtain y(n) given H(e^jw) and x(n) using only Fourier's series?

[shut peak]

It asked me to convert from POS to SOP using Kmap

so I did this

My answer is
B'C'+AC

Is it correct?

[quaint ermine]

Yeap

In any case you can check in a Karnaugh map calculator. But for me it's okay

[alpine yoke]

kinda stuck here
can someone help?

[coral parcel]

Do you have a definition of the indexed intersection notation you can unfold here?

[alpine yoke]

I think I do? but it's in French

More generally if {...} (not good enough at latex to try to type this lol) is a collection of sets, .... is a set of elements 'c' that belong to every A(alpha)

[coral parcel]

So you're looking for things that belong to every { a in N | a > n }, where "every" means for every n in N.

[alpine yoke]

but N contains an infinite amount of elements so there couldn't possibly be any?

[coral parcel]

Right.

[alpine yoke]

so none?

[coral parcel]

Yes.

[alpine yoke]

oh i see thank you so much

was stuck there for so long haha

[coral parcel]

Or rather, the set with no elements.

[alpine yoke]

I'm sorry for bothering you again, but what about this?

The definition I have been given:
More generally if ${A_\alpha, \alpha \in I}$ is a collection of sets, $\bigcup_{\alpha \in I} A_\alpha$ is a set of elements 'c' that belong to at least one of the $A_\alpha$

[vital dew]

pogn't

[ember obsidian]

draw some sets in the collection

[alpine yoke]

Something like this? What I think to have understood from the definition is that it could be any set in the gray area. Is that correct?

[ember obsidian]

these arent the sets

see how A_r is defined

[alpine yoke]

mhm

I still don't get it

A_r is defined as any elements having x^2 + y^2 bigger or equal to r^2

[ember obsidian]

what does x^2+y^2=r^2 describe?

[alpine yoke]

what do you mean? Im really sorry but im so confused

[ember obsidian]

it describes a certain shape

[alpine yoke]

you mean Pythagoras 'theorem? but what does it have to do with sets?

I did think of that at first but i cant seem to link it with what i have here

[ember obsidian]

circle, center (0,0), radius r

[alpine yoke]

omg

i see now

wow im literally that dumb

tysm

[ember obsidian]

A_r is the circle & points outside it

np

[alpine yoke]

so just making sure but it's basically all the red area, right?

[ember obsidian]

yes

[alpine yoke]

but how would you write that? 😅

[ember obsidian]

its described in the definition of A_r

[alpine yoke]

so i just copy paste it?

[cloud cargo]

is it just me or does it seem like the circle is getter smaller and smaller

[ember obsidian]

the sketch is just to help u find the union

[alpine yoke]

🤔

Well the union is basically everything but what's inside the circle but i have no clue as to how i should mathematically write this

[alpine yoke]

<@&286206848099549185> ?

[coral parcel]

Everything except the interior of the circle is one of the sets you're taking the union of.

[blazing timber]

Unit-3Recurrence Relations 8 hours
Towers of Hanoi, Iterations, Homogeneous linear equations with constant
coefficients, particular solution, Solution of homogenous recurrence relations with Particular
solutuons and Total solutions. difference table, finite order differences,Line in a plane in general
position,

i have these topics to cover

can anyone tell me any better resource

[olive wren]

MIT OCW has a good discrete math course that covers a lot of that

[blazing timber]

where i can i find it

[olive wren]

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/

[blazing timber]

thank you so much

[olive wren]

Np

I think lecture 15 covers the material

Might want to watch around as well, I might be wrong

[slate burrow]

can i assume that $(k+1)^{2} \\Leftrightarrow\ ( k-1)^{2}$ ?

[vital dew]

Steppaz

[slate burrow]

I mean it's not but could i assume that if i used Strong induction?

really?

[hollow grove]

this notation doesn't make any sense

[slate burrow]

yes

i gotcha

thanks

ah it works

[haughty garden]

P(k + 1) = 2(k + 1) + F(k) - 1

Yeah

I had a brain fart moment and thought my solution was wrong but it was fine lol

But once you expand everything out, you get P(k + 1) = (k + 1)^2

Well your definition of F(n) is 2n + F(n - 1) - 1. So if you let n = k + 1, you replace all of the places where you see n with k + 1

// something tells me I can’t do math when I’ve just woken up

[deft dock]

what topic of math would one explore after doing a college course on discrete math

i also dont know if i got the full gist of discrete math, bc sometimes i see things in this channel that i had never seen in that class

[haughty garden]

real and complex analysis perhaps, abstract algebra, perhaps another course on number theory if that piqued your interest

[keen lava]

@deft dock I would say a mathematical structures class is the next step up, the beginning will feel familiar but it branches off really quickly.

[balmy ivy]

Combinatorics

[fallen vigil]

My combinatorics and probability intuition was awful in discrete math, does it get better with practice or am I cursed

I just couldn’t “get” it no matter how hard I studied

which is weird because I get everything else, Calc I-III, Linear Algebra, ODEs, and everything else in Discrete Math was fine

[slow jewel]

Any ideas on how to start going about this?

I know from Mengers theorem that for every two vertices u, v there is 5-internally disjoint uv-paths

[stray reef]

yeah so there are 5 internally disjoint paths from u to v

i.e. 5 paths from u to v that never meet at any vertices other than u and v themselves

thus w can lie on at most one of those paths

the other 4 paths can comprise your two cycles

@slow jewel

[slow jewel]

write

i think drawing is simplifying this quite alot

Thnaks

[stray reef]

i am not oversimplifying it in the slightest tbh

you can generalize this to arbitrary k-connected graphs

for a $k$-connected graph and $u, v, w_1, w_2, \dots, w_r$ pairwise distinct vertices in $G$ you can get the existence of $\floor{\frac{k-r}{2}}$ cycles that all have only $u$ and $v$ in common but none pass through any of the $w_i$

[vital dew]

Ann

[spice rover]

if i have a planar graph i can pick a vertex and embed it in the plane such that the vertex is on the outside

is it possible to do this if i want to pick two vertices?

if not does any1 have a simple counterexample

[stray reef]

@spice rover still here?

i think you can't do it with the octahedral graph and two nonadjacent vertices

[jagged junco]

• We have 50 red rocks and 50 blue rocks
  In how many ways can you place the rocks on a 10x10 chessboard such that the red rocks sit only in the black squares and the blue sits only in the white squares, or the opposite?

I think that it is 50! * 50! * 2 is it right?

[stray reef]

are the red rocks distinct from each other?

[jagged junco]

they're identical

[stray reef]

then there's only two

either red goes on black and blue on white, or the opposite

[jagged junco]

aha makes sense

and if they're not identical?

[stray reef]

if the red rocks are all distinct, and all the blue rocks are distinct, then your original answer becomes correct.

[jagged junco]

aha I understand now 🙂 thank you ann

The second part of this question is:

• We have 50 red rocks and 50 blue rocks (they're distinct from each other)
  In how many ways can you place the rocks on 10x10 chesboard so that in every line you have exactly 5 blue rocks and 5 red rocks.

---

Is the answer now is:
For specific line: (10c5) * 5! * 5! / 2!
And then multiply this by 10 for whole board?

is it correct?

[stray reef]

define "in every line"?

do you maybe have a picture of the question exactly as it was stated? i want to ensure that there are no missed but crucial details in wording

[jagged junco]

Every line is like 1, 2, 3, 4..

[stray reef]

so every row?

[jagged junco]

yes sorry my bad

every row is more correct to say

[stray reef]

For specific line: (10c5) * 5! * 5! / 2!
this is correct
And then multiply this by 10 for whole board?
this is not

[jagged junco]

why not multiply by 10?

[stray reef]

...wait hold on

where did (10c5) * 5! * 5! / 2! even come from

i must have misread either your question or your attempt at an answer

and you've also refused to share any pictures of the question so i strongly suspect you fucked up the wording and anything i say now will be pointless!

[jagged junco]

Let's say we're looking at specific row.
We want to pick place for the Red rocks first so (10c5) then placing them on the chosen spots 5!, and all the Blue rocks go to the rest in same row so 5!
Then dividing by 2! because I prioritized the Red rocks first and the blue rocks second, and it can be the opposite

[jagged junco]

yes I'm sorry I didn't provide any pictures

[stray reef]

well CAN YOU????

We want to pick place for the Red rocks first so (10c5) then placing them on the chosen spots 5!, and all the Blue rocks go to the rest in same row so 5!
Then dividing by 2! because I prioritized the Red rocks first and the blue rocks second, and it can be the opposite

[jagged junco]

I don't have any picture there to be honest , it's just wording and it's not in English so I tried my best to find a picture that desribes the problem like the one I sent

[stray reef]

this smells like bullshit through and through but i don't know exactly how to explain it to you

[stray reef]

so what language is it in?

[jagged junco]

I'm sorry hmm it makes sense to me

[jagged junco]

hebrew 🙂

this is the original question the one I asked earlier

[stray reef]

so let me get this straight

[jagged junco]

with the 50! * 50! *2

This is the last question

just wording

and that picture they provided is not good picture haha

[stray reef]

i don't speak hebrew

[jagged junco]

yes I know I know just wanted to show you that you did'nt miss anything

🙂

[stray reef]

did you put that emoji there on purpose to infuriate me

so you have a 10 by 10 chessboard, you have 50 red stones and 50 blue stones and they are all distinct from one another

and you want the number of arrangements of these stones on the board in such a way that each row has exactly 5 stones of each color...

[jagged junco]

Exactly

[stray reef]

okay, so then that sounds like $\binom{10}{5}^{10} \cdot 50!^2$

[vital dew]

Ann

[jagged junco]

It makes sense to me, yea I think it's correct too. Also need to divide by (2!)^10

[stray reef]

no, you do not.

[jagged junco]

But we did (10c5) so you don't know who goes first there?

[stray reef]

we arbitrarily decided to arrange the red stones first

(10C5)^10 is the number of ways to pick the spaces where the reds go

once we've settled on one of the choices, the rest will become the spaces for blue stones

[jagged junco]

Right

they taught us that if we artiblary decide something goes first we need to cancel it by dividing by the number of "options that can go first"

[stray reef]

???

what are you talking about

are you sure you aren't misinterpreting or misremembering something

[jagged junco]

I'll give you an example in other question
Let's say we want to divide 4 people into 2 pairs
So we do
(4c2)(2c2)/2!

so it's the same concept

[jagged junco]

maybe I got it wrong but this is what I remember sorry

[stray reef]

no it's not the same concept

when dividing two ppl into pairs, the pairs themselves are indistinguishable

i.e. the assignment Pair 1: A, B; Pair 2: C, D is the same as Pair 1: C, D; Pair 2: A, B

[jagged junco]

aha I get what you mean

so you said previously because it's distinguishable so we don't need to do division

I think

[jagged junco]

yes

thank you for your help ann I'm sorry if I infuriated you I appreciate your help

[jagged junco]

it makes more sense to me the more I think about it

[spice rover]

seems right thx

[iron bloom]

is there a mistake in the table here? Doesn't {1, 3, 2} o {2, 1, 3} mean we are first performing the {2, 1, 3} mapping and THEN the {1, 3, 2} mapping?

[gritty pumice]

yes

but they are using weird notatioin

usually we use ( ) for permutation cycles

[stray reef]

well you aren't done yet

but so far you have not made any mistakes

[slate burrow]

What is the next step?

I don't know how to proceed

[stray reef]

well as you can see the congruences you arrived at are clearly false no matter what k is

and 49 is not 3 mod 4.

yes, that is what it means

you have shown that if n is odd, then n^2 has a remainder of 1 when divided by 4 (as evidenced by (2k+1)^2 = 4k^2 + 4k + 1)

and if n is even, then n^2 has a remainder of 0 when divided by 4 (as evidenced by (2k)^2 = 4k^2)

neither 1 nor 0 are congruent to 3 modulo 4.

[iron bloom]

thank you Lsfhv

[pearl torrent]

Can anyone tell me how to do this?

What I've done was coloring such that if two vertices have an edge between them, they cannot be colored with the same color

But following that I can only color it with 5 blue and 2 red or 5 red and 2 blue, not 3-4 as it is requested here

[stray reef]

but it doesn't say that adjacent vertices should be different colors

[pearl torrent]

Yeah, it's just that's the only coloring I've done in the past

So basically I can do any coloring?

[stray reef]

as-is, it appears so.

[pearl torrent]

I see, thanks!

[coral parcel]

It's correct that the word "coloring" in graph theory often implies that adjacent vertices are to have different colors, though.

[slow jewel]

Any ideas

[jagged junco]

Anyone?
In how many ways can you sit 2n people in a row of 6n+2 seats, such that between every 2 people there will be 2 or 4 empty seats, and the first and last person in the row will sit in the start/end of row.

[obtuse lance]

I would first work out how to place 2n people so they have exactly 2 empty seats between them

then I can think about adding in the 2 extra seats between people as single chunks between the people to make it 4 to fill out the seating arrangement

[pearl torrent]

Can anyone help me verify if this graph has total 6 automorphisms (that preserve the coloring)?

Because it doesn't look okay when I'm trying to compute the cyclic index (and number of inequivalent colorings)

[coral parcel]

I think there are only 4: You can swap 3-4, or swap 6-7, or both, or none.

[pearl torrent]

I’ve also swapped (2, 5)(3, 6)(4, 7) for example

Why isn’t that possible?

[coral parcel]

Swapping 2 and 5 doesn't seem to preserve the colors.

[pearl torrent]

I see, thanks

[unborn pasture]

How many permutations are there with the letters A, B, C, D,E,F,G, H if there is 2 or 3 letters between A and B?
I can't seem to figure this one out. In the solution it says 18*6! = 12960 but i'm not sure how they come up with that solution

This is my solution:
5!(6c2)+4!(6c3) but it's no way near their solution.

This is what i think:
2 letters between A & B:
A ** B c,d,e,f,g,h so we have 6 letters to choose from, and we want to pick 2 of those so 6c2, if we pick two letters we then have A cd B e,f,g,h. If we pick two letters we then have 5! therefor we multiply with 5! and so on

I know that's wrong but that's my reasoning, any help is appreciated 🙂

[gritty pumice]

what does it mean 2 or 3 letters betwee A and B

[unborn pasture]

so like ther must always be 2 or 3 letters between A and B from the letters C, D,E,F,G, H so if 2 letters then: A cd B, A ce B, if 3 letters then A cde B or A cdf B

i think that's what they mean or maybe they mean A cd B efgh with all the remaining letters coming after them

[gritty pumice]

so A cc B also valid?

or only once

[unborn pasture]

no since we only have 1 c

we can only use the ones stated up there

And i have no idea what their solution is about

[gritty pumice]

theres 6! for the case for 2 and 6! for the case for 3 then

if i understood u

[unborn pasture]

are you sure?

The solution is 12960

[gritty pumice]

not really

do we gotta use all letters

[unborn pasture]

yeah since the answer is 12960

[gritty pumice]

what im thinking is

for 2 letters between A and B

A 6 x 5 B 4 x 3 x 2 x 1

numbers represent how many choices we have

[unborn pasture]

yeah

is the same for 3 letters as well

[gritty pumice]

u typed ur question correctly?

[unborn pasture]

let me se

Yeah, that's literally it. how many permutations of the letters ABCDEFGH are there if b) there must be 2 or 3 letters between A and B

[gritty pumice]

can u show a screenshot it

even the first part

part a

[unborn pasture]

yeas

[gritty pumice]

ok

[unborn pasture]

a) "if there are no restrictions"

[gritty pumice]

oh

i c

[unborn pasture]

so like a) 8!

[gritty pumice]

u misundestood the question

[unborn pasture]

😄

[gritty pumice]

we can have xyzw A gf B aswell for example

[unborn pasture]

A and C are A and B in the question that i sent

right right

and we are not counting those in in our 5!(6C2) for ex?

i thought those were included in 5!(6C2)

[gritty pumice]

why r u using choice

we dont care

since permutation

[unborn pasture]

ok

so its 8P4?

let me put some more thoughts into it

[gritty pumice]

ehm

im getting 9*6! as answer

hmmmm

[unborn pasture]

i think i got it

[gritty pumice]

how

[unborn pasture]

4!(6P2)

[gritty pumice]

thats 720?

[unborn pasture]

so 4! because let's say we have AcdB... AcdB has it's own permutations so 4! for those

[gritty pumice]

mmm dont understand you

ohhhhh

yeahhh i got it

[unborn pasture]

Ok so like A ** B have their own permutations no? same with A ''' B

[gritty pumice]

yes

we can do A .. B and B ,,, A

yeah so double 9*6!

[unborn pasture]

But it still dosen't give me the correct answer, it's either wrong or somthing is missing

[gritty pumice]

its 2*9 * 6!

bcz

A 2 B 4

the numbers represent the amount of letters there are

so 2 between A adn B and 4 after

[unborn pasture]

aha

[gritty pumice]

then we have 1 A 2 B 3

2 A 2 B 2

...

4 A 2 B 0

[unborn pasture]

yeah yeah i'm with you

[gritty pumice]

thats 5*6! so far

then for 3 letters case

[unborn pasture]

A 3 B 3
1 A 3 B 2
...

yeah shiiiiet

[gritty pumice]

letters

yeah

so count then for 9*6!

then A x B and B x A are different

[unborn pasture]

it makes sense, but i need to let it sink in rn

[gritty pumice]

double it

[unborn pasture]

lol

[gritty pumice]

yeah

so yeah matches ur answer

[unborn pasture]

yeah i'm withchu, tyvm

[gritty pumice]

yw

u dont need that permutation function

[unborn pasture]

yeah i was mixing it

i tried everything i could but i couldn't figure it out

so like yeah lol

[gritty pumice]

👍

[shut peak]

guys quick question

It asked me to get the inverse of the function

but what does it mean by ( x>= 3)

?

I did this

[coral parcel]

It says the function f is only defined for arguments that are at least 3.

Which is a good thing. because if, for example, f(1) and f(5) were both defined, the function couldn't have an inverse. (Can you see why?)

[indigo olive]

Anyone knows to write algorithm by using pseudocode

I just need some tips

[stray reef]

@indigo olive literally just check the pairs one by one and return false if you ever find a zero?

there is nothing you can do here except for brute force

[indigo olive]

What’s brute force

[stray reef]

check the pairs one by one and return false if you ever find a zero

[indigo olive]

What does that mean

[stray reef]

is it not clear

when i say pairs i mean pairs of vertices of course

if you want to write code for it, you would do a double for-loop in which you loop over i ∈ S and then loop over j ∈ S and if j ≠ i look at the value of M_ij

[indigo olive]

In a pseudocode manner

Like

Start

Statement 1

Statement 2

till

End

@stray reef

Am stuck here idk what else to write

[stray reef]

what's Size and why are you initializing it to 0?

[indigo olive]

Oh

I mean to write S

Set S

[stray reef]

...

okay, you're kind of overcomplicating it

[indigo olive]

Sooo can u give a brief idea

[stray reef]

and also not using proper indentation for your nested loops

[indigo olive]

yep sorry

[stray reef]

probably easier to just write it myself

[indigo olive]

Yes

[stray reef]

otherwise you'll just struggle forever

For i ∈ S:
    For j ∈ S:
        If j ≠ i and M_ij = 0:
            return False
return True

[indigo olive]

Wtf that’s fast

Bru

That simple

[stray reef]

yes

it really is that simple

there's no ingenuity to be had here

[indigo olive]

i make things complicated f

For that algorithm what would be the time function and big O complexity? @stray reef

[stray reef]

what do you think its complexity is?

it's a double loop over S

[indigo olive]

2n squared + 2?

[stray reef]

O(|S|^2)

[indigo olive]

Since for is the iteration of n

[stray reef]

or O(n^2) if you want

[indigo olive]

Yup

[indigo olive]

So 2n^2 + 2? Is valid right

[stray reef]

what do you mean by "valid"

2n^2 + 2 is a valid mathematical expression, and so is log(n) + e^(3sin(2n)) - 55

[indigo olive]

cos another question asking if I found the algorithm

It’s asking the time function

[stray reef]

do you really want the exact number of operations this algorithm takes?

[indigo olive]

yes

[stray reef]

jeez wtf

[indigo olive]

am new to this

And the question like this

wtf

[stray reef]

depends on what we count as an operation i guess

if we want to be scrupulous my algorithm can take between 3 and 3n^2+1 operations

[indigo olive]

I see I see

[stray reef]

(and obviously where exactly it ends up depends on the exact input being passed into it, since it stops the moment it sees a zero)

finding the EXACT time taken by an algorithm is most often a worthless pursuit

[indigo olive]

lmaooo

Is there a point of inistialising in that algorithm? @stray reef

[stray reef]

what do you want to initialize

[indigo olive]

Initialise M to be a matrix of size n x n whose entries are all 0

[stray reef]

what

M is your input

[indigo olive]

O

[stray reef]

plus do you really need to keep track of anything here

you don't

[indigo olive]

Yea I need to

[stray reef]

no

no you don't

[indigo olive]

What

[stray reef]

you just scan through the relevant entries of your matrix

if you ever see a zero, then you STOP and return FALSE.

[indigo olive]

that makes sense

[stray reef]

if you go all the way through every entry without ever seeing a zero,

then it means all of those entries you scanned were 1s

and so you should return TRUE

[indigo olive]

Here’s an example

S ={0,2,3}, need to verify if three vertices are pairwise adjacent

[stray reef]

ok sure

you check M_02, M_03 and M_23

if one of these is a zero return false

otherwise return true

[indigo olive]

“To do so, you need to check similar thing for all pair i,j in S”

[stray reef]

i do not understand what part of this isn't crystal clear

WAS THIS NOT WHAT I'VE BEEN TALKING ABOUT FOR THE PAST 20 MINUTES

[indigo olive]

LOL

yes

[stray reef]

HAVE YOU NOT BEEN PAYING ANY ATTENTION TO WHAT I'VE BEEN SAYING

[indigo olive]

Now I get it

Also a vertices of 6 with edge 13 is not a planar graph right? @stray reef

[stray reef]

what?

[indigo olive]

Another qs

[stray reef]

i don't understand what "a vertices of 6 with edge 13" means

[indigo olive]

Oh

[stray reef]

did you mean "a graph with six vertices and thirteen edges"?

[indigo olive]

Yes

[stray reef]

how did you conclude such a graph cannot be planar?

[indigo olive]

Graph is non planar because adding some extra vertices or edges into an existing edge.

The resulting graph is still non-planar

[stray reef]

??

[indigo olive]

that’s my conclusion

[stray reef]

Graph is non planar because adding some extra vertices or edges into an existing edge.
this is nonsense

[indigo olive]

What

[stray reef]

i'm not even going to try and dissect it

what you said makes zero sense, period

[indigo olive]

Oh

[stray reef]

it's just some words you've put together with no rhyme or reason to it

[indigo olive]

So what’s the proper way of concluding it

[stray reef]

...i expected you to say something about euler's characteristic formula.

maybe something about how if the graph were planar, then drawing it on the plane would divide it into ___ regions, and then something about the number of edges adjacent to every region...

but to be honest i do not have high hopes

[indigo olive]

Here an example can u check this one hold up

@stray reef

[stray reef]

great, in this example you have an actual graph to work with

while in the problem you presented me with, all you have are the vertex and edge counts

[indigo olive]

Yea

[stray reef]

you will not get a K_3,3 or K_5 minor out of that

[indigo olive]

So it’s easier having an actual graph

[stray reef]

different problems require different tactics.

[indigo olive]

u have enlighten me

[stray reef]

have i now

[stray reef]

that's really sad

i would've hoped it would have occurred to you

[indigo olive]

Alright another q

Decide if the following graphs are planar

@stray reef

My answer is no

[stray reef]

and do you have proof?

[indigo olive]

Um

Nope

[stray reef]

okay then you don't have an answer

[indigo olive]

what

I need to explain why they aren’t?

[stray reef]

you just said "my answer is no" and then admitted you have nothing to back it up

OF COURSE YOU NEED TO EXPLAIN

did you really think you didn't need to explain

[indigo olive]

I used a formula 3(n.vertice) -6

[stray reef]

that's not a formula, that's an expression.

[indigo olive]

Oh

YouTube

[stray reef]

and until you say what it means, it won't mean anything.

so what if you multiplied the number of vertices by 3 and then subtracted 6 from the result

can you say what the result should mean, or is it just a computation that you memorized without purpose?

[indigo olive]

If the result is over the number of edges

It means it’s not a planar

say 3(6)-6 = 12

But the edges is 13

[stray reef]

"the result is over the number of edges"

you said that if $3|V| - 6 > |E|$ then the graph isn't planar. do i understand you correctly?

[vital dew]

Ann

[indigo olive]

Yes that

[stray reef]

but 12 isn't greater than 13

so according to you, the graph might be planar.

[indigo olive]

Idk if YouTube teaching me correctly

[stray reef]

im not gonna sugarcoat it: you are really bad at communication.

[indigo olive]

Iol

lmao

[stray reef]

all you've been doing so far is regurgitating things you've watched on youtube without any semblance of understanding.

[indigo olive]

ahhh

[stray reef]

it's exhausting

[indigo olive]

So back to the topic . What kind of proof do I need

To prove it isn’t planar

[stray reef]

i can't tell you that without just giving away the entire proof i have in mind

so i will not bother

[indigo olive]

What if I add extra vertices

[stray reef]

....

[indigo olive]

according to kuratowskis theorem

A non planar is either K5

Or k3,3

[stray reef]

no

you're missing like half the words

[indigo olive]

What

[stray reef]

and what you've just said amounts to "K_3,3 and K_5 are the only nonplanar graphs in existence"

[indigo olive]

Let me write the whole thing then lol

A graph is non-planar if and only if it can be obtained from either K5 or k3,3 by adding some (or no) vertices and edges and inserting some (or no) new vertices into existing edges.

[stray reef]

great

[indigo olive]

[stray reef]

and this theorem will be of NO use for you here.

[indigo olive]

WHAT

Oh yeah

[stray reef]

yes, imagine! if you know nothing about the structure of your graph, then a theorem that relies upon said structure cannot be applied!

or at least, if it can be applied, it's going to be way more effort than needed.

[indigo olive]

Isn’t a planar graph is one for which we can give a planar graph drawing

However, these graphs aren’t capable of doing so

[stray reef]

how do you know these graphs cannot be drawn without self-intersection?

just because these particular drawings have intersecting edges does not by itself mean the graphs are nonplanar

otherwise even K_4 would have been declared non-planar if you drew it a certain way

[indigo olive]

ah this is troublesome

[indigo olive]

Becaus it can be drawn without any edges crossing?

Is eulers formula can work here

[stray reef]

....

god

[indigo olive]

[stray reef]

it's like a game of telephone

first you say these graphs are not planar

now you say they are

and then you bring up euler's formula, as if i had not mentioned it before

[indigo olive]

because I have no proof

[stray reef]

and you produce more bullshit out of your mouth

[indigo olive]

That’s the thing

[stray reef]

well it certainly is possible to do something with euler's formula

but with your apparent ineptitude maybe it will look impossible for you

[indigo olive]

[stray reef]

getting you to remember the statement of kuratowski's theorem was a struggle, and even then you probably just copied it from somewhere

[indigo olive]

From my notes yes

Is this reasonable? @stray reef

[stray reef]

your value of f is wrong

it's 9, not 11

[indigo olive]

Isn’t -9

Then if we add 11 we get 2?

[stray reef]

??

6 - 13 + 11 is not 2

i don't know where -9 is coming from either

[indigo olive]

Oh wait u right

Iol

Typo

So is that a good proof tho?

[stray reef]

i guess i can't expect you to make anything better

[indigo olive]

Lmao

tyty

Am becoming more math enthusiast

[weary tiger]

i was reading Hopcroft's automata text, and didnt understand this part where they work on delcap(q,a), i dont understand how is delcap(q,epsilon) = q ?

a here is a single input or string ?

[stray reef]

and input symbols a

anyway

[weary tiger]

yea

[stray reef]

$\hat\delta(q, \ep) = q$ means that a FA that starts in state $q$ and receives nothing as input stays in state $q$. which should be obvious.

[vital dew]

Ann

[weary tiger]

ok

they mentioned epsilon for the first time so I got a little confused

thank you for clarifying

[stray reef]

epsilon is the empty string

[weary tiger]

oh, makes sense

[stray reef]

hence why i called it "nothing"

[main cargo]

Im a bit confused as to why this is the case, shouldn't it be R superscript +?

,rotate

[stray reef]

it should be [0, +∞)

also whoever wrote this has shit handwriting

[main cargo]

Alright yes, that what I though

That's my handwriting lmao, but thanks

[scenic birch]

This would be 1/366^2 * (58 C 2) right ?

[stray reef]

no, that doesn't sound right

you have not accounted for the other 56 students being born on days OTHER than jan 1

which will incur a multiplier of (365/366)^58

[scenic birch]

yeah that makes sense

thanks

[willow fog]

is this a good definition of the maximum element of a set?
$\ \max{S} = {x \in S : x>y \ \forall \ y \in S}$

[vital dew]

the true embodiment of a sully

[gritty pumice]

what happens when theres multiple max

the set is empty

[willow fog]

so should I use $\geq$ instead of >

[vital dew]

the true embodiment of a sully

[gritty pumice]

yessir

[willow fog]

okay ty

[unborn pasture]

A Directed graph with nodes n >1 has a topological ordering if there is a node with indeg(V) = 0, is this true or false?

Let’s say we have a simple directed graph with 2 nodes, then there is a topological ordering, right?

A•—>——• B
Let’s say this is our graph, A has a indeg of 0

[gritty pumice]

yes

[unborn pasture]

oh my

Thanks!

Also if we talk about the same graph with nodes n > 1, if there is a walk from u to v then it means it's a cycle, this one is false right?

Does that make sense?

[gritty pumice]

which graph are we talking about

[unborn pasture]

yeah so like if there is two nodes u and v and there is a walk from u to v then our graph must have a cycle

same graph as before with 2 nodes

A•—>——• B

I say it's false since we have defined our from n > 1, for it to be a cycle n must be >= 3. So by showing that we can make a walk from u to v in a graph with 2 nodes we prove that our statement is false

[gritty pumice]

is that a graph with vertex A and B and a just a single edge from A to B?

[unborn pasture]

yes exactly

And that's why i think the statement is false, i'm not so good with graphs tho

[gritty pumice]

there cant be a cycle with a single edge

[unborn pasture]

ok niceee then

tyvm 😄

[gritty pumice]

👍

[weary tiger]

where did they get the double ~~ from?

I'm little confused

it says law of double negation

but there wasn't double negation in first place

[past widget]

Isn't the law t = not not t so you can replace that?

[stray reef]

@weary tiger they introduced a double negation

[final cliff]

Are you trying to define max{S} to be the maximum elt of S? Because max{S} is not always an element of S here. For example, if S={1,2,3} then max{S}={3} which is not an element of S.

[willow fog]

but 3 is an element of {1,2,3}

oh

nono

max{S} doesn't have to be an element of S

[final cliff]

The issue is max{S} is an element of the powerset of S rather than of S, but you want max{S} to be an element of S instead.

[willow fog]

I do?

[final cliff]

Well, if you say m is the maximum elt of A wrt the ordering >, you'd like to be able to say things like: if n is in A then m>n right?

But > would be defined for elts of A, not necessarily for elts of P(A).

So if you use your max as it is what you're doing might not make sense.

[willow fog]

oh

[final cliff]

For ex with A={1,2,3} we had maxA={3}, but then what would {3}>2 mean?

[willow fog]

but doesn't this idea exist already

the maximum element of a set?

[final cliff]

Yes.

It only really makes sense if a single unique max element exists though iirc

You could have two distinct elements in a partial ordering that are greater than all the others, but are not comparable.

https://en.m.wikipedia.org/wiki/Partially_ordered_set

Under "derived notions" talks about those kinds of objects and junk.

[willow fog]

oh okay

ty

I didn't realize it was so weird

[final cliff]

When you have a property that characterizes an object uniquely you can just name the object with some symbol or notation in terms of that property.

[willow fog]

with functions it's an easy thing to define

but ig not w sets

[final cliff]

There's probably something subtle going on.

For naming and sets.

Idk, like, the empty set is a good ex.

We define it as a set having no members.

It turns out this property can be used to show the empty set is unique.

So we're justified in using the empty set symbol to denote the empty set because of this.

Like, we can't accidentally have the empty set symbol refer to two distinct sets I mean.

[willow fog]

true

[final cliff]

If you look at fig 6 under extrema in that wiki you'll see an ex where there is no max elt wrt subset ordering.

So in that poset, if you referred to something as "the maximum", you'd be saying something ambiguous at best.

https://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Hasse_diagram_of_powerset_of_3_no_greatest_or_least.svg/660px-Hasse_diagram_of_powerset_of_3_no_greatest_or_least.svg.png

[willow fog]

oh oof

ty for clarifying :)

[weary tiger]

Can planar graphs be multidimensional?

(Asking for a friend)

[obtuse lance]

what do you mean by multidimensional

if it's a planar graph it can be embedded in R^2, which itself can be embedded in R^n for n>2

[weary tiger]

So I think I understand everything except why in the last image a=1. Only thing I don’t get

[final cliff]

This theorem holds for any real numbers a,b where a>0.

So in the case where a=1, then a>0 so the theorem applies.

[weary tiger]

yeah that makes sense but it seems like a=1 came out of nowhere

idk why the 1 from the previous equation belongs there

[final cliff]

Yeah, they're just picking it I suppose, and them picking it is totally justified by the thm.

This is just density of Q in R I think?

[weary tiger]

lol

[final cliff]

So there's probably some nice intuition for it. 🤔

[indigo olive]

In terms of big O complexity, which one is bigger is it n^2 or n^2log2

[sour arrow]

Both the same. Constant multiples don't matter.

[final cliff]

Maybe something like this helps? https://math.stackexchange.com/questions/830836/question-about-the-density-of-q-in-r

I think the proof they're talking about might be diff from urs tho

Ah wait nvm looks the same

The second reply to that thread has a pretty nice way of looking at it

[jaunty ruin]

hey anyone knows what dead state method is ?

i know how to convert by creating a table but have no idea what it means by dead state method

[weary tiger]

what does this sentence mean

?

[olive wren]

It means that if you can draw the graph such that the edges (the lines that connects two nodes (points)) dont intersect (cross each other)

[weary tiger]

Hmm thanks

[jagged junco]

Anyone? (Graph theory)
Given: G=(V,E). There's one singular path between every 2 vertices (a path is a trail in which all vertices (and therefore also all edges) are distinct).
Prove: G is a tree.

---

We know because of the given that the graph is connected.
So to complete that T is a tree, we need another condition like |E|=|V|-1 which I don't know how to prove here
or to show in some way that it contains no cycles? how to show this?

[olive wren]

If there's a cycle that means between two nodes on the cycle, there are two paths

So there arent any cycles

[jagged junco]

yes but I can't say it simply like that, I understand that intuitively like you said

but I don't know how to formally make it

[olive wren]

Oh okay

So how about

Suppose there exists a cycle

You can write it like so:
[ v_1\to v_2\to\cdots\to v_n ]
Where $v_1=v_n$
So one path from $v_1$ to $v_2$ is $v_1\to v_2$, but another is $v_1\to v_{n-1}\to\cdots\to v_2$

[jagged junco]

yes

[vital dew]

Slurp

[jagged junco]

aaha you're right

so we found 2 paths between two vertices, in contradiction to having only 1 singular

[olive wren]

mmhmm

Exactly

You might want to explain why the two paths are distinct

But its pretty simple

[jagged junco]

yes

sounds good

thank you for your help 🙂

[olive wren]

no problem!

[jagged junco]

Any clue?
Given: G=(V,E) undirected graph. The number of vertices is n and n is odd (n ≥ 3). G has Eulerian cycle.
Prove: G has 3 vertices with exact same degree

--
We know from Eulerian cycle that every vertex degree is even. idk how it helps

[hardy viper]

@jagged junco you should find how many possibilities there are for the degree

[jagged junco]

so I know that 2 is the minimal degree and that the maximum is n-1 because n is odd

how do I continue?

[hardy viper]

write out all the possibilities and count them

[jagged junco]

I'm having hard time counting the possibilities because there isn't much information, or maybe I'm missing something (probably)
I know that every vertex has degree with one of those {2,4,6, 8, ..., n-1}

[hardy viper]

yea, I'll give you 2 ways of counting them

you can divide it by 2 since they're all even for {1,2,3,4,...(n-1)/2} and that's a basic list so it's (n-1)/2 total

or you can write n=2m+1 and the list is {2,4,6,...2m} for m total

so there's 2m+1 vertices and only m choices for degree

[jagged junco]

oh wow

so from pigeonhole principle we can say that we have 2 vertices with same degree

[hardy viper]

you got it

well 3 with same

[jagged junco]

(2m+1)/m = 3?

[hardy viper]

since worst case scenario is each degree having 2 and there's 1 left over to make a 3

(2m+1)/m = 2.1 basically

it's slightly over 2 so there has to be a >=3 somewhere to bring up the average

[jagged junco]

aha I get what you mean

it all makes sense to me now but I'm mad at myself that I couldn't come up with this haha

thank you very much !

[storm tinsel]

are there any youtube channels you guys would recommend that tackles discrete math really well

[weary tiger]

can someone plz clarify why the set of real numbers and irrational numbers is uncountable but rational numbers arent. rational numbers and irrational numbers both have the same cardinality as the set of positive natural numbers meaning both sets should be countably infinite.

[weary tiger]

I don't even fucking know bro

Also

What do you mean R^2?

I've seen that before, isn't that like a tuple?

Soe shit like that idk

[weary tiger]

yea R^2 is the cartesian product of R and R returning the set of all 2 argument tuples (x, y) in a plane

Erm, what? What do you mean Cartesian product?

so given two sets, A and B, the cartesian product would be the combination of all elements from each set. so for example: A = {1,2,3} and B = {4,5,6}. The cartesian product AxB would be {(1,4),(1,5),(1,6),(2,4), etc...}

so R^2 is the set of all points (x, y) on a real 2D plane

So like the mapped points?

On a cartesian plane?

yes

oh shit I'm stupid

how did I not know this

okay

so

let's say it's a R^3

This would be multi-dimensional?

yep

okok thanks

R^2 is also multi-dimensional fyi

pretty sure multi means more than one

I think in relation to a regular set however

could be

idk

[haughty garden]

The set of real numbers is uncountable since it's not even countable in the interval [0, 1). You can show this using Cantor's diagonal argument. Suppose you have some enumerated infinite list of real numbers in the interval [0, 1). Then consider the diagonal elements of each of these numbers. If you change it slightly, then you can form a new number that does not appear on the list because at some index, the numbers don't match. This is another number in the interval [0, 1) but it doesn't appear on your list.

Note that the set of real numbers is the countable union of rational numbers and irrational numbers. So at least one of the rationals or irrationals must be uncountable; otherwise, the set of real numbers is countable which leads to a contradiction (this is a result from the fact that the countable union of countable sets is countable). But the set of rational numbers is countable which means that the set of irrational numbers is uncountable

To show that the set of rational numbers is countable, you can either find an explicit bijection from Q to N or invoke Schroder-Bernstein theorem and find two injections, one from Q to N and one from N to Q

[indigo olive]

Did u do any finite state machine before? @haughty garden

[pearl lodge]

I have a question regarding a function from a set A to B, where the function is surjective. The problem is to prove if A is countable B is also countable. My logic is that since the function is onto each element of B must be mapped to at least one element of A. Since we can count A values we can count B values. Does this seem like a reasonable argument? I am doing some self study for basic discrete mathematics but am bad at proofs and had a bit of trouble understanding the implications of cardinality and surjective/injective functions on sets

[olive wren]

I’m not entirely sure how rigorous that is. A better approach I think is to define an injective function from B to A by using the axiom of choice

Essentially given an element x in B, g(x) will be an element where f(g(x))=x. Since there must exists at least one element like this, you can choose one

[coral parcel]

Why do you think the irrational numbers have the same cardinality as the set of positive naturals?
That is false (as well-known proofs show), but the reason you would think they do deserves examination. You might need to unlearn some intuition that doesn't work for infinite sets.

[elder berry]

Quick question: To show injectivity (f(a) = f(b) -> a = b for all a, b), a and b don't have to be distinct right?

Rather, it is totally fine if we have a function that has only one element, say f(x1) = y1 and it is an injection, correct? (Domain of f is {x1})

[coral parcel]

Correct, a and b don't have to be distinct.

In fact, when they are not distinct you're immediately happy because the right-hand side of the -> is true.

[elder berry]

Yup, and the contrapositive also makes sense, but just wanted to confirm. Thank you!

[coral parcel]

"Since we can count A values we can count B values" doesn't sound rigorous to me. It might actually describe an intuition that turns out to be valid, but as it stands, it sounds a lot like just stating the thing you have to prove in different words and calling that a known fact.
A good proof here ought to describe in detail how to satisfy the definition of "countable" for B if you know it is satisfied for A. The details will depend on what your definition of "countable" is. There are several equivalent possibilities, and you need to connect to the particular one your class uses.

[pearl lodge]

That hits the problem I tend to have with proofs. I came from a physics background looking at this, where analogies are used for almost any “proof” until you get to a very high level of understanding. I’ll keep working through it looking some definitions as a guide. I also wrote it at 2 in the morning and forgot to include that A and B are both infinite sets, with A being countable

[coral parcel]

If A and B being infinite sets is an explicit assumption, then that changes my guesses at what your definitions probably are.

(Unfortunately there are two different meanings of "countable", favored by different authors. Everyone agrees that a set of the same cardinality as the natural numbers is "countable", but there is a disagreement whether the word also ought to encompass finite sets).

Analogies and appeals to intuition are rarely accepted in mathematical proofs. This can feel rather stuck-up, but the underlying reason is that a proof is not only convincing ourselves the conclusion is true, but also for convincing ourselves that we have listed all the assumptions that force it to be true. The latter part is important because it is what tells us when we can reuse the reasoning in a different setting that is formally similar.

[plucky slate]

Hello stats nerds/geniuses
Anyone able to help me with this Applications of Probability question?
I'm struggling to answer...well either parts really. Like part A I've got an answer but I'm not particularly confident with it.
Anyone able to help me out with this?

[pearl lodge]

No worries, I reframed the proof I had in mind to fit within one similar to one in my text, which had a few (what I assume are good) examples of something similar for a set. Thanks for your help

[pearl lodge]

I’m not quite understanding the line 9 in a row count as 3. Would 7 then be 21 successful shots?

[twilit cloud]

Not sure if this counts as "discrete math" but that's what the course is called

Right now we're learning about trees and spanning trees

I forgot the formula I'm supposed to use for this assignment (image 3), so I looked it up, and apparently the number of spanning trees in a graph is v^(v-2)

[plucky slate]

Hell...I'm confused on that. Either 1 streak is 3 consecutive shots and therefore 7 shots is 2.3333... shots...it's...weird

[twilit cloud]

However, in the notes (images 1 and 2), it seems she's teaching that the number of spanning trees in a graph is... the number of vertices in each circuit in the graph, multiplied by each other in the first example (image 1)

And in the second example (image 2) shes doing something... completely different

I have no idea what to do

[gritty pumice]

know the definiton of a spanning tree?

[twilit cloud]

Yes

[gritty pumice]

some edges are must haves right

[twilit cloud]

It's a tree that consists of a set of edges that touch every vertice once

Yes

[gritty pumice]

sorry i mean

BC and AC and AB **

we cant have those at the same time in a spanning tree

[coral parcel]

In the second example, the task stated is to draw all the spanning trees, not just compute how many there are.

[gritty pumice]

i mean just the first part

and then look at the middle part

and just count every scenario

thats how i would do it

maybe an algorithm exists for this but im not aware

[coral parcel]

So the red crossings-out in image 2 is an example of how to make one of those spanning trees, not part of a counting algorithm.

[twilit cloud]

Oh

OH wait