discrete-math

[wide vine]

took a look at it and figured out the notation

only had to skip to the next unit to find it -_-

😡

are they saying "NOT non-increasing"?

here is their defintion btw

A sequence is non-increasing if for every two consecutive indices, k and k + 1, in the domain, ak ≥ ak+1.

[pale epoch]

its not non-increasing, yes

[tidal tulip]

hard to type tex on mobile

do it later

[pale epoch]

this is correct btw, as in its all the correct words in the correct order

[tidal tulip]

thanks!

i was trying to copy that over

(don’t have internet connection on laptop so was hard to do)

[pale epoch]

you use the same variable x for two different things

[tidal tulip]

ah

ty

i’ll work on it

[severe swan]

Can someone explain this to me?

Identify the prime factorization of 10!

10! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 =3,638,800

The prime factors are 1, 3, 5, 7

The prime factorization is 2^8 * 3^4 * 5^2 * 7

Can someone explain why this is the correct answer?

[obtuse lance]

1 isn't a prime

[true venture]

Every prime less than 10 will be a factor since it is a factorial

[obtuse lance]

maybe you meant to put 2 there cause 2 is prime

[tidal tulip]

@pale epoch Let $x \in f^{-1}(f(A))$. Then $f(x) \in f(A)$. We want to show $x \in A$.
We know $f(x) \in f(A)$. Let y:=f(x), so there exist an $m \in A$ such that $f(m)=y$. Note that f(m)=f(x), and since $f$ is injective,m=x, and so $x$ is in $A$. Thus $f^{-1}(f(A)) \subseteq A$.

[vital dew]

strings

[pale epoch]

yes, this is correct

[tidal tulip]

ty for helping me understand this

really appreciate it

[pale epoch]

[tidal tulip]

how does this sound for the other one @pale epoch

let $x \in A$, then $x \in f^{-1}(f(A))$ since $f^{-1}(f(A))={x \in X | f(x) \in f(A)}$ by definition. This is because:

1. Since $A \subseteq X$, we know $x \in A$.
2. since $x \in A$ we know $y=f(x) \in f(A)$ by definition of f(A).
   therefore $A \subseteq f^{-1}(f(A))$

[vital dew]

strings

[shell lagoon]

how do you show that every outerplanar graph is 3-colorable?

[coral parcel]

By strong induction of the number of vertices. The interesting case is the one where the graph has an interior edge. Pick one such edge. The picked edge together with the part of the graph on one side of it forms a smaller outerplanar graph; so does the picked edge together with the part of the graph on the other side of it. Recursively 3-color both of these smaller graphs.

[shell lagoon]

oop thanks yeah I just got it hahah

can you help me with another thing please?

I'm not sure how to count the perfect matchings in the trees

is it something to do with edge coloring?

[coral parcel]

Hint: the answer is always either 0 or 1.

Further hint: start with the leaves.

[shell lagoon]

oh shit I must be misunderstanding perfect matchings then

[coral parcel]

Hmm, what is the definition of "perfect matching" you're working with?

[shell lagoon]

oh I see, you need to cover all the vertices huh

[coral parcel]

Yes, that's what makes it "perfect".

[shell lagoon]

true

🥲

sorry im weak at this

so is the choice of 1 then covering the whole tree?

no that doesn't make sense

[coral parcel]

I'm saying that a tree either has no perfect matching at all, or there is only one way to get one.

[shell lagoon]

ooh

[coral parcel]

(The situation is more interesting for graphs that are not trees).

[shell lagoon]

what is the one way to get a perfect matching? like if the graph has an even number of nodes or?

or is there an algorithm

[coral parcel]

"One way" was perhaps not the best wording. I didn't mean one method, just there can't be two different perfect matchings.

[shell lagoon]

hm

but I'm looking at this thing saying that a cubical graph has nine distinct perfect matchings?

or are they really the same

[coral parcel]

A cubical graph cannot be a tree.

[shell lagoon]

oh okay this is for trees

sorry

[coral parcel]

"Perfect matching" has the same definition for all graphs. The thing that is for trees is my claim that the number of perfect matchings is either 0 or 1.

[shell lagoon]

ok then this must have to do with degrees

[coral parcel]

Did you see the "further hint"?

[shell lagoon]

yeah I was thinking about it

[coral parcel]

The exercise doesn't ask you to come up with a general criterion, just to find out what the answers are for those two particular graphs.

[shell lagoon]

true

[coral parcel]

I think it is much easier to find those concrete answers first, and then (if you're still curious) try to generalize your reasoning to cover other trees.

[shell lagoon]

yeah you're right I'm being distracted

it just doesn't seem possible to cover all the vertices without having some edges sharing vertices

[coral parcel]

That means that the number of perfect matchings is 0.

[shell lagoon]

ok nice

yeah and the leaves make it obvious because

well you have three edges coming out of that vertex onto another 3 seperate vertices lmao

idk how to formally say it without just pointing

you're just bound to have collisions

I guess?

[coral parcel]

Give the edges and vertices names and say something like: The only way to cover v1 is to include e2, and the only way to cover v3 is to include e4, but e2 and e4 cannot be in a matching at the same time because they both end at v5.

[shell lagoon]

true

[lime plinth]

Help me understand this proof. Where do q^(n^2) and 1/((q;q)_n)^2 come from exactly and why can you just multiply them?
I suppose the author uses the symbolic method but not sure what are the atoms.

[lime plinth]

it's called a claw btw

[shell lagoon]

oh sick

lol

[shell lagoon]

thanks a bunch!

[desert edge]

Just wanna see if I got this right. Does a reflexive relation only occur if every point has a loop?

Or can I say its reflexive, if xRy and zRz?

What am trying to understand is, for a graph to have certain relations, does every node need to have those properties?

if xRy and yRz, and yRz, then xRz. But if yRx, do we still have a transitive relation? I know I asked more than one question, sry about that

[gritty crescent]

This is better suited to #prealg-and-algebra .

[gritty crescent]

If you want to draw a graph representing a relation, then yes, reflexivity translates to "every vertex has a loop", symmetry is natural to undirected graphs, but for directed graphs I'd expect "if there is an edge from vertex a to vertex b, then there is an edge from vertex b to vertex a", while transitivity corresponds to "if there is an edge joining a and b, and an edge joining b and c, then there is an edge joining a and c".

[stray reef]

@flat lichen if you have another doubt that is better posted here then post it

[desert edge]

Ok great. Does transitivity still occur if theres symmetry between two nodes?
xRy, yRx, yRz, xRz
Theres transitive relation in two ways. It still counts, right?

z is not transitive but x and y should be

[gritty crescent]

Transitivity is a property of the relation, not the individual elements.

R is transitive only when aRb and bRc implies aRc.

[desert edge]

ohh I see

that actually clarified many things. I was looking at the elements

[gritty crescent]

If you know that R is transitive here, you can conclude that xRx because xRy and yRx.

[desert edge]

Im dumb

😄 Thanks for pointing it out

[gritty crescent]

[spring surge]

{ Element | Element is a permutation of {1,2,3,4} }.

Is there an elegant way to write it in formal way?

[unreal stump]

S_4

[cerulean wind]

{f : {1,2,3,4} —> {1,2,3,4} | f is a bijection}

[desert edge]

Can someone help me understand how he got 5a_k-1 - 6a_k-2 in second picture from first?

Hes doing it from the assumption of n < k but I dont see why k-1 in first and k-2 in second term

[slate onyx]

A=2 -1 3 2 7 5 x B=0 -4 3 1 4 6 7 2 9 -3

[proven silo]

-2 on all indicies?

You have an expression on a_{n+2} so shift it by 2

[desert edge]

Can he choose any number k thats greater than n, and the result will be the same?

i dont have the intuition to see why -2

[spring surge]

thanks!

[proven silo]

Say n=6 then a_{6+2}=5a_{6+1}-6a_6. But if n=4 we have a_{4+2}= 5a_{4+1}-6a_4

Which is exactly the same as the formula written down for a_k for k=6

[slate onyx]

<@&286206848099549185>

A=2 -1 3 2 7 5 x B=0 -4 3 1 4 6 7 2 9 -3

[desert edge]

I think I see my issue here

I forgot k > n meant n = k - 1

I kept thinking of it as n = k + 1

[proven silo]

k>n does not mean either of those

[desert edge]

no but it does help with understanding why the value of n got lower

[proven silo]

What? I could also write down formula for a_{k+100} if I wanted

[desert edge]

for k to be greater than n + 1, k - 2 does the trick

i was trying to figure out where that k - 2 came from

[proven silo]

Yes they do it to use inductive hypothesis but sounded like you didn’t understand why the two things were the same

That has nothing to do with k greater than…

[proven silo]

.

[desert edge]

Im most likely missing some understanding. This is all new to me

[proven silo]

Given a number k you have the formula for k+2

So call m=k+2 now you have a formula for a number m

Is just all they did

[desert edge]

so k - 2 = n + 1 and k - 1 = n?

[proven silo]

.

If m=k+2 then k=m-2, plug that in and you get a_{m-2+1} and a_{m-2}

I could also do this with m=k+103918182 or whatever it doesn’t matter, this is still true (as long as we don’t go below a_0)

[desert edge]

why is this so hard for me to understand

it makes alot of sense but something doesnt click

m is just k with an added 2 and k is m when you remove that 2. the number doesnt matter

i actually got it

i somehow didnt notice a_n+2 .. so a_n is substracting 2 from 5a_n+1 and 6a_n......

[proven silo]

Yes

[desert edge]

D:

thanks for the patience

[shell lagoon]

anyone know how to show this? I know I need to use hall's theorem

I guess you must show N(S) geq S

but isn't it obvious..

I guess I can try contradiction

[stray reef]

may be possible to prove there exists a hamiltonian cycle in G

actually no hold on that was bullshit

[shell lagoon]

hahah

[unreal stump]

<@&268886789983436800>

[pale epoch]

🤨

please dont advertise @whole verge

got bonked

[shell lagoon]

can anyone explain this?

I think I understand the first case

but I don't understand why the neighbourhood of W would be equal to n in the second case

couldn't W just be one vertex with degree bigger than n/2 but not equal to n? therefore its neighbourhood is not equal to n

[vital dew]

@dapper rose

[dapper rose]

@shell lagoon

[shell lagoon]

yikes, bad oversight

thanks ill rethink it

wait no

wait let me show you what i think is a counterexample

[shell lagoon]

what about this?

[dapper rose]

bottom right has degree 1

[shell lagoon]

ah shit you're right

lol

welp, thanks

[silent hinge]

hello friends

we know 43 is a prime number, so I decided to use Fermat's technique. And this algorithm consists of breaking down exponent, taking what's left, and then using fast exponentiation algorithm. I did all those steps but for some reason im gettign the wrong answer

can anyone verify where im failing

[silent hinge]

take a look at my question whenever you get a chance, thanks in advance

[proven silo]

6^40=6 mod 43. 6^2=36 mod 43

6*36=1 mod 43

[coral parcel]

This latest question seems to have nothing to do with the conversation you're replying to.

[silent hinge]

sorry i do not know how to tag users on discord

[coral parcel]

I would prefer if you don't attempt to ping me in any manner if you're not responding to something I've said.

[silent hinge]

roger that

[silent hinge]

i see what you doing. thanks

[true venture]

Related to a question yesterday, asking : given a set of random positive integers find the permutation that has the maximum sum of differences between each number. Are there any theorems involving this sort of thing?

[heavy tinsel]

Having a degree 4 vertex means that we need at least four leaves (for a tree). Is this True?

[weary tiger]

Soo I got both of these questions correct by applying logical thinking on what to do. Though I am a little confused.

The first question is no unique digits, the second one has the constaint unique digits. What technique/rule differentiates the two questions?

The first question I applied 2 * 10^4 while the second question I applied 2 * 10 * 9 * 8 * 7

Like 1 uses unique elements from the set the other disregards that. Yet both of them state that different arrangements are unique answers.

[weary tiger]

I guess one requires distinct objects the other doesn't is the way you would explain it? Both of them being permutations though and not "combinations"

[tidal tulip]

let f: X -> Y, f be injective. A subset X

i want to prove A $\subseteq f^{-1}(f(A))$.

is this correct

1. Since $A \subseteq X$, we know $x \in A$.

2. since $x \in A$ we know $y:=f(x) \in f(A)$ by definition of f(A).

therefore $A \subseteq f^{-1}(f(A))$

[vital dew]

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

[vale cairn]

What does your first line mean, what is x

But besides that, sure

this inclusion always holds though and we have the equality if f is injective

[tidal tulip]

f:X->Y, just letting x in A

i can probably just state suppose x in A and then go from there

[vale cairn]

Yeah

[weary tiger]

Can anyone tell this?

[stray reef]

what is there to tell?

@weary tiger which part(s) of the screenshot you sent here are troubling you?

[weary tiger]

yes

[hoary cloak]

wut

[weary tiger]

like how we take the degree

[hoary cloak]

i mean, what's written sounds correct to me

[weary tiger]

is it like the connections to the vertices

[weary tiger]

Yes ik

[hoary cloak]

isomorphism on graphs is a bijection that maps elements to elements, in such a way that an element is adjacent to another in f(G) iff they're adjacent in G

so if there's a vertex of degree 3, in f(G) you'd need exactly 3 vertices adjacent to it...

[weary tiger]

I got it but its kinda still confusing can u help me in vc if u dont mind

[hoary cloak]

right now i can't

i mean it'd be good if you put what's confusing you into words

i'll go out for a while and be back later

[stray reef]

"which part(s)..." is not a question to be answered with "yes"

if you meant that you don't know what the word "degree" means then why not say you don't know what the word "degree" means?

[night heath]

This is the question

What does he mean at the part that says there are 2k terms each >= 1/2^(k+1)

[stray reef]

2^k not 2k

but what is said is exactly what is meant...

there are a number of terms, each one is greater than or equal to 1/2^(k+1) and there are 2^k such terms

@night heath does this answer your question?

[night heath]

How did the 2k come out

I don't get it

[weary tiger]

sure let me know when ur back

[weary tiger]

like i didnt get the degree part like how do we take it

[unreal stump]

Look up definition of degree

[stray reef]

do you mean:

1. "i don't know what the word 'degree' means"
   or
2. "i don't understand how to find the number of degree-4 vertices in either graph"
   or
3. "i don't understand how they knew to consider vertices of degree 4 and not anything else"
   or
4. "i don't understand how it comes from this that the graphs are not isomorphic"

[weary tiger]

Like I'm getting confused with finding degrees

1

[stray reef]

#1, ok

the degree of a vertex is the number of edges connected to it

in your original screenshot, each vertex has its degree written next to it

does this resolve your confusion?

[hoary cloak]

i'm here

from what i gathered it seems like you're having trouble with what ann said

[weary tiger]

yes

[hoary cloak]

did they help clarify?

[weary tiger]

yes

[stray reef]

okay

do you have anything else you are confused with?

[weary tiger]

yes

[weary tiger]

so,we take each point and calculate its degree if im not wrong

[stray reef]

that is what they did, yes

it's not much of a calculation

since your graphs are given as pictures it's more like looking at the picture and counting

[hoary cloak]

knowing the vertex degree is very simple, just count how many edges are linked to it

[stray reef]

that is what i said

[weary tiger]

Cool

I got it now

Thanks a lot

[hoary cloak]

👍

[tidal tulip]

does this proof of (a) look good

[stray reef]

Since A subset X, we know x in A
we know x in A anyway

[tidal tulip]

ok so i can delete 1) and keep the rest of the proof

ty

so is this correct

if added more words it’s saying:

let x in A
then we have f(x) in f(A)

since f(A) = { f(a) | f(a) for some a in A}

and since A subset X

we have x in X

hence x in f^-1(f(A))

[tidal tulip]

?

[stray reef]

f(A) = { f(a) | f(a) for some a in A}
now this is bad

you should have just deleted 1 and not touched anything else

[tidal tulip]

ok

[worldly knot]

how come no. 2 is not true?

[stray reef]

what even is this question

"Find the error/s in the proof" what proof

[worldly knot]

I'm guessing "The sum of any two rational numbers is a rational number"

[stray reef]

that's not a proof

that's one assertion

[tidal tulip]

i want to prove that gof is injective if g,f is injective — can i get a proof check

let f: X->Y, x,y in X

suppose (g o f)(x) = (g o f)(y)
g(f(x)) = g(f(y))
since g is injective we know
f(x)=f(y)
since f is injective we obtain
x=y

thus gof is inj

[stray reef]

and nothing else

[worldly knot]

welp i just checked the question again and that's only what's given

[stray reef]

so the question is fucked up then

[tidal tulip]

does my proof look ok

[stray reef]

yes your proof is ok

[tidal tulip]

k

[worldly knot]

huh i c

[tidal tulip]

i want to prove if g, f is surjective then gof is surjective

can i get a proof check in this:
want to show for all z in Z there exist x in X such that (g o f)(x) = z

proof:

consider (gof)(x)

since f is surjective for all y in Y there exist an x in X such that f(x)=y

thus g(f(x))=g(y)

since g is surjective for all z in Z there exist a y in Y such that g(y)=z

thus we see for all z in Z there exist an x in X such that (gof)(x)=z

[worldly knot]

could someone give me an idea as to how the answer is 12870?

[coral parcel]

Do you know binomial coefficients?

[tidal tulip]

does my surjection proof look ok

[worldly knot]

yeah we kinda tackled it but why are we exactly using it for this case?

[coral parcel]

(a choose b) is exactly the number of size-b subsets of a set of size a.

"Unique but not disjoint" in the problem statement seems to be just filler. It seems to try to prevent misunderstandings of what is being asked, but doesn't add a substantive restriction of itself.

[tidal tulip]

could someone check this

[sleek loom]

maybe check your own proof?

[tidal tulip]

i did i don’t see any problems with it but it doesn’t mean i don’t have a blind spot and fooling myself

[sleek loom]

because checking your own proof is a valuable skill

you can't always get someone to check your proof

[tidal tulip]

yes and i think it’s fine but it doesn’t mean it’s actually correct

[sleek loom]

have some confidence in yourself

I self study discrete math too

look I'm not arguing with you, just advice ig

it'll slow you down to constantly ask people to check you

I don't care what you do with what I say

gl

[tidal tulip]

i appreciate your advice

[jolly rivet]

Would this be a valid way to do this proof

It makes sense in my head but I don't know if it is proper really

Maybe because I haven't really seen any examples like this

[severe swan]

Can someone explain this to me? I guessed D and it was not correct.
What is the greatest common divisor of c^2+c and 25c, given that c>0? I don't understand how to figure this out.

A c + gcd(c, 25)

B gcd(c, 25)

C gcd(c+1, 25)

D Incorrect Response c × gcd(c, 25)

E Correct Answer c × gcd(c+1, 25)

F c + gcd(c+1, 25)

G None of the other answers listed here is correct.

[coral parcel]

c²+c = c(c+1), and then apply the general rule gcd(xy,xz) = x·gcd(y,z).

[distant bobcat]

For a directed bipartite graph is it sufficient to have a partition of disjoint sets A,B where for each directed edge in A connects a vertex from A to B (or vice versa for B) or do we need the directed edges to connect both ways?

So, in the first definition both of these will be directed bipartite graphs, while if the second def. is true only the second graph will count.

[hoary cloak]

you don't need edges to go both ways, you just need to be able to split the vertices into 2 independent sets

and yes, both of those are bipartite

[distant bobcat]

ok, thanks.

also what about empty vertices? do we consider this as a bipartite graph? On one hand we can achieve a 2-coloring, but on the other hand there is no edge from one vertex.

[hoary cloak]

still bipartite

if you can achieve a 2-coloring, it's bipartite

it means you can split it into 2 independent sets which is the definition of bipartiteness

[distant bobcat]

yes, that makes sense.
Also, do you know how we define a directed line graph?

[hoary cloak]

tbh

the only kind of line graph i know is undirected

i mean, you'll switch the vertices with the edges, but idk how would you assign an orientation to each edge on the line graph

[distant bobcat]

yes, Im also unsure as I just know undirected line graphs. How about directed path graphs? These shouldn't be a problem to define

[hoary cloak]

yes but i'm unsure on what you plan to use this information for

[ebon quest]

Hi, can someone help me with this question? I’ve been looking at it but I don’t have any idea how to start

[distant bobcat]

@hoary cloak Actually I am just listing as many properties as I can for all directed graphs of 4 vertices. I have drawn them all in Latex. Tiresome work, although I did find a website that listed properties regarding undirected graphs I have yet to come across a website listing properties for directed graphs.

[hoary cloak]

gotcha. i mean there are a loot of properties for sure

you won't be able to do an exhaustive list (probably no one would)

is this for an assignment?

[stray reef]

up to isomorphism, hopefully?

[distant bobcat]

yeah,its for my thesis. However I don't need to list all properties. I just want to have some interesting properties associated with them

[true venture]

I think you would use binomial coefficients

[obtuse lance]

to make a directed line graph of a directed graph what you do is suppose you have edge E pointing to vertex v and edge F pointing away from v. Then in the resulting line graph you make a directed edge from vertex E to vertex F. Otherwise, you don't make directed edges at all

oh there's also an example here https://mathworld.wolfram.com/LineGraph.html

[distant bobcat]

Thanks)

[ebon quest]

Could you elaborate on that?

[true venture]

Wait, I don't think that's correct cause you aren't only choosing each letter once.
Or is that what distinct means?

Also make sure you don't count the words that begin with ABCD and end with MONKEY twice

[ebon quest]

This was what I did, do you know if this would be correct?

I followed a similar example

[true venture]

Idk if it is correct, but looks good

[ebon quest]

do all my P(n,r)'s look good? Any errors?

[true venture]

Wait I think order matters here right? cause using a binomial coefficient order does not matter

[true venture]

Sorry using a binomial coefficient order does not matter but here it does as different ordering would be considered different words.
Makes it a bit easier, think of the first set of words starting with abcd, then there are 13 letters that could follow, then 12, etc. Over the 9 remaining letter positions.

I got 261122190 words

Also the way you did it first with assuming oder doesn't matter should get a number less than the number for when order does matter.
So this it should be P(9,13) + P(7,11) - P(3,7)

P(n,r) being ways to choose n elements from a set of r elements.

Am I thinking of this correctly?

Interesting that if order didn't matter there are only 1010 words

[ebon quest]

Wouldn’t it be P(13,9) + P(11,7) - P(7,3)

[true venture]

Oof yea, I was thinking 13 letter words

What does distinct mean here, each letter in the word is different?

Oh so each word only needs 13 unique letters and then can have 4 letters repeat?

[ebon quest]

I think it was a mistake in the question and we’re supposed to treat it as 13 words

[true venture]

Lol if you assume the question is written wrong how can you answer it?

The question makes sense, just a bit more complex, since each 17 letter word needs 13 distinct letters and 4 nondistinct letters.

Gives much bigger answer. Since you need to tack on 17^4 on each term to account for the 4 non distinct letters

[true venture]

What class is this for if I may ask?

[ebon quest]

It’s just called discrete math

[ebon quest]

The teacher said to treat it as 13 words

[true venture]

So 13 letter words, with 13 distinct letters?

[ebon quest]

I think so yeah

[ebon quest]

So this would still make sense

[true venture]

No you cant choose 13 letters out of 9 letters and have them all be distinct

But because order matters here, binomial coefficients shouldn't be used

[ebon quest]

Isn’t the first number the amount of numbers you have and the other one is how many you can pick?

So if you have 13 letters, you can pick 9 distinct ones

[true venture]

Ok I wrote it backwards

But n choose r is wrong for this problem

Because order matters

[ebon quest]

Huh ok

[true venture]

In the words that start abcd....
You have already used 4 letters and have a total of 17, so there are 13 you could use for the next one. Then for the next letter 12 choices.

13x12x11x10x9x8x7x6x5 is the number of words that start with abcd I think
This can be written as 13! / 4!

Then the ones ending in monkey is
(17 letters- 6 used)! / ((17-6)-(7 letters open))

Being 11! / 4!

[ebon quest]

Right that makes sense

The last one would be 7!/4! right?

[true venture]

Yes

[ebon quest]

Oh ok yeah that makes sense

[true venture]

The problem of 17 letter words with 13 distinct letters is more interesting.
Not sure how the overlap of words starting with abcd and ending with monkey would be calculated. You should ask your teacher that lol

[ebon quest]

If I remember I’ll ask lol

[true venture]

Does anyone else here know how that would work?

[severe swan]

Can someone explain this to me? i don't understand why that answer is the one that is not equal to all the others.

Which of the following is not equivalent to the others?

a is not divisible by b

a mod b > 0

a is not a multiple of b

b is not a factor of a

a is not a divisor of b This is the correct answer

all the above statements are equivalent

[sleek loom]

a is not a divisor of b doesn't mean b is not a divisor of a which is what all the others answers are saying?

[true venture]

I naturally think of a>b when thinking of the others so saying b is not a multiple of a feels weird. I know that doesn't matter though

[true venture]

Interesting, I've never heard of a line graph before, where do you end up if you just keep converting to a line graph?

[true venture]

You have said you self study discrete math, how are you going about this?

[sleek loom]

About the self studying?

[true venture]

Yea just wondering like what books or topics

[sleek loom]

I just picked up a reputable book, but it's not in English

And being really critical of my understanding of the material

I don't think the book itself matters as much as how you study, so just any alright book might work

And the book just teaches the topics in order

[obtuse lance]

idk fun question, looks like cycles are going to be fixed points under iteration

I worked out a formula to count the number of edges in the new graph given the old graph as a starter to see when it increases or decreases

[true venture]

Wikipedia says depending on the starting graph some disapear, become a triangle or grow without bound

I was drawing the square with a diagonal shown on wokframm

That one seems to get more edges each iteration

[obtuse lance]

I kind of imagine drawing the graph on some closed 2D surface, and then constructing the line graph of that on the new surface as a way to kind of try to tame it

I think you can always do this, sort of makes it clearer to me whether it's going to get bigger with each iteration or not since it seems like it's kind of subdividing the mesh further at each step

this makes it so if you look at any single vertex, it's approxmately planar there and then you're making a face at that vertex, then you kind of go around all the edges incoming at that vertex to make the edges

similarly every old face also becomes a face

so sort of like taking a 3D shape and sanding off its vertices to make a new shape

[true venture]

Cool

[obtuse lance]

I think we can then exactly count the number of vertices, edges and faces for each iteration with euler's formula

[true venture]

What is a face here?

Also lame i can't find any pictures of a bunch of iterations

[obtuse lance]

picture it in your head 😛

the graph is embedded in a 2D surface so a face is enclosed by a cycle

like think a soccer ball

but can be a donut with a graph drawn on it too

[true venture]

But a triangle area is not a face?

[obtuse lance]

?

why wouldn't it be

[true venture]

Cause not a soccer ball

[obtuse lance]

soccer ball is just a 2D surface with a graph on it

could be any graph drawn on any 2D surface

that was just an example

[true venture]

Oh ok

[ebon quest]

So for this question, I got to here but then I’m not sure what to do next

[livid minnow]

notice that (k+1)/(k-2) < 2

thus the inequality would hold if you multiply a number greater than or equal to two when you multiply the left side by (k+1)/(k-2)

[plain pawn]

is there dataset of circulant graphs? http://oeis.org/A049287

[steady path]

Setup looks reasonable. What is causing you to get stuck? Can you use the inductive hypothesis somehow?

[old delta]

can anyone dm to see if my proof makes sense?

here are the questions

[ember obsidian]

pls post here

[worldly knot]

what are these called

[coral parcel]

Indexed union.

[candid fractal]

can someone explain what this means in simple words and maybe a concrete example?

[worldly knot]

is there a calculator online that I could use? I'm tryna review for exams

[cerulean wind]

it’s literally defined on the page

[candid fractal]

i don't really understand what it means

[stray reef]

$N(k) = |A_{i_1} \cap \dots \cap A_{i_k}|$

[vital dew]

Ann

[candid fractal]

What is N(k)? the number of elements in the intersections of k sets?
First line after 'then the formula becomes' on the RHS, why are we able to pull out the N(k) from the sum?
Why does the 1 part become (n,k)?

[stray reef]

What is N(k)? the number of elements in the intersections of k sets?
yes

we're considering the case where, no matter which k sets you go with, their intersection will have the same size

and in this case N(k) of course no longer depends on the i's i.e. on which sets you're taking intersections of

[candid fractal]

What does the 'finally Ai subset....' mean? what does N(0)=|X| mean?
How does that translate to the 'complement version'?
What does all of this mean in a combinatorial sense? (would be easier to see with a small 3 set exam)

[stray reef]

Why does the 1 part become (n,k)?
you have a sum of several terms each equal to 1, and there is one term for every possible strictly increasing list of k indices, of which there are nCk by definition of nCk

[candid fractal]

so it depends only on the number of sets we're choosing, not which ones

[stray reef]

yes, that's the special case they're considering

What does the 'finally Ai subset....' mean? what does N(0)=|X| mean?
if we consider all of our A_i as subsets of some bigger set X, we get a formula that gives us the number of elements in the complement of the union of A_i wrt X, as written on the left-hand side of the formula
setting N(0), a quantity not otherwise meaningful, to |X| produces a somewhat more elegant formula

[candid fractal]

'you have a sum of several different terms equal to 1'
which terms are you referring to?

[candid fractal]

does this mean it's equal to one? this notation is a bit confusing

[stray reef]

what's "it"?

[candid fractal]

'the sum of several different terms'

[stray reef]

no

the TERMS THEMSELVES are EACH equal to 1

their sum isnt

[coral parcel]

Depending on your intuition, it might work for you to simply skip the middle line there. In the first line you have a sum of a bunch of things, each of which equals N(k). Then in the third line that sum has become N(k) times how many of the "N(k)" you had in the original sum. The intermediate expression with a sum over 1 may or may not help you see how that works.

[candid fractal]

i think this makes a bit more sense, and then "how many of the "N(k)" you had in the original sum" i'm assuming is (n,k)?

what does this notation mean exactly?

like what is it doing

[coral parcel]

It says there is one term for each way to choose i1, i2, ..., ik that satisfy the inequalities.

That's arguably a bit of overkill here, what is meant is just that there is one term for each k-element subset of {1,2,...,n}.

[dry sandal]

a directed acyclic graph has the same "structure" as a partial order right?

and how to say this more formally?

[coral parcel]

No, since a DAG does not have to be transitive.

[dry sandal]

oh

[coral parcel]

I.e. the graph on {1,2,3} withe edges {(1,2),(2,3)} is different from the graph with edges {(1,2),(1,3),(2,3)}, but they would encode the same partial order.

[dry sandal]

ok makes sense

what is the word to use for talking about preserving the "structure" of a structure but neither (or not necessarily) their sets, functions, nor relations?

[candid fractal]

would you be able to give a concrete example of this special case of IE with a small set of suppose n=3 and how it would work out?

[weary tiger]

i need help

[supple rapids]

If $f: A \to A$ is not surjective then: $\exists a \in A ( \forall b \in A, f(b) \neq a)$

Feels wrong to me, but its equivalent to:

If $f: A \to A$ is not surjective then: $\exists a \in A ( \lnot\exists b \in A, f(b) = a)$

Is this correct?

[pale epoch]

no

the \neq in the second statement has to be =

[supple rapids]

Ah

[vital dew]

ryаn

[supple rapids]

So is this correct?

[pale epoch]

yes

[supple rapids]

also whats with there being no standard for how (,) are used and sometimes | instead or even a comma?

[pale epoch]

i wouldnt use a comma here

or anything

parentheses to show scope of the quantifiers

like you did for the first one

[supple rapids]

Wikipedia used something like:
$\exists a \in A ,\lnot\exists b \in A, f(b) = a) $

[pale epoch]

🤷

[supple rapids]

Though some books use:
$\exists a \in A ,\lnot\exists b \in A | f(b) = a $

[pale epoch]

you almost never write down statements like this

and when you do, you define your syntax precisely

[supple rapids]

ah right, its like how no one writes "1 / 2 * 3" or "a ∧ b ∨ c", since its syntactically ambiguous

[pale epoch]

eh, natural language is just the better choice

[supple rapids]

yea so much for set theory being on formal rigourous grounding....

[pale epoch]

the only reason to write down such things is if you want to syntactically manipulate it but then nobody cares how you write it down

or if you build a language formally and you have to care about how statements must look like

and then the book will use some precise definition

[supple rapids]

hmm i see

[tidal tulip]

to show that a bijective function has an inverse function i need to prove:
(a) if a function f is bijective, then f has an inverse
(b) if a function f has an inverse, then f is bijective

correct? because the class proved (a) and made it seem that was the end of the proof

[sleek loom]

To show that a bijective function has an inverse function you need to prove (a) only, to show that if a function has an inverse then it is bijective you have to prove (b) only

If you want to show that a function is bijective if and only if it has an inverse then you need to prove both

[tidal tulip]

ah, ok i see

[ebon quest]

I just don’t have any idea what I can do from here to in order to prove it

[steady path]

Ok, but can you identify where exactly you are stuck? Do you know what it is you are trying to do next? Can you recall any relevant formulas regarding binomial coefficients?

[tidal tulip]

how do i prove the inverse of a bijection is a surjection?

i know we want to show for all a in A there exist a b in B such that f^-1(b) = a assuming we are talking about a function f:A->B

i started by saying let a in A. we know f^-1(f(a))=b because… and get lost here finding a b in B for any a in A

[viral crown]

uhhhh i'm not sure where else this goes so i'll just ask here

why is $\phi \times \mathbb A$ where $\mathbb A$ is a set always just $\phi$

[vital dew]

valley

[viral crown]

is it because you can't really "take" elements from $\phi$?

[vital dew]

valley

[austere swan]

First of all, use $\emptyset$ or $\varnothing$ for the empty set. Secondly, it's precisely because of that. The definition of a cartesian product is
$$A\times B={(a,b):a\in A, b\in B}$$
If one of the sets in the product is empty, there aren't any elements in it, so there aren't any tuples satisfying this, hence the set has no elements, so it's.empty.

[vital dew]

ShiN

[tidal tulip]

any ideas on this

[austere swan]

f^-1(f(a))=a, not b

Where does f(a) live

[tidal tulip]

f(a) lives in B

let a in A. Let b:=f(a)

we know f^-1(f(a))=f^-1(b)=a by a lemma i proved earlier

so there exist a b in B such that f^-1(b)=a

namely b:=f(a)

i think but confused if that works or why

trying to unwind definitions

[austere swan]

that does work

that's exactly how you do it

i'm not sure what you mean by a lemma, f^-1(f(a))=b is exactly the definition of the inverse function

[tidal tulip]

i guess i’m confused because i don’t see why plugging that a into f and then saying b:=f(a) is my b for any a works, i need it explained a little more

i think i get it

it’s saying

we want to show for all a in A there exist a b in B such that f^-1(b)=a

and i say oh i have a b

b:=f(a)

apply the defs

and you see f^-1(f(a)) = f^-1(b) = a

that it?

[tidal tulip]

@austere swan

[austere swan]

exactly

[tidal tulip]

ok awesome

[hearty furnace]

Can somebody explain to me how you might get these?

[weary tiger]

for f_n just follow the pattern

shouldn't it sum up to 2^n?

[hearty furnace]

For that first part yea

[weary tiger]

ok and whats theorem 5.2?

[distant dove]

I believe first part n^n

Second part has to do with induction

Something like n(n+1)^(n+1)

Or (n(n+1)^(n+1))/4

[cold latch]

does anyone know how I would find the definition of the following set of numbers: h = {(1, 2), (2, 1.5), (3, 1.333 . . .), (1, 1.25), . . .}

[coral parcel]

Are you sure the last of the listed pairs shouldn't be (4,1.25)?

[cold latch]

yeah :/

[coral parcel]

How about {(((n-1) mod 3)+1, 1+1/n) | n in Z+}?

[cold latch]

that works actually, thank you 🙂

[ebon quest]

So I just did this, does this seem correct?

[dusky robin]

https://oeis.org/search?q=0%2C3%2C8%2C15%2C24&sort=&language=english&go=Search

[onyx fable]

How is that the recursive forumula?

[proven silo]

scroll down to formula

[onyx fable]

I cant find it?

[olive wren]

[south marten]

King Arthur chooses three of the 25 knights sitting around his table to fight
a fearsome dragon. How many possible choices are there, if no two of the chosen knights should sit next to each other?

To solve this question I did 25 choose 3 - 24! is this correct ?

[proven silo]

What? Yes it is

[dusky robin]

Your answer is a negative number.

[south marten]

oh other way around my bad

I'm not sure if I counted correctly

[proven silo]

What? 15+2*4+1=17 in your mind?

[viral crown]

does anyone know a simple proof that for any infinite set $\mathbb A, |\mbb A| = |\mbb A^n|, n \in \bZ^+$?

[vital dew]

valley

[viral crown]

someone told me it was true and i understand the diagonalization and induction argument for the integers, but i wanna see a proof that can be applied to the reals

[spring hound]

What is the generic name of combinatorics functions that produce actual results, like all permutations of a set or a cartesian product, rather than the count of results?

[cerulean wind]

what part do u need help on

[onyx fable]

Not sure how to do it...

[cerulean wind]

well what have you tried? what are the definitions of cardinality that you are using? what does it mean for two sets to have the same cardinality?

[cerulean wind]

not really a simple proof but ik one that uses zorns lemma and induction

[onyx fable]

Two sets A and B have the same cardinality if there exists a bijection

[cerulean wind]

okay great

so there is a bijection from A to B and a bijection from B to C

how would i get a bijection from A to C?

[onyx fable]

Thats the part not sure about

[cerulean wind]

you need to compose the bijections

if f : A —> B, g : B —> C are the bijections, then consider the composition g o f : A —> C

where (g o f)(x) = g(f(x))

[onyx fable]

okay give me a sec to try

[viral crown]

could you link it or post it? i'll come back to it when i know more set theory

[onyx fable]

okay I understand how to get here

[onyx fable]

@cerulean wind i got to g(b)=c

[cerulean wind]

search for a pdf of enderton’s “elements of set theory”. should be the first link on google. check in the chapter about infinite cardinal arithmetic

[cerulean wind]

i’m not sure what this means

you need to show that g o f is a bijection

[onyx fable]

hmmm, so when do I have to do from there?

[viral crown]

is that a good book?

[wide vine]

A function from X to Y can be viewed as a subset of X × Y: (x, y) ∈ f if f maps x to y. It is possible that X and Y are in fact the same set, in which case f is a subset of X × X.

what do they mean by the X × Y

Are they saying it is basically a subset of the cartesian product of the sets X and Y?

Say X is the set of Reals and Y is the set of Reals?

[steady path]

Yeah that kind of idea works. Nice. See if you can write in complete sentences to explain what you're doing along the way.

[ebon quest]

Ok sweet, also idk if you’re familiar with this kind of stuff but I’m having trouble with two smaller questions

[hard citrus]

Sort of, yes. It's trying to say that the mapping can be represented as pairs (x, y) where x is in X and y is in Y and f(x) = y

[hard citrus]

It would be easier to construct an example with a finite countable* set, take some small subset of N and some arbitrary set X, then your f will map the elements of the subset of N to elements of X and the pairs (n, x) will be in NxX

[wide vine]

sure but when they used the term "subset" of X x Y means that you might have a function that doesn't use all the X set or Y set . like how you might say 1<=x <=4 ?

But the whole set of X and Y could be the reals but you only have a subset of those in your f

[hard citrus]

If f doesn't use everything in X then it's not a function

[steady path]

And what are your troubles?

[hard citrus]

It might not use all of the Y elements though

[wide vine]

oh. so they mean more so that you wont see all combinations

[hard citrus]

And that's why it's a subset

[wide vine]

I see

[hard citrus]

Have you by any chance learnt about relations?

[wide vine]

nope

[ebon quest]

I’ve never been taught this and don’t know what it’s asking

[hard citrus]

This way of looking at functions becomes really clear after you get introduced to relations

[steady path]

Have you tried doing any research online? Can you give the definition of a graph?

[ebon quest]

I tried but I didn’t really understand

[hard citrus]

Try to construct an example if you have a hard time seeing it. Take A={0, 1, 2} and B={a, b, c, d, e}. Make an arbitrary function f: A->B and see that it is a subset of AxB @wide vine

[wide vine]

we have this example and I see how it is a subset.

so like for exmaple

example

X x A should have all 16 pairs? but in this case we only have 4 of the X x A

like how w only maps to a

[rigid oriole]

subset of X x A

[hard citrus]

Yep

Can you see why it's always going to be a subset of XxA ? ||I realise now that this is a weird question||

[wide vine]

but in the X x Y you could have (w,a), (w,b), (w,c), (w,d)

[hard citrus]

Exactly

[wide vine]

well by definition it seems you can't have a mapping from the domain to multiple elements in the co-domain

so you would always have a subset

they also call it "target" but idk what the correct term is for it

[hard citrus]

Also, XxA does have 16 pairs, but f has 4

f: A->B
A - domain
B - codomain

[wide vine]

Yeah that is what I meant

while the X x A will have 16 pairs, the f won't because you can't have an element in A that would map to multiple elements in the codomain

[cerulean wind]

yes

[viral crown]

hmmmm ty i'll check it out

[wide vine]

for a function to be surjective wouldnt this mean the cardinality of domain has to be the same as the co-domain

[wide vine]

or greater

[wide vine]

How would I go about proving something is surjective, bijective, and injecive?

my problems are not asking me to prove them but just answer what they would be based on the function. I can determine it but I can't say for "certain" it is

like with a proof

[weary tiger]

proving a function is bijective is proving that it is both surjective and injective

[final cliff]

If $f:A\to B$, one common way to prove $f$ is surjective is to assume $y\in B$ and then find an $x\in A$ such that $f(x)=y$.

[vital dew]

DootDooter

[final cliff]

For injectivity one common way is to assume $f(x)=f(t)$ and then to show $x=t$.

[vital dew]

DootDooter

[final cliff]

(Or to do the contrapositive of that)

Though in other contexts you might have special theorems and tricks that allow you to avoid proving injectivity/surjectivity those ways.

[wide vine]

I'll have to look into this and probably see a few examples.

[final cliff]

Those two ways are basically just showing the definition of surjectivity/injectivity hold I suppose.

Proving those is basically just showing every elt of the codomain gets mapped to or that no two distinct elts of the domain map to the same thing.

[wide vine]

is this stuff easier if you are working with integers . Not sure if you could use some sort of f(n+1) idea or f(n-1) from a base point to show maybe 1:1 etc

like some sort of proof by induction

I guess that might just depending on the actual function also though

[final cliff]

Functions on the integers can be pretty complicated.

[wide vine]

more so then just reals?

I thought it would make the problem easier if you have a "smaller" set to work with

[final cliff]

Well number theory is a whole thing I guess lol.

I'm probably not qualified to really say which of those things are more complex lol.

But sometimes there are nice theorems with finite sets of integers.

Pigeonhole principle can be helpful.

So can well ordering property type stuff.

I'm pretty sure most of the really common counting principles from combinatorics can be stated in terms of set cardinalities of finite sets too.

[wide vine]

@final cliff If you could show an inverse of a function will that show anything about it being surjective/ injective?

[final cliff]

Yeah a function is bijective iff it is invertible iirc.

[wide vine]

I just got to my "inverse of a function" section so maybe bad time to ask

but I would think a one to one function might be invertible?

although idk

[final cliff]

A 1-1 function is always invertible

[wide vine]

sounds like it should be

[final cliff]

It has to do with the codomain/range distinction.

A 1-1 function might not be onto its codomain, but it is onto its range.

The codomain and range of a function might not be the same.

[wide vine]

Yeah I see.

[final cliff]

So I guess maybe I worded this poorly lol.

[viral crown]

mannnn i don't understand cantor and dedekind's proof of transcendental numbers at allll

anyone have any good resources to hammer polynomial things into my head

https://www.math.ucdavis.edu/~hunter/m127a_19/rat_dense.pdf

in this paper, they say "Suppose that $A \subset \bR$ is a set of real numbers. A maximal element of $A$ is a number M = max $A$ such that $M \in A$ and $M \geq x$ for every $x \in A$. A minimal element of $A$ is a number m = min $A$ such that $m \in A$ and $m \leq x$ for
every $x \in A$. It follows immediately from the definition that if $A$ has a maximal or minimal element, then sup $A$ = max $A$ or inf A = min $A$.

[vital dew]

valley

[viral crown]

but

what do they mean by sup and inf?

[stray reef]

supremum and infimum

least upper bound and greatest lower bound respectively

@viral crown

[weary tiger]

https://gyazo.com/33f4ade24893b8c765645ae9ea7d7529

anyone familiar with this?

[stray reef]

what is "the game with demon"?

[haughty garden]

that sounds like the standard way of showing that a language is not regular. You give the demon the language; the demon picks the pumping constant; you give the demon a string w in the language where |w| >= p; the demon gives you a way to break up the string into w = xyz where |y| > 0 and |xy| <= p; you give the demon an i such that xy^iz is not in the language

[stray reef]

how does that differ from applying the pumping lemma directly

[haughty garden]

it doesn't

it's the same formulation

[stray reef]

so how does one follow the directive not to apply the pumping lemma directly?

[weary tiger]

Hi! So I have this set of arguments and we have to construct a formal proof using chain of reasoning.

Since C is equivalent to A, would that make C equivalent to C ↔ A?

So I can write C ↔ A ∨ ~B

[molten chasm]

I don't think so, if C if true and A is false, then
C is true but
C <-> A is false,
hence they are not equivalent

[weary tiger]

isee

[molten chasm]

oh wait, I have miss the premise C <-> A so C and A cant be different

[weary tiger]

man i've been stuck with this problem for houRs 💀💀

our reference materials did not have premises containing <->, searching in google doesn't have examples either so 💀💀

[molten chasm]

what you reference materials have

[weary tiger]

this is the closest

how would you guys work this out?

by 16 years, 99% of patients have at least a 2-year period of remission

[weary tiger]

however, i can't see a solid link between the premises and the conclusion

[weary tiger]

unlike this example that could easily be proven thru modus tollens

[molten chasm]

given C<->A, can you break it into C->A and A->C to eliminate the bicondition?

[weary tiger]

so far i have:

1 C <-> A | premise
2 C ∨ ~B | premise
3 (C -> A) ^ (A -> C) | 1, material equivalence
4 C -> A | 3, simplification
5 ~A -> ~C | 4, contrapositive
6 ~C -> ~B | 2, material implication
7 ~A -> ~B | 5,6 hypothetical syllogism

[weary tiger]

ya i've done that

[weary tiger]

so far i got to the point where i proved that ~A -> ~B

tho i can't seem to figure out how i would make that useful

[molten chasm]

I can see that the last step can becomes (C v ~B) n (A v ~B)
since we have C v ~B, we need to obtain A v ~B

I think 7 can help you?

[weary tiger]

so i'll get the material implication of 7

so it would become
8 A v ~B | 7, material implication

(C v ~B) n (A v ~B),, i dont get this tho

[molten chasm]

distributive law

[weary tiger]

oh

u mean

ill conjunct them

then isolate ~B

??

[molten chasm]

yes

[weary tiger]

WTF

[molten chasm]

9 conj
10 distributive

[weary tiger]

https://tenor.com/view/mind-blown-gif-11131691

dam

our examples did not include any distribute out

it was always in

thanks~

[molten chasm]

[urban mantle]

Can someone link me good data set of isomorphic graphs? I need to write algorithm that checks if two graphs are isometric so I need to write tests of it first but creating even 100 isometric graphs by hand is too long

[pale epoch]

i have a dataset of only circulant graphs

but its digraphs

in general its very hard to generate such a dataset

and it depends a lot on how you store graphs on your computer

there are some pretty good (fast) probabilistic algorithms that check graph isomorphism, its probably best to just randomly generate a bunch of data

my data looks like this:

those are all circulant (di)graphs on 10 vertices

each line is an isomorphism class

a circulant graph on n vertices has vertices {0, 1, ..., n-1} and a number x here means that each vertex i has a (directed) edge to (i+x) mod n

e.g. those are the graphs {1, 2, 5} and {1, 5, 6} on 8 vertices

(they are isomorphic)

[coral parcel]

Good non-isomorphic test cases are harder to come by systematically because they need to look sufficiently alike that it takes all the sophistication of your algorithm to tell them apart.

[true venture]

Oh here it is my bad

[ebon quest]

I got 2 and no for my final answers can you see if that’s right?

[true venture]

I'm trying to work out the graph problem. What are these for? I've enjoyed thinking about the ones you have posted.

What is the relation of the min number of edges for a graph with x vertices of degree x+1?

[ebon quest]

They’re just review questions

For the first question the sum of degree = 2 * edges

So that’s 2*30 which is 60

We know 60= 7*6 + 3(# of vertices with degree 3) + 0(# of vertices with degree 0)

So vertices of degree 3 is 6

Since there is 14 vertices total and 6 of them are degree 7 and we just found 6 of them are degree 3, the last 2 are degree 0 or isolated

[true venture]

Why is the sum of the degrees always 2* edges?

[ebon quest]

I’m not sure, just found it online but I think it’s because each each is incident to 2 vertices

[true venture]

Ok what you did makes sense then

I was trying to draw 6 vertices of degree 7 and kept using too many edges

[elfin tiger]

So I’m struggling with being able to differentiate the difference between permutations and combinations in word problems. Is there an easy way or like keywords that gives these away

[true venture]

Think about does order matter? Like if I picked the three numbers (234) does that count as one possibility or, do 243, 234, 324, 342...ect. each count as a different possibility

[true venture]

From what I was drawing I drew 6 vertices with degree 7, but also with 2 vertices with degree 6. Which isn't allowed, that where was getting messed up

[dire obsidian]

How does this proof work?

[obtuse lance]

it's called proof by induction, there are two parts, proving a base case and proving that the kth case implies the k+1 case

[true venture]

Can you draw the graph?

[obtuse lance]

the second part is called the inductive hypothesis, it's kind of like saying if you have dominos lined up and the kth one falls down it knocks down the k+1 domino in front of it

the base case corresponds to knocking down the first domino

[spring surge]

what real life problems does combinatorics solve in engineering/economy/medicine fields?

[olive wren]

How many ways you can order blue and red balls

[true venture]

Drawing the graph takes much longer

[ebon quest]

Yeah I can tell lol

[obtuse lance]

you drew that 😬 haha

brave but painful

[obtuse lance]

oh 3.g is fun

||first vertex is connected to nothing, last vertex is connected to everything, contradiction||

[ebon quest]

Oh so, I was right when I circled “no”

[obtuse lance]

well idk if I would conflate "lucky" with "right"

[ebon quest]

I just thought of it differently, it’s not possible to have a degree 6 vertex and degree 0 vertex together

But it’s basically the same logic as what you said

[obtuse lance]

gotcha

[true venture]

The classic problem of packing Vienna sausages into a can.

[true venture]

This is wrong anyways 😪

[severe swan]

Would this be correct?

A particular brand of shirt comes in 10 colors, has a male version and a female version, and comes in three sizes for each sex. How many different types of this shirt are made?

My answer: 180

10 colors * 2 versions (male and female) * 3 male sizes * 3 female sizes = 180

or would it be 10 * 2 versions * 6 sizes = 120

[proven silo]

can always just scale it down to check your answer - if 1 colour you can list out all types

[true venture]

Here is a correct graph with 12 vertex, 6 of degree 7 and 6 of degree 3.

[ebon quest]

Actually now that I think about it, can’t you make a regular graph from the sequence?

But not a simple one

Or am I wrong?

[obtuse lance]

what do you mean by regular graph? graph where all the degrees are equal?

[ebon quest]

There’s 2 types of graphs right? Regular and simple?

[obtuse lance]

I still don't know what you mean

[ebon quest]

Simple is a graph without loops and parallel edges

[obtuse lance]

regular graph means graph where all the degrees of all the vertices are the same to me

[ebon quest]

I’m just saying couldn’t you make a normal graph with that sequence (0,1,2,3,4,6,6) but not a simple one

[obtuse lance]

yeah possibly

[ebon quest]

Well the question is asking if you can make a graph with the sequence (doesn’t need to be a simple graph)

[obtuse lance]

the word graph usually means "simple graph"

unless they state otherwise

[ebon quest]

I think my question doesn’t mean “simple graph” when they say graph

[obtuse lance]

otherwise they would have asked for multigraph or something with multiple edges or loops

you're over thinking it

[ebon quest]

Because I was just told if they ask for a simple graph they would specify in the question

And if they ask for a regular graph, they just write graph

[obtuse lance]

https://mathworld.wolfram.com/SimpleGraph.html

read the first few sentences, I can't really convince you otherwise if you don't want to believe me

[ebon quest]

Right I get that but here

[obtuse lance]

ah well that changes things

[ebon quest]

So it would be yes right?

[obtuse lance]

possiby

[ebon quest]

This is a different example but you get what I’m saying tho

[obtuse lance]

yeah you can make one, there's an easy example I have in mind

[ebon quest]

Ok, the final answer was yes

[obtuse lance]

well you have a lot of freedom so drawing an answer is easy

the question says to draw one so you kinda have to be able to construct it too

[ebon quest]

For my sequence, you don’t really need to show it unlike the other one I sent

Cause the sequence I’m talking about is different

[obtuse lance]

well it depends on the sequence if you're talking about a different one

probably better to just ask that question instead

[ebon quest]

I’m talking about (0,1,2,3,4,6,6)

[obtuse lance]

oh I thought this was the exact same question but showing more for context, confusing

[ebon quest]

The sequence was different

[obtuse lance]

well whatever if you feel content with not knowing how to construct one I won't twist your arm

[ebon quest]

Here I’ll just delete it

Ok but you can draw a regular graph for the sequence (0,1,2,3,4,6,6) right but not a simple one

Right?

[obtuse lance]

stop and think

[ebon quest]

It should be yes?

because you can say the last one that’s connecting to 6 things isn’t connecting to everything

Cause you can have 4 connected to one and 2 connecting somewhere else

[obtuse lance]

@ebon quest this is where we started, it seems like you didn't understand this proof

explain why this works

[ebon quest]

Because you can’t have a degree 6 that’s connecting to everything and 0 at the same time

Because 0 is connecting to nothing

[obtuse lance]

👍

[ebon quest]

So even with a regular graph, you still can’t make it with the sequence (0,1,2,3,4,6,6)?

[obtuse lance]

try to make one

[ebon quest]

Yeah I don’t think it’s possible

[obtuse lance]

you're allowed to make self loops right?

[ebon quest]

Yeah

[obtuse lance]

you can just make loops on everything to make them, with one edge between the two odd degree vertices

[ebon quest]

Wait so it is possible

[obtuse lance]

yep

[ebon quest]

okkk that makes sense

Just to be clear

you CAN make a regular graph (with loops and parallel edges) with the sequence (0,1,2,3,4,6,6) but CANT make a simple graph(without loops and parallel edges)

[obtuse lance]

right

[ebon quest]

ok, so before you thought it meant simple graph

which was why it wasn’t possible

[obtuse lance]

a graph with arbitrary edges like that can always be made as long as it has an even number of odd degree vertices

since you can fill out all the even degrees with loops and the odd degrees can be handled by making edges between them in pairs to match up

[ebon quest]

So any sequence with an even number of odd degrees always has a regular graph?

[obtuse lance]

yeah

[ebon quest]

Dang that’s good to know

[obtuse lance]

although you shouldn't call them "regular graphs" because a regular graph means the degree of all vertices is equal

[ebon quest]

Right

All good now right

[obtuse lance]

sure, I guess

if your teacher marks it wrong you just show them that screenshot you showed me of the other question

I won't try to mind read what your teacher expects, you're on your own

[ebon quest]

yeah but I know for a fact he didn’t mean “simple graph”

cause he said it himself

But thanks again for the help

[obtuse lance]

yup you're welcome

have any more problems?

they're kinda fun lol

[ebon quest]

umm not really, I solved the rest of them

unless you wanna try solving them yourself lol

[obtuse lance]

sure might be fun later to play around with

[viral crown]

thank you!

[weary tiger]

Whats discrete math

[coral parcel]

Sometimes it means "the scattered selection of math topics that CS students at such-and-such university must learn". As such it contains general "math literacy" areas such as proof techniques, basic sets and functions, mathematical induction, etc. It also contains a few topic of particular CS interest, such as asymptotic growth, computability, often some rudiments of formal logic, etc.

At the same time, it also functions as a bit of a "wastebasket category" for things that don't have better channels of their own, but do seem to have some kind of "discrete" character -- such as combinatorics or graph theory.

[true venture]

😟 I thought combinatorics and graph theory had a solid place here

[coral parcel]

Graph theory is definitely also a thing needed for CS.

I have no idea who really needs to know how many distinct words can be formed from the letters of ANTIDISESTABLISHMENTARIANISM if there must be at least two As and at most three consonants can come together.

[viral crown]

me i really need to know

[true venture]

Lol

[tame scaffold]

discrete question here hi ( :

confused on how one would write a floor/ceiling function with factorials ?

[dire obsidian]

Why does this count as an induction proof even though the induction hypothesis is k-4?

[viral crown]

bc of the condition at the bottom, i would assume?

[dire obsidian]

can you elaborate?

[viral crown]

it says it's true for all $n \in \bZ^+$ with $n \geq 24$

[vital dew]

valley

[viral crown]

which is why the IH can be for just 24+

[dire obsidian]

but why is IH allowed to be k-4

I get how inductions usually work when IH is just n=k

but not n=k-4

How do you know if it even covers all of the claimed domain

[severe swan]

How would I solve this?

There are 26 letters in the English alphabet.

A license plate consists of either (2 upper case letters followed by 4 digits)

or (4 upper case letters followed by 2 digits). How many different license plates are possible with these restrictions?

I am using permutation because it looks to me like the order everything is in matters.
Would this be the correct formula?
(26P2 * 10P4) + (26P4 * 10P2)
2 letters and 4 digits + 4 uppercase and 2 digits

[dire obsidian]

You want to use permutations with repetitions allowed because you can reuse digits and letters

otherwise lgtm

Anyways moving on I'm still stuck on this stupid induction problem

[unreal stump]

You need to consider 24,25,26,27 and 28 explicitly

After that you use strong induction

Since 24<=n-5<n and n-5 can be written in that form our hypothetical is true

[dire obsidian]

can you explain this a little more? The main part I am confused at is why you can get away with using k-4 as IH

[unreal stump]

This is strong induction

[dire obsidian]

What?

[unreal stump]

You can assume everything in a set satisfies the IH instead of just one element

And then you expand this set one element at a time

So {24,25,26,27,28} is initial set

29-5=24 in set so 29 satisfies our set becomes {24,25,26,27,28,29l

[dire obsidian]

wait but n = k-4

why isnt it {20,21,22,...}

[unreal stump]

Because you start considering from 29

[dire obsidian]

I'm so confused

[unreal stump]

Your initial set is {24,25,26,27,28} because the Induction hypothesis holds for those

[dire obsidian]

what about {20,21,22...}

[unreal stump]

And then when you include a new element k,you check if k-5 is in the set

[unreal stump]

Hypothesis doesn't hold

[dire obsidian]

But then they are not proved at all

owait n >= 24

[unreal stump]

You do it explicitly

Yea

[dire obsidian]

you don't need to prove them

becauase domain

[unreal stump]

Yea

[dire obsidian]

can you explain to me how set {24,25,26,27,28} is involved in an IH of n=k-4

[unreal stump]

That's your basis

24=5+5+7+7
25=5+5+5+5+5
26=7+7+7+5
27=5+5+5+5+7
28=7+7+7+7

[dire obsidian]

I have to prove the set using basecase first before IH?

This is how quizlet solved the question

extremely confusing

wait I think I wrote the answer wrong in my original screenshot

nvm

I'm so confused why this range of IH

How do you decide what range of Basis you need and how do you decide the domain of your k in IH?

[unreal stump]

Depends on the question

Here the question was n>=24

And we needed n-5 to satisfy that

So n has to be atleast 29 for hypothesis to work

[dire obsidian]

can you explain this to me as If I am absolutely stupid

[unreal stump]

Ok so suppose n were 26

[dire obsidian]

yes

[unreal stump]

Then n-5 will be 21 which we know is not in the set

So we can't really reason with 26 this way

[dire obsidian]

ok but why use k-5 in the first place?

[unreal stump]

Well combination of 5 and 7

So if k were a combination then either (k-5) is a combination or (k-7) is a combination

You could have went with 7 too

[dire obsidian]

sorry that question was too stupid

so then why include 24 within the set

if 24 - 5 = 19

[unreal stump]

That's the thing you can't prove it with induction

But you can prove it by writing it explicitly

[dire obsidian]

ok so basically I first consider domain given

then select n-5 or n-7 (use n-5)

then see the values that don't work under the domain

and then use them as basis to prove

[unreal stump]

Yea

[dire obsidian]

so I need to have my IH in mind by the time I do my basis step then

[unreal stump]

For 7 your basis will be {24,25,...30}

Because n-7 is less than 24 for all those

[dire obsidian]

Ok but how exactly does the induction step look like if I set n=k-5 for IH

does it actually work?

[weary tiger]

haven’t gotten an answer after more then an hr so I might as well ask here

[dire obsidian]

dude why ask right now when I'm literally in the middle of a question here

[weary tiger]

my bad

[dire obsidian]

allg

So does the induction step actually work if I set n=k-5 for IH?

@unreal stump

They used n=k-4 in the solutions on chegg so I'm confused

I hate mathematical induction so much

[quick axle]

I don't understand but you use strong induction as he said

because you're trying to prove it for Z+

and n starts from 24

The next possible integer is 29 since when i = 1 ( count), n = 24, and n + 5 = 29

[dire obsidian]

ok but does IH n=k-5 actually work?

[quick axle]

what's the bounds of k

n has to be >= 24

[dire obsidian]

same as n

how do you decide what to set as IH is essentially my question

[quick axle]

the base case

[dire obsidian]

but your base case is dependent on your IH

[quick axle]

yes and you do whatever number

is first

[dire obsidian]

what?

[quick axle]

Say you have x^n

and n >= 0

and you want to prove that when n = 1, it'll equal x

[dire obsidian]

during the actual manipulations I need to get it to actually make sense

[quick axle]

you simply show that x^0 is equal to whatever your inductive hypothesis is

[dire obsidian]

idk if n=k-5 will work

[cerulean wind]

you assume it works for all m with 24 <= m < n and try to prove it for n. to make sure that you can actually “step back” at most seven steps, you need to check the first 7 numbers from 24 to 30

[quick axle]

I think you could solve it for any multiple of 5s or 7s

[cerulean wind]

you can

[dire obsidian]

like this is the manipulation I'm talking about idk if you can do the same thing for n=k-5

[cerulean wind]

it’s at most 7 tho

[dire obsidian]

can you show me how to do it via IH of n=k-5?

I'm very confused at this thing

I hate grimaldi the textbook sucks ____s at explaining

[cerulean wind]

for n = k - 5? why?

[dire obsidian]

If I can generalize this to use IH of n-(whatever is lowest component) this is major win and would trivialize this type of question by a bunch

but idk how it works when IH n=k-5

[cerulean wind]

lowest component of what?

[dire obsidian]

in this instance it is 5

I just take k+1 = (k-5)+6-6?

see it doesn't work because we're dealing with 6s here

[cerulean wind]

what makes you think you can just write any number as sums of r, s for any integers r and s?

[dire obsidian]

the generalization doesn't work

n=k-5 doesn't work

I'm confused at what to set as my IH

can you just show me how the IS woudl look like

if you used n=k-5 as IH

[cerulean wind]

k + 1 = [(k + 1) - 6] + 6 = (k - 5) + 6

[dire obsidian]

you have 6 that doesn't work

you want component 5 and 7

[quick axle]

i don't think you can

for n = k-5

[dire obsidian]

rihgt that's what I was trying to get into

how do I determine what to use for IH