discrete-math

[honest barn]

On top and bottom

It’s just 1

Like if you take an expression

x = x * (2/2)

Because 2/2 = 1

[copper ore]

yeah

[honest barn]

It’s just that

[copper ore]

but then why did he put that there

[honest barn]

So you can rewrite it in terms of n!/(n-m)!

[copper ore]

you know the red part

[honest barn]

Dude

[copper ore]

what's the whole thing

[honest barn]

You just need to think harder

About this

[copper ore]

chill

[sick swallow]

he is trying to say that u need to think for yourself sometimes

[copper ore]

i know

i thought about it for 30 min

so i came here

[sick swallow]

bruh

[copper ore]

see

you gotta chill

why the bruhs

i will wait for someone else

[sick swallow]

u need to be more flexible or something

[copper ore]

???

[sick swallow]

when u are thinking

[copper ore]

i will wait for someone else

[sick swallow]

im just saying that it is pretty simple

[copper ore]

for you

dont understand why academia discords are so cancerous

[honest barn]

Because we’ve explained it dude

Let the green bit just be called x

[copper ore]

some people are super chill

[honest barn]

Let the thing on top of the red by called y

All he’s saying is

x = x*(y/y)

The next line he says

This is equal to (xy)/y

But y = (n - m)!

And xy is seen to be n!

[copper ore]

i

i just wanna know this

[honest barn]

I don’t know

What that even means

[copper ore]

i dont see the pattern in the red part

[honest barn]

It’s just

(n-m)!/(n-m)!

[copper ore]

(n-m)(n-m-1)(n-m-2??)

im talking about the red part

[honest barn]

That’s (n-m)! dude

Yes

The red as a whole is

(n-m)!/(n-m)!
@honest barn

Look at the top

It’s just (n-m)!

Look at the bottom

It’s (n-m)!

[low leaf]

Can anyone help with B and C

[umbral summit]

I understand i)

but I do not get ii)

online it says that you get (n choose 4) * 3

why is that

[last timber]

@umbral summit do you see why we have n choose 4?

[umbral summit]

Yeah sort of

what is tripping me up is it says 2 element subsets

is it that the vertices are literally going to be {1,2} and {3,4} for instance?

[stray reef]

yes

each vertex is labeled with two (distinct) integers from 1 to n

[umbral summit]

Okay so I looked into it more and I think I understand it

but where does the 3 come from

@stray reef

[quaint star]

For every four distinct elements a, b, c, d you choose, you can create three edges, by putting a with b, or a with c, or a with d. @umbral summit

[umbral summit]

but I thought that there was only 2 vertices for instance with each one labeled with two elements

because I found something online showing it

with only 2 vertices

one labeled {1,2}

and the other {3,4}

[quaint star]

For distinct elements a, b, c, d there are the the following three edges: {a, b} to {c, d}, { a, c} to {b, d}, and {a, d} to {b, c}

There are nC4 ways of choosing a, b, c and d. And then for each of those choices, there are 3 edges.

Hence 3 times nC4

[umbral summit]

ah okay I see now

so its not the actual number of edges

just the possible ones?

@quaint star

[quaint star]

No, those are the actual number of edges

[umbral summit]

But what about if you have only 2 vertices {1,2} {3,4} that would form an edge, but it would be only one right?

how would that be 3? because I thought the vertices are just represented by the set {1,2} for instance

At first, I thought that each number was a vertice

but then someone told me that it was actually the set that was

so from n 1 to 4 its only 2 vertices

e.g. someone showed me this

[quaint star]

You are misunderstanding. 1, 2, 3 and 4 is a choice of distinct elements. And for those elements, there are three edges. {1,2} to {3,4}, {1,3} to {2,4}, {1,4} to {2, 3}.

[umbral summit]

they just wrote the set as a number 12 instead of {1,2}

[stray reef]

that's for brevity

12 isn't "twelve" here it's "one-two"

[umbral summit]

so its actually 2 vertices 1 and 2 linked together but for brevity

for instance

[quaint star]

It's one vertex, labelled with a set of two elements.

So every vertex is labelled with two distinct numbers where the order doesn't matter, so {1,2} is the same vertex as {2,1}

[umbral summit]

so does that mean each vertex can have multiple edges linked to it?

[quaint star]

Yes

[umbral summit]

Oh okay so I see where I was misunderstanding

[quaint star]

I don't, but I'm glad you do :P

[umbral summit]

I was thinking you could only have one edge per vertex

like if you had {1,2} {3,4} I was thinking it would only be one edge because when you represent it visually there is only one line

but its actually 3 right?

because 4 choose 4 is 1 then you multiply by 3

so it would be {1,2} to {3,4}, {1,3} to {2,4}, {1,4} to {2, 3}.

[quaint star]

There is only one edge between {1,2} {3,4}. The point is you can form different vertices with the same numbers

[umbral summit]

I am not quite sure how you do that because you did say {1,2} is equal to {2,1} but how did you get that to be {1,3} for instance

how are the different vertices being formed? I assumed that they would remain the same

[quaint star]

Every vertex is a subset with two elements

{1, 2} and {2, 1} are the same vertex, because as sets they are the same set

[umbral summit]

yeah I get that

but how are you getting new elements like 1,3

since its not in the original subset for that vertice

[quaint star]

{1, 2} and {1,3} are not the same set, so they are different vertices

[umbral summit]

oh wait

I realized I missed something simple

yeah but say you have n=4 so you have 1,2,3,4 and then you choose 4 from that. Then for each vertice you choose 2 right? so it can be any choice {1,2} {3,4}, {1,3} {2,4}, or {1,4} {2,3}

so there are actually 6 vertices

not two

because 4 choose 2 is 6

I was thinking it would always be set at {1,2} {3,4} or some other combination

so no matter what you ended up with 2 vertices

not 6

[stray reef]

uhh wait hold on

hold on now

there's an edge from {a,b} to {c,d} exactly when {a,b} cap {c,d} is EMPTY, right???

because if so then both of those graph pictures are wrong!

[umbral summit]

oh wait yeah it is wrong

[stray reef]

in fact they are as wrong as they possibly could be, since they display the COMPLEMENTS of the graphs as defined!

[quaint star]

Indeed, I wasn't even looking at the picture. No wonder you are confused.

[umbral summit]

Yeah

I was like wtf is going on lol

[stray reef]

G_3 is three scattered points

[umbral summit]

someone else sent me that

and I was really confused

[stray reef]

G_4 is three disconnected edges

[umbral summit]

so say you have n=4

you should have 6 vertices correct

[stray reef]

yes

[umbral summit]

and then you get {1,2} to {3,4}, {1,3} to {2,4}, {1,4} to {2, 3}.

[stray reef]

12-34, 13-24, 14-23 are the only three edges

[umbral summit]

I see where I was confused

I was assuming if n=4 it wouldnt be like that

Okay, I think I understand it now

[stray reef]

for n=5 i think you get the petersen graph

[umbral summit]

Okay, I think I understand everything now

thank you for the help! @stray reef @quaint star

[quaint star]

Go yell at the person who gave you that picture, haha

[umbral summit]

lmao

yeah

I was stuck on this problem for the longest time

[umbral summit]

@quaint star how do you prove this

[quaint star]

Please don't ping me directly, but anyway

Use the fact that a = dq and b = dr for some q and r, then substitute that into the equation

[umbral summit]

Sorry about that

where would I go from there

to prove it is relatively prime

[quaint star]

The gcd of x and y is the smallest positive integer that can be written as a linear combination of x and y, so since 1 can be written as such, it follows immediately that 1 is the gcd

[last timber]

use euclidean algorithm

[vital dew]

Commander Vimes:

[last timber]

this can be reformulated in convenient form

[umbral summit]

Figured it out

thanks for the help

[vast mulch]

can someone tell me how they got 1/4?

[stray reef]

$\frac{4^{n-1}}{4^n}$

[vital dew]

Ann:

[vast mulch]

so n-1 is neg exponent?

[stray reef]

??

n-1 is n-1

$\frac{4^{n-1}}{4^n} = 4^{(n-1)-n} = 4^{-1}$ if you insist on being more formal

[vital dew]

Ann:

[vast mulch]

thanks ann

[orchid gust]

this is more of a computer science question but it belongs here too i guess

there's this matrix exponentiation formula for finding the Nth fibonacci number

as well as the n+1th and n-1th as you can see

i was wondering if there's a general formula like this for any c-reccurent sequence

[pale epoch]

you can do this with all linear recurrence relations

and then compute a general formula via eigenvalues

i think you can even do it in a slightly more general setting, but i lost my notes on that

[orchid gust]

i think i found something

this is the lucas sequence but it works in general

[pale epoch]

yeah, but you get big matrices really quickly

and it some point it becomes computationally heavy

[orchid gust]

wym big matrices?

[pale epoch]

like

depending on your recurrence formula, the matrix becomes bigger

[orchid gust]

you mean the dimensions of the matrix?

[pale epoch]

yes

[orchid gust]

but those shouldn't change

right

[pale epoch]

it depends on the recurrence relation

[orchid gust]

oh right

[pale epoch]

if you have something like a_n = 3*a_{n-1} + 7a_{n-2} + 42a_{n-3} + 666a_{n-4}

[orchid gust]

i thought you meant the dimension increases with respect to N

[pale epoch]

you get 4x4 matrices at least

ugh

[orchid gust]

yeah

[pale epoch]

discord formatting

i think you get it

and i think you can even solve recurrence relations if there is at most one squared term in it

in the same way

but then your matrices get even bigger

i once heard a talk on that, but either lost my notes or didnt take any

i have a book source, but its german and not translated i think so 🤷

[orchid gust]

i was writing a little program that does binary matrix exponentiation to find the Nth fibonacci term in O(logN) time

but that isn't really impressive considering there's a formula to find it instantly

[pale epoch]

moivre binet works fine

[orchid gust]

so i was trying to modify the algorithm to work for any F_0 and F_1

[pale epoch]

you can do some tricks, but not sure how fast

that's possible but not sure how fast you can compute a general formula

wait, you just have to compute eigenvalues for a 2x2 matrix

[orchid gust]

is moivre binet specific only to the fibonacci sequence? There's no general formula to find the Nth term of any Fn=Fn−1+Fn−2 relation for any starting terms?

[pale epoch]

moivre binet is fibonacci

but just modify that matrix you have

compute the eigenvalues

and then you get a similar formula from that

[orchid gust]

ight thanks

i think i got what i needed

[pale epoch]

yeah, you have to diagonalize the matrix

then you can compute the powers of the matrix more easily

and thus get a general formula

[compact shell]

Let A = {a, b, c, d}, determine the number of relations on A that is antisymmetric, reflexive and contain (d, a). You must explain your work.

Could someone explain this?

[weary tiger]

I may have a solution but it might be wrong

there are 16 elements we can choose to place in a relation on A
6 of the choices, (i,i) for i in A, and inclusion of (d,a) and exclusion of (d,a), are forced on us

not sure if this next part is right, but to count the distinct ways of including some number of the remaining 10, I split them into 2 groups, separated by antisymmetry

we can choose 0,1,2,3,4 or 5 elements of, let's call it, group 1. If we choose 0, there are 2^5 choices for group 2. If we choose 1 from group 1, there are 2^4 choices, and 5 ways to choose 1, so 5*2^4 total. This can be done in a similar way for the remaining cases and summed up

so $\sum_{n=0}^5 {5\choose n}\cdot 2^{5-n}$ maybe

err

[vital dew]

Botn:

[weary tiger]

@compact shell

[compact shell]

Hmm, I see. Thank you

[obtuse lance]

it's worth mentioning that this simplifies to (1+2)^5

[weary tiger]

would relationship "mod 2" have 2 equivalence classes

[0] and [1]

because they would be the only two possible remainders

[weary tiger]

Thanks

[umbral summit]

Is induction technically a type of contradiction?

I saw a problem that is easy to prove by induction

but it says hint: by contradiction on it

The problem in question

@worthy palm

I seriously doubt induction counts as contradiction

but I am unsure about how to use contradiction in this case so I am just hoping it does by some technicality

Yeah figured

How would I do it via contradiction though

this is where I am confused

I know I would have to prove deg r < deg b is not true

but I am not quite sure how to go about that

wouldnt it be deg r >= deg b

what is the ' for

Take polynomials q and r such that the degree of r is minimal
for this do you mean like making up an example?

for p and f do you mean a and b

oh okay

I am a bit loss though as I am new to this stuff. How would I take polynomials q and r such that the degree of r is minimal? Also, thanks for the help

Oh lol

I thought I would have to prove it or something

I did this so far

does this look about right

How would I find the polynomial p and f though

or can I just state

Let $p$ and $f$ be polynomials such that $a = pb + f$ and deg f $<$ deg r.

[vital dew]

Kori:

[errant bear]

the second line is weird, you should just say "let deg r >= deg b"

[umbral summit]

This is what I changed it to

but I am not sure how to proceed from here

oh wait

when you said the degree of r is minimal

you didn't mean less than

you meant its the smallest possible r that fulfills the equation

But how do you find p and f?

Are you just stating it

smaller degree than b you mean

oh

but how would you manipulate a = qb + r into that?

Yes

but how would that help?

oh wait

what is the c from?

so it would be a-cb = qb + r -cb

Also what if the degree of r is more than b

in that case

it wouldnt subtract the leading right?

ah okay

[obtuse siren]

How would I go about solving this...

im not taking a class, I actually am studying some topics from other discrete courses because I found out the one I took last spring was kind of pathetic, and the relations stuff we did looked nothing like this

so honestly idk where to start

like some of it is familiar to me

a lot of the terminology in relations questions at other universities was not covered in my course

granted I got an A in my discrete course and this just looks like nothing I've seen...

Like maybe 85% of the symbols used I know, but the terminology is a foreign concept to me

like poset as an example

[umbral summit]

nvm I fixed everything and got help

[weary tiger]

If I have to pick 12 bagels, from at most 4 bagel types. Given there are 20 bagel types. How many possibilities are there

can someone help me with this ^

I got 1^12+2^12+3^12+4^12. aka case with 1 max bagel type, 2 max bagel type, 3 max bagel type, 4 max bagel type. but this doesn't seem right given it would need a combination with 20 total types

[sick swallow]

i did it quickly, but i think it is (20C4)times (15C3)

the first bit in choosing the bagel types, the second being how many ways to partition 12 into 4 groups, (allowing a null set)

[twilit bolt]

Please help me in this question

[sick swallow]

it is because n and m are integers

so it doesnt make a difference if x has decimal places as the floor will be the same

[upper tide]

If I have the sequence (1,1,1,1,...) the generating function is: 1/(1-x)
and if I want to shift it right once to add a leading 0, as in sequence (0,1,1,1,...) does that mean the generating function will be x^1/(1-x)? because we multiply 1/(1-x) with x^1 to shift it once to the right?

and how does the sequence (0,2,2,2,2,2,2,0,0,0....) give me (2x(1-x^6))/1-x?
I end up with 2x(x^1+x^2+x^3+x^4+x^5) and dont know what to do next

[obtuse minnow]

(0,2,2,2,2,2,2,0,0,0 ...) is (0,2,2,2,2,2,2,2,2,2,2 ...) minus (0,0,0,0,0,0,0,2,2,2,2,...)

Oh ... that is the same thing I think...

[west hedge]

@upper tide all you're missing is to use (1 - x) * (1 + x + x^2 + x^3 + x^4 + x^5) = 1 - x^6
except you also seem to have omitted the constant term inside the parentheses in your last message

[upper tide]

Yes, you are right.. the constant term got lost in the confusion. And thanks!

[dim sapphire]

this notation appears in my text, but doesn't explain it. i made up an example, can someone write out the explicit expression so I can understand what it means? let + denote OR, let * denote AND and and let [i=1 to n] represent the index i ranging from 1 to n. Then, can someone show me what this expression is written out completely: +[i = 1 to 2] *[j=1 to 2] +[k=1 to 2] p(i,j,k)?

[stray reef]

(p(1,1,1) or p(1,1,2)) and (p(1,2,1) or p(1,2,2)) or (p(2,1,1) or p(2,1,2)) and (p(2,2,1) or p(2,2,2))

[dim sapphire]

thanks for answering, taking the time to carefully look at this

[dim sapphire]

@stray reef I now understand it, thank you!

[near quartz]

is there a formula or theorem that exists for 1b

[wintry schooner]

hey guys

n(n + 2)(2n − 1) ≡ 0 (mod 3) for any natural number n

how would I show that this argument holds?

im new to discrete maths so any help or guidance would be appreciated 🙂

i need to argue why this following statement holds

i assume I would have three cases? 2k, 2k+1, 2k+2?

not sure :/

[delicate ridge]

i mean a "brute force" way is to use induction

[quaint star]

If any one of the three factors ie congruent to 0,then the product is too

[honest barn]

If n = 0 mod 3 you're done from the first bit, if n = 1 mod 3 then you're done from the n + 2 term, so you're left with n = 2 mod 3

[quaint star]

So consider n congruent to 0, 1, and 2 as separate cases, and show that one of the factors is always congruent to 0

[near quartz]

@delicate ridge did u reply?

[delicate ridge]

yeah sorry misread the question the first time @near quartz

ok, so we have the following setup: f needs to map 2 to some intermediate number which maps to 3

f(2) = x, f(x) = 3

[wintry schooner]

@quaint star so would I choose n = 3k, 3k+1, 3k+2 and substitute into the formula and expand?

[delicate ridge]

there are 4 possible values that x could be, since x cannot be 2

now fix f(2) = x; this means there are 3 other values we need to define the mapping for

[quaint star]

Chmonkey basically wrote out two of the cases for you, you just have to do the last one. You don't have to explicitly write out n in that form, but you can @wintry schooner

[delicate ridge]

there are 5 possible options for each

[near quartz]

could you also do f(a) = 3 for a e A and just use this constant function?

[delicate ridge]

so there are 5^3 potential functions for a given x

[near quartz]

there are 5 possible options for each
@delicate ridge how did u determine that

[delicate ridge]

5 possible values an element in A could map to

so to give a specific example, we can say that x (ie. f(2) ) is 4

i could have said x is 1, 3, 4, or 5, but ill say 4 for examples sake

so we know what f(2) is (ie. 4), and we know what f(4) is (ie. 3)

now we need to define f(1), f(3), and f(5)

f(1) could be any of 1, 2, 3, 4 or 5

likewise for f(3) and f(5)

so there are 4 choices of x, 5 choices of f(1) and 5 choices each of f(3) and f(5)

4 * 5 * 5 * 5 = 500

[near quartz]

i get you but what I'm not understanding is how why f(2) and f(4) have only one choice. Is it because f(2) = 3, but then what about f(4)?

[delicate ridge]

f(2) isn't 3

f(f(2)) is 3

[near quartz]

but to get f(f(2)) to be 3 doesn't f(2) have to be 3 as well?

[delicate ridge]

nope

[near quartz]

so lets say f(2)=4 and then f(4) = 3

that's what you're saying right

[delicate ridge]

yep

[near quartz]

but then why is there only 4 choices instead of 5 for x

[delicate ridge]

see if you can tell me

[near quartz]

couldn't u use any element

[delicate ridge]

which value doesn't work for f(2)

[near quartz]

2

[delicate ridge]

why?

[near quartz]

i think its because if f(2) = 3 then f(f(2)) will be f(3) = not 3 since each element in the function can only have 1 output

but then my question is if that is the case

wouldn't there only be 1 choice for x instead of 4?

so it should 1 x 5 x 5 x 5

[delicate ridge]

no, you had the right answer but got confused

you said the value of f(2) that doesn't work is f(2) = 2

the question requires f(f(2)) = 3

so what's f(f(2)) if f(2) = 2?

[near quartz]

f(f(2)) = 2 if f(2) = 2

[delicate ridge]

yep

[near quartz]

is that correct or am i completely lost

[delicate ridge]

f(f(2)) = f(2) = 2

which wont do

but its fine, we can just say that f(2) = x, where x is one of 1, 3, 4, 5

[near quartz]

ah

thats why there's only 4 choices

[delicate ridge]

once we've picked an x, we're locked into saying f(x) = 3

[near quartz]

thanks, and I have another question regarding this one

what if we're asked how many one to one functions there are from f: A->A that are also fof(2)=3

1-1 means that if f(x) =f(y) then x=y but how do you show that

[delicate ridge]

try working through it like i did

start with f(2) = x for some x (not 2)

f(x) = 3

since f is injective, x =/= 3

otherwise both 2 and 3 would map to 3

[near quartz]

for the 1-1 am i trying to get f(x) = x?

[delicate ridge]

no?

think carefully about what one to one is

you don't want any elements to be "over crowded"

if 2 -> 3 -> 3, then two elements are mapping to 3

ie. f(2) = f(3), but 2=/=3

[near quartz]

i know onto means that every element in the codomain gets hit so is 1-1 every element in the domain has only 1 mapping?

isn't it just trying to say f(x)=f(y) so f(2)=f(2) so x=y 2=2?

[delicate ridge]

just take it slow

we're trying to work out what possible values f(2) can take

can f(2) be 2? no, because f(f(2)) wouldn't be 3

[near quartz]

every value but 2

[delicate ridge]

can f(2) be 3? also no, because then f(2) = 3, and f(f(2)) = 3, meaning f(3) = 3

but we then have f(2) = f(3), with 2 =/= 3

[near quartz]

yes i got up to that much 😆

[delicate ridge]

so f(2) can only be one of 1, 4 or 5

[near quartz]

ok, and just as a hypothetical lets say the question was fof(2)=4, then f(2) could only be 1,3, or 5 right?

[delicate ridge]

aye

[near quartz]

so f(f(x)=y, then f(y) and f(x) are not possible, which is a contrapositive of the definition of one to one right?

so f(2) can only be one of 1, 4 or 5
@delicate ridge so is it correct to say there's only 3 one to one functions or 5^3?

[delicate ridge]

There are three options for f(2) if f is one to one

Call that number x

So we have defined f so far as f(2) = x and f(x) = 3

We have three other numbers we need to define

The first one has three possible values that it can be mapped to (since it cannot map to x or 3)

Then the next has 2 remaining options

Then the final one has 1 option

Say f(2) = 4

Then f(4) = 3

We need to define f(1), f(3), f(5) still

f(1) can be any of 1, 2 or 5

If we choose f(1) = 5, then f(2) can be either 1 or 2

Etc etc

[near quartz]

So 3!

[viral sphinx]

hi i need help on this..

Supposed you were hired by a company at an initial salary of RM24,000 per annum. At the end of each year, you would receive a 3% raise, but RM1000 will be deducted automatically from your annual salary by your company to pay your study loan. The total amount of money after the deduction would become your annual salary for the upcoming year. Let equal your salary at the end of n years with the company.

Determine a linear recurrence relation to represent your annual salary at the end of n years with the company

[ a_n =(1.03) a_n-1 - 1000(n)] i did try this but the salary for next year keep decreasing.. so ithink y=this formula is wrong?
Can someone help me fix>? thank you

[last timber]

@viral sphinx why you have -1000n?

[viral sphinx]

because every year 1000 will be deducted so -1000n where n reppresent year. no?

[last timber]

why

it would imply that on second year 2000 will be taken

on 10 - 10000

on 50 - 50000

which is not 1000 every year

[viral sphinx]

ohh.. i get it ..

so theres no need to times by n right?

[stray reef]

the problem as written is kinda ambiguous

like

[viral sphinx]

[ a_n =(1.03) a_n-1 - 1000]
so is this what it become?

[stray reef]

in year 1 you earn 24,000

in year 2 you earn 24,720 pre-deduction but 1k goes towards your loan

so is the next 3% raise applied on the 24,720 or the 23,720

[viral sphinx]

23,720 will be applied..

[stray reef]

the salary just keeps getting smaller
sounds like a ripoff to me

[viral sphinx]

i know thats why im confuse with the ques

[stray reef]

it's not your fault, the question's wording is confusing

[honest barn]

It's student loans, they are the true evil in this equation

[stray reef]

what i'm saying is the raise doesn't cover the deduction

unless, of course, the raises are always applied on the PRE-deduction amounts, and the amount received is just a constant 1k lower bc of the loan

[honest barn]

yeah, but it says the new years wage is the pay, after deduction which seems to imply the other way around

but then I'm inclined to say the problem as stated isn't what the person who wrote it intended

[stray reef]

but we're not here to guess intentions

malicious compliance says the salary will just keep getting smaller at an ever-accelerating rate

in 28 years it'll be half the starting salary, and in 44 years it'll be negative!

[honest barn]

I mean, sure, but you also have to consider if there was a mistake in transcribing the problem

[last timber]

just typical work IRL

[honest barn]

I'm somewhat doubtful that this is actually what the problem wanted

[stray reef]

ah yes negative salary

[obtuse lance]

this mathematical model is so powerful it even predicts extreme political change, very cool

[stray reef]

??

[half heart]

[viral sphinx]

but then I'm inclined to say the problem as stated isn't what the person who wrote it intended
@honest barn

i think so too..

btw thank you guys

[vast mulch]

can someone explain how they derived the area in the red box? i dont get how it got expanded

[stray reef]

$(n-1)! = (n-1) \times \underbrace{(n-2) \times (n-3) \times \dots \times 2 \times 1}_{(n-2)!}$

[vital dew]

Ann:

[stray reef]

@vast mulch does that explain it?

[vast mulch]

where does the (n-2)! from the numerator come from?

[stray reef]

??

i just showed you

did you misword your question?

[warped rivet]

ok

@vast mulch

Perhaps looking at some values may help

We read n! as "n factorial", so n! is n(n-1) ... 1

What this means is if I take an integer n

and I say n factorial

I multiply n with all the numbers before it

So for example

4! = 4 * 3 * 2 * 1

or 8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

[stray reef]

they ghosted me :|

[warped rivet]

I'm able to write 8! as 8 * 7!

rip

[weary tiger]

maybe he got scared

and ran

[stray reef]

am i really that intimidating??

[last timber]

tbh, for some people your manner of writing may seem somehow aggressive

[stray reef]

how

[last timber]

well, maybe it is only me, but sometimes your messages look as written with a lot of annoyance behind them

[warped rivet]

I think, in that particular instance, Ann didn't display that

[stray reef]

is it because i don't follow the unspoken social rule of "beat around the bush for an exact but unspecified period of time"

[pale epoch]

people will interpret "did you misword your question?" and such as mockery

although i think he never read that and was gone before

[lyric pumice]

Hi. Combinatorics can be intimidating.

Or maybe he figured things out and then promptly left.

Some people are just in a hurry.

[warped rivet]

yeah uh

probs cramming

[stray reef]

people will interpret "did you misword your question?" and such as mockery
????

the fuck?

[weary tiger]

where does the (n-2)! from the numerator come from?
@vast mulch

followed by

??
i just showed you
@stray reef

My guess is I think that response kinda rubbed him the wrong way maybe. It seems that you responded that way because you couldn't believe that he wasn't understanding what you just explained, making him look dumb perhaps. In that instance maybe it would have been better to further clarify, or asking for clarification as to what he was not understanding.

[warped rivet]

[vast mulch]

relax guys I wasnt intimidated just had to Youtube videos on how to simplify factorial coz i didn't know what Ann meant but I understand it now

[warped rivet]

epic

99!/98! = ? @vast mulch

[stray reef]

next time let me know you're off to watch some videos or whatever

please

so that i don't get left in the dark

[warped rivet]

👻

[vast mulch]

99*98!/98!?

[warped rivet]

which simplifies to?

[vast mulch]

99!

[warped rivet]

No.

Try again.

[stray reef]

i think the ! there might have been an exclamation mark

and not a factorial symbol

[warped rivet]

oh

lol

fair enough

[stray reef]

i tend to put a space before the ! if i use it that way next to a number

so as to disambiguate

[warped rivet]

thats a nice convention

[vast mulch]

wait its not 99!?

[warped rivet]

No.

[vast mulch]

99?

[warped rivet]

Yes.

Now tell me why

[stray reef]

99! divided by 98! surely isn't 99! again...

[warped rivet]

:/

[vast mulch]

ok that make sense

[warped rivet]

Same way how 5!/4! = 5 right

or 5!/3! = (5 * 4 * 3 !)/3! = 54 = 20

sorry

5*4

not 54

[twilit bolt]

it is because n and m are integers
@sick swallow Thanks

[vast mulch]

can someone confirm if i'm doing this right?

[warped rivet]

wouldn't it be

pi/6 -2n

this needs to be verified though

i'm sleep deprived rn

[vital dew]

alpacatrain:

[warped rivet]

yeah

i think he's thinking 6 steps to get to (pi/6) -6

[vital dew]

Commander Vimes:

[weary tiger]

ye also got (pi/6) - 2(n-3)

[vast mulch]

oh yeah forgot -2

is there a trick to finding out the general formula? i'm staring blank at the screen at times :/

[weary tiger]

idk about general, but in this specific case since the change is linear, it suffices to subtract a certain t_n with t_n-1 to see the pattern, for instance t_6 - t_5 u get -2 as the difference, meaning that going from t_5 to t_6 only a -2 was added. Same goes for from t_4 to t_5, a -2 was added, so we found a pattern

and then for writing up the general formula we always have pi/6, so that stays constant, but a -2 is always added at each consecutive n, so usually it would be -2n, but since we are beginning at n = 3, then we subtract with 3, so therefore 2(n-3)

i feel like for harder problems you just have to experiment and be creative

oh it says n > 3 in the exercise, so I guess it would be (pi/6) - 2(n-4) then

[pallid lintel]

hey are complex numbers or analysis used in graph theory or matroids at higher levels? (yes i realize all real numbers are complex, i mean with nonzero b in (a+bi)). I've chosen to study lots of algebra and number theory first.

how much though? i've only encountered basic topology so far, things like metric spaces/open balls. No complex yet

[soft bobcat]

Starting on the 19th, I'm officially taking discrete math c::

[molten quail]

Good luck @soft bobcat

It’s a fun class

[small kayak]

Can someone please guide me through this problem ?

[stray reef]

two proofs huh

[quaint star]

Lol, obviously induction is dumb

[small kayak]

Yeah two proofs. I have found out one way is to group them into pairs

[stray reef]

i think a combinatorial proof could be made here

[small kayak]

Like C(n, 1) + (n - 1) * C(n, n -1) + ...

[stray reef]

but im not sure

[small kayak]

But i don't know how to make a combinatorial proof

[stray reef]

hm.

oh hold on

okay this is gonna take me some time to phrase in a way someone other than me could understand

[small kayak]

Okay

[stray reef]

ah yes

say you have n people and you need to pick some of them for a team. the team can be any size but it has to have a captain (a role not interchangeable with other team members). how many ways can you do this?

on the one hand, you could first decide on a size (say k), pick that many people in one of C(n,k) ways, and then appoint one of those k people as the captain
add up k * C(n,k) for k from 1 to n and you have your LHS

on the other hand, you could first pick the captain in one of n ways, then have the captain pick a subset of the remaining n-1 people for her team, potentially allowing her to pick no-one and go it alone. this gives the captain 2^(n-1) options

[obtuse lance]

one proof I'd give is the calculus proof

[stray reef]

[obtuse lance]

differentiate (1+x)^n lol

[small kayak]

Ok let me try differentiating (1+x)^n

[stray reef]

rip my combinatorial proof

[small kayak]

Tks a lot Ann i understand your combinatorial proof

Tks for your help

[weary tiger]

differentiate (1+x)^n lol
This is a nice one

[obtuse lance]

makes deriving the expected value and standard deviation of the binomial distribution a breeze

[stray reef]

anyone wanna hear a nice combinatorial proof problem?

Given $k$ positive integers $n_1, n_2, \dots, n_k$, prove that $$\binom{N}{2} = \sum_{i=1}^k \binom{n_i}{2} + \sum_{1\leq i < j \leq k} n_in_j,$$ where $N = n_1 + n_2 + \dots + n_k$.

[vital dew]

Ann:

[stray reef]

there's a nice combinatorial argument to be made here

[honest barn]

Wait so this is for any k sized partition of N?

This seems completely whack wtf

Also what if an n_i = 1

Do we treat n_i C 2 as 0?

[stray reef]

yes

[honest barn]

This seems really hard lol

[stray reef]

there is a very elegant purely combinatorial argument

[honest barn]

Something something, how many ways to pick a team of two from N people

[stray reef]

yes

partition the N people into k groups of sizes n_1, n_2, ..., n_k

[honest barn]

Yeah I figured that much

[stray reef]

then ||consider whether the two you are picking are from the same group or not||

[honest barn]

There’s a lot hidden in those double | |

But surprisingly also so little

[stray reef]

yes

here's another nice one: $$\sum_{0 \leq j \leq k \leq n} \binom{n}{k} \binom{k}{j} = 3^n$$

[vital dew]

Ann:

[stray reef]

actually here's the same one on steroids:

nvm

[last timber]

best proof ever /j

[rain stone]

Those combinatorial proofs were really really nice

[soft bobcat]

Are there any tips for this class that I should know? (I'm coming from Calculus BC)

[last sigil]

In discrete, you will probably have to prove things, unlike in Calculus BC

While it sounds intimidating, you will get the hang of it with practice

[molten quail]

Are there any tips for this class that I should know? (I'm coming from Calculus BC)
@soft bobcat I did it, it wasn’t bad. Most proof techniques are taught in the beginning, you’ll be fine

[soft bobcat]

Alright, thanks!

[wintry schooner]

hey guys how do i do this? like how do i go about it

Let A, B be sets. Show the following is true

P(A ∩ B) ⊆ P(A ∪ B).

[last timber]

is P power set of what

@wintry schooner

[stray reef]

assuming P means powerset, have you already shown that X \subset Y implies P(X) \subset P(Y)?

[wintry schooner]

yeah P means powerset

im not sure how to show this statement is true

and no i havent shown that @stray reef

[stray reef]

maybe show that then, it'll be a bit easier

once you do, you'll be able to apply it as long as you're able to show $$A \cap B \subseteq A \cup B$$

[vital dew]

Ann:

[wintry schooner]

oh okay interesting

[hollow bloom]

To show two graphs are not isomorphic this website tells me a few ways

But what does it mean by showing different number of connected components?

[quaint star]

A connected component of a graph is a subgraph where every two vertices in the component has a path between them

So if I have a graph of seven vertices where 3 of the vertices are connected to form a triangle and the other 4 to form a square, then the triangle and the square are the connected components

[hollow bloom]

I see

Thank you so much!

So if they don’t have the same connected components

Then the two graphs are definitely not isomorphic right?

Like one have a triangle circuit

And the other one have a square circuit

Then they are definitely not isomorphic right?

[quaint star]

Well here they just say that if the graphs don't have the same number of connected components, but I imagine if the components aren't the same, it's true as well

[hollow bloom]

Gotcha

👌 Thanks!

[hollow bloom]

@quaint star Hi Lunasong hope you don't mind if I ask an example to clarify

Like for this one, I first mapped a to 1, then I looked at the adjacent vertex since it must be preserved if it is isomorphic. I mapped h to 8, b to 2, but on the right graph 8 to 2 have a edge but h and b doesn't so does this mean that these two graphs are not isomorphic?

Can I argue it like that?

[pale epoch]

you cannot

it just means that the map you constructed is not a graph isomorphism

[delicate ridge]

you could probably develop that into an argument by considering the symmetry of each graph

[pale epoch]

ye, probably, but you have to consider more cases

like, mapping a to 1 WLOG is fine due to symmetry, but then you need to argue a bit more

[hollow bloom]

If you have time do you mind walking me through this problem

Because if what I said cant' be used to argue isomorphism

Then yikes I think previous problems I did the same

[pale epoch]

showing that 2 graphs are not isomorphic can generally be pretty hard

often you can argue thst graph A has a vertex of degree n, adjacent to a vertex of degree m, and graph B does not or something along those lines

doesn't help for this particular example though

you can turn your argument into a correct one though, i think

[copper ore]

I dont get the P(s) = {T : T <= S} part

what is it saying?

[quaint star]

Sorry for the late reply. Like the others said, your argument isn't quite valid because you assume a is mapped to 1 when it could be mapped to any number.

@hollow bloom

[pale epoch]

thats not the issue, you can assume that, the other assumptions are not valid though

like, what if you map b to 3 instead

@copper ore its what the sentence above says but in set builder notation

[quaint star]

I mean, you can assume that, but you should at least address the symmetry. But you're right, that's not the main issue

[copper ore]

oh yeah i get it now

[quaint star]

I'm also not really familiar with showing graphs are or aren't isomorphic, so I'm not exactly sure how to fix your proof

[hollow bloom]

Oh :/

All good

I just wish my textbook have more examples

[pale epoch]

i tried to find an argument in my head, but its too much to consider

I'm not entirely convinced those graphs are not isomorphic

but maybe I'm missing something easy

[quaint star]

It looks as though the graph on the left has no closed paths of length 3 while the one on the right does

[pale epoch]

ah, that would work

[hollow bloom]

How about 2 circuit of length 4

With unique vertex

Is it easy to find that?

And yea Lunasong I think that is a good catch

[quaint star]

But, yeah, lol, it's difficult to see. I convinced myself for a while they were isomorphic

[hollow bloom]

Damn

Alright I gotta look back at some of my problems

So I can't just

[quaint star]

Good luck

[hollow bloom]

Like do what I said

Like for this one, I first mapped a to 1, then I looked at the adjacent vertex since it must be preserved if it is isomorphic. I mapped h to 8, b to 2, but on the right graph 8 to 2 have a edge but h and b doesn't so does this mean that these two graphs are not isomorphic?

This one

I can't do this?

[pale epoch]

no

[hollow bloom]

👌

[pale epoch]

as i said, what if you instead map b to 3

[quaint star]

You need to consider/address all possible cases if you do that, which would be lengthy and difficult

[hollow bloom]

I see

[pale epoch]

in general graph isomorphism is NP

[hollow bloom]

But there are algorithm that can solve it?

[pale epoch]

sure

you can in theory look at all the maps between the graphs and check

for finite graphs at least

[hollow bloom]

I see

and one more thing

adjacency is preserved under isomohpism right?

like the neighbors will be the same

[pale epoch]

yes

thats kinda the definition of graph isomorphism

[hollow bloom]

yikes im dumb 😦

Alright thank you so much!

❤️

no homo

[lyric pumice]

Hi, can anyone simplify this?

[stray reef]

uhh

what values of h, d, f and r are even admissible here

@lyric pumice are you sure that's the thing you want simplified?

bc this looks like some sort of nasty over-generalization attempt

let's throw it into WA

,w sum[j=0,h] C(d,j) * C(f-j,r)

[vital dew]

Results provided by WolframAlpha

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

Requested by Ann#0413

[stray reef]

YIPES

[leaden pebble]

oh yes, a nice simplification

[warm gyro]

discrete mafs gud

[west hedge]

Just out of curiosity, did anyone ever figure out whether those two graphs are isomorphic? @hollow bloom

https://cdn.discordapp.com/attachments/496785905474994186/745360879104557096/unknown.png

[hollow bloom]

Oh it wasn’t isomorphic

That’s at least what we concluded

Yesterday

[west hedge]

Why?

[hollow bloom]

What I did was I picked out the sub graph of the neighboring vertex of a

Like first I mapped a to 1

Then I looked at all the neighbor vertex of a

Which is h, f, e, d and b

Then I find the vertex induced graph of all these vertex

And do the same for the right graph

Then compare them

Find the sub graphs aren’t isomorphic

Hence the original graph can’t be isomorphic either

Did that make sense?

[west hedge]

Let me think about it for a minute, I don't really know the subject off the top of my head xD

[hollow bloom]

Ay

I just started as well

Sooo yea I’m just basing off what I read on textbook and what others said

[west hedge]

Okay so what it comes down to is that a has a neighbor (e) that neighbors all four of a's other neighbors (b, d, f, h)

But each of 1's neighbors is only adjacent to two other neighbors of 1

Right?

[hollow bloom]

Yes sirrr

That’s what I got

[west hedge]

Nice that makes sense 😄 I thought about it for a while yesterday but couldn't come up with anything so it's satisfying to finally find a solution

[hollow bloom]

👍

Ye I know that feeling Xd

[serene basalt]

first graph has 8 cycle, 2nd graph has no 8 cycle

in fact it can be seen easier still, the first graph is connected, the second graph is 2 separate components

[pale epoch]

are we looking at the same graphs?

you can just go around the "circle" part

[serene basalt]

i didn't realize the circle was part aof the graph

[lyric pumice]

@stray reef Hi. The issue has been resolved.

[stray reef]

oh has it?

[last timber]

@novel spire but it has wheel as a subgraph so it is not tree by definition!

[serene basalt]

first graph connects each node to that node {+1,+3,+4,+5,+7} (mod 8), second is {1,2,4,6,7}

could we use this idea to prove they are non isomorphic?

[last timber]

you are doing that?

nvm idea failed

[serene basalt]

yeah

thats how i represent the graphs

now can I calculate an invariant?

[last timber]

@serene basalt hm look
a -> b -> c -> d and 1 -> 5 -> 7 -> 8 but betweed 1 and 7 there is direct edge and between a and c there is no

mb this is key

[serene basalt]

I am looking through wikipedia graph invariants: These gaphs have the same order, size, connected components, diameter, girth, clique number!

https://en.wikipedia.org/wiki/Vertex-transitive_graph

[pale epoch]

they're even circulant

[serene basalt]

they have the same chromatic number

6

https://en.wikipedia.org/wiki/Circulant_matrix

can we quickly compute any graph invariants from the fact its circulant?

[pale epoch]

yes

[serene basalt]

I will try

[pale epoch]

you can solve graph isomorphism in quadratic time

due to a result by

uh

muzychuk

[serene basalt]

? f(x) = x^1 + x^3 + x^4 + x^5 + x^7
%1 = (x)->x^1+x^3+x^4+x^5+x^7
? g(x) = x^1 + x^2 + x^4 + x^6 + x^7
%2 = (x)->x^1+x^2+x^4+x^6+x^7
? prod(i=0,8-1,f(exp(2*I*Pi/8)))
%4 = 1.0000000000000000000000000000000000000 - 2.350988701644575016 E-38*I
? prod(i=0,8-1,g(exp(2*I*Pi/8)))
%5 = 0.00086655177722008891100052244318394357381 - 4.918364879128313671 E-41*I

is this valid?

https://en.wikipedia.org/wiki/Circulant_matrix#Determinant used this

[pale epoch]

i guess

interestingly, there is no other graph isomorphic to the first one

and there is one other graph isomorphic to the second one

(if you don't allow relabeling of the vertices)

i just recalled that i have classified all circulant graphs up to order 20-ish at one point

and i just checked my data

yeah, up to order 20

[serene basalt]

what do you mean no other graph isomorphic to it?

[pale epoch]

the automorphism group is trivial

[serene basalt]

the automorphism group includes the 8 cycle

it can also be flipped

it seems actually the graph on the left has an automorphism that the graph on the right doesn't

[pale epoch]

oh yeah, but other than this trivial case

actually let me rephrase

you can characterize a circulant graph if you fix a vertex and just consider the adjacent vertices of that one

you call that the connection set and consider two circulant graphs different only if they have different connection set

so ignore the cyclic subgroup of the automorphism group

[serene basalt]

with some help I put these graphs into GAP/GRAPE and computed their automorphisms

the first has order 2^7 and the second has order 16 (it's D_8)

this is the first invariant i found which differentiates these graphs

was really interesting how hard it is to separate them

in the end using a computer is basically cheating too

[hollow bloom]

If a graph G has n vertices, all of which but one have odd degree

This can't be possible right?

[quaint star]

@hollow bloom It is indeed not possible, can you explain why?

[hollow bloom]

Like I read

In my textbook saying that the sum of all degrees in the graph

Is equal to twice the number of edges

So if all but one is odd, and rest is even

Then we can write 2n+1 = 2y

Where n is number of even vertices

Y is number of edges

But that can never be true

[quaint star]

Yeah, exactly, so the sum of the degrees must be even

[hollow bloom]

I see

👍

But like here is the problrm

The problem ask how many vertices of odd degree are there in g complement

But if I can never make the graph

Is there a complement?

[quaint star]

Does the problem say only one vertex has odd degree?

[hollow bloom]

Yea

[quaint star]

That's strange.

[hollow bloom]

And I think one big hint I found online

Is using the formula n-1-d to find the degree on the complement graph

For that vertex

Where n is number of total vertices and d is degree for that vertex

[quaint star]

Yeah, can I see the exact problem?

[hollow bloom]

Yea of course

[quaint star]

That's the opposite lol

All of them are odd, except one is even

[hollow bloom]

WOT

[quaint star]

It's not the one that has odd degree, but the all of which but one

So all have odd degree, but one.

[hollow bloom]

OHHH

shit my english is failinig me

[quaint star]

Haha, it's okay. Good on you for spotting it would be impossible though

[hollow bloom]

yikes

alright lemme solve this real quick

Okay took like 15 minutes

But I think it is n-1 odd vertices

Even in the complement graph

[pliant horizon]

if A={1,1,3} and B={1,3,3} does A=B? And what is the cardinality of A and B?

[quaint star]

@pliant horizon what do you think?

[pliant horizon]

I think they are equal

[quaint star]

Yes

[pliant horizon]

I'm irritated that the definition of cardinality in my text does not specify whether or not the elements are distinct. So I want to say 2, but I'm not sure.

[quaint star]

The definition of cardinality might not, but the definition of set should

Sets can only contain an element once, so {1,1,3} is just {1,3} so even when you talk about the number of elements, there are only 2

[pliant horizon]

Okay yea that's what we were thinking. So when we take cardinality of a set X, we evaluate that on the set equal to X with the fewest number of... entries?

as in if X={1,1,1,1,1,1,3}, Y={1,3}. X=Y and |X|=|Y|=2

[quaint star]

{1,1,3} is shit notation. The set only contains two elements, 1 and 3. It's not that it's equal to some other set with fewer elements. It's the same set, here it's just written in a way to confuse you

as in if X={1,1,1,1,1,1,3}, Y={1,3}. X=Y and |X|=|Y|=2
@pliant horizon Yes

[pliant horizon]

right thats why i didnt want to say different number of elements. i guess my question is then what is the difference/distinction between {1,1,1,1,1,1,3} and {1,3}? i want to say entries but idk

[quaint star]

There is none

They are different representations for the set containing the elements 1 and 3

[pliant horizon]

okay so only visually different but mathematically identical

[woeful spire]

Anyone available to step me through an RSA decryption question?

[sour arrow]

Go for it

[woeful spire]

I'm fairly sure it's basic but I get to a point each time I'm going through it where I get lost. I'm given pq = 65, e = 7, and I need to decrypt the cipher text 57 9.

Without telling me the answers at each step, can you tell me the general steps I go through to find that?

[compact loom]

how do I verify whether numbers are divisible without a calculator

e.g.

2|107, 3|107, 5|107, 7|107

nvm

[copper ore]

i don't get this

why is it 5 choose 3

not sure

umm like why is it 5 choose 3 exactly haha

i got roasted in another discord for asking this question hoping i dont get roasted here 😅

oh i see

and there are 10 possible ways to do that?

yeah

im just really trying to understand how they are doing the binomial theorem stuff

[lyric pumice]

When you expand (x+y)^5, the x^2 * y^3 term appears due to mixing of the x and y terms among different factors. In how many ways are x and y multiplied to give the term x^2 * y^3? Where in the expansion do these multiplications occur?

@copper ore

[copper ore]

x * x and y * y * y

The goal is to count how many
oh okay

that seems like a hard thing to do though?

is there a trick to use

[waxen bear]

can someone help me with a problem I have come to an answer but not sure if my approach is flawed

its a very easy problem

[lyric pumice]

If you can multiply by choosing choose either an x or a y from each of the five x+y factors , how many ways can you choose 2 xs and 3 ys? @copper ore

[waxen bear]

is this 10 or am i dumb

[lyric pumice]

You are smart.

@waxen bear

[waxen bear]

thank u so much

[copper ore]

sorry i was eating

back now

If you can multiply by choosing choose either an x or a y from each of the five x+y factors , how many ways can you choose 2 xs and 3 ys? @copper ore
@lyric pumice 20?

10 + 10

[lyric pumice]

Start by looking at (x+y)^5=(x+y)(x+y)(x+y)(x+y)(x+y).

[copper ore]

yeah

[lyric pumice]

Count the number of ways you can pick xs and ys from the factors.

[vital dew]

slimvesus:

[lyric pumice]

For example, x,x,y,y,y ; x,y,x,x,y ; y,x,x,y,x ; etc.

@copper ore

[copper ore]

slimvesus:
@vital dew ya

For example, x,x,y,y,y ; x,y,x,x,y; y,x,x,y,x; etc.
@lyric pumice i have no idea tbh

[lyric pumice]

Multiplication means that the xs and ys must get distributed among each other in all possible ways.

For example, you can take x from the 1st factor, y from the 2nd factor, y from the 3rd factor, y from the 4th factor, and x from the 5th factor.

Multiplying them gives you x^2 * y^3.

[copper ore]

i see

so we need to find all possible combinations?

[lyric pumice]

But there are other ways to pick to get the same term.

@copper ore Yes.

All of the combinations that are possible occur in the distributed multiplicaiton.

[copper ore]

do i just try to write them all out?

[lyric pumice]

@copper ore Go ahead.

You will see that there are 10 possible ways.

But you should also see how this number is given by (5 choose 2).

Why is it 5 choose 2?

[copper ore]

But you should also see how this number is given by (5 choose 2).
@lyric pumice yeah i dont really follow that part

Important to keep in mind is what I said before: each (x+y) contributes EITHER x OR y to a given copy of x^2 * y^3
@weary tiger yeah this helped a lot

true

[lyric pumice]

You start with 5 factors to choose from, and you pick 2 of these factors to be where the ys come from.

[copper ore]

one question i had is why is it 5 choose 2 and not 5 choose 3

[lyric pumice]

They are equal.

[vital dew]

slimvesus:

[copper ore]

ohhhhhhhhhhhh

okay

nope

[lyric pumice]

Picking 2 xs from the 5 factors means that you picked out the 3 ys from the 5 factors.

[copper ore]

yeah my professor was talking about something about "leaving out"

don't really get that part

Picking 2 xs from the 5 factors means that you picked out the 3 ys from the 5 factors.
@lyric pumice like this

Yeah that's good: choosing n-k objects is the same as choosing k objects to "leave out"
@weary tiger and this

im so dum blol

sorry all

oh

Or, i could pull n-k out
@weary tiger so with this option the k balls will just be in the bag instead

i see

that's so cooool

wow

didn't notice that

yeah ^^

it is v good

[vital dew]

slimvesus:

[copper ore]

is the binomial coefficient related to the product rule in any way?

[lyric pumice]

Yes.

[copper ore]

i notice that the only difference is that there is a k! at the bottom

[lyric pumice]

It is due to the factorials.

Basically, the binomial coefficient counts the number of ways you can pick k objects from n different objects.

And you should prove how this is the case.

[copper ore]

does order matter in binomial coefficient?

like

it says that binomial coefficient is the number of k element subsets of an n element set (basically what you said) but was wondering if that means ordered?

lol waitt

say that again

that confused me

n!/(n − m)! how is this for ordered only

How many strings of two characters are there, if the first character must be an uppercase letter and the second character must be a digit? like for this, how would order matter?

[lyric pumice]

It depends on how you are using "order". In your case, that order matters means that the sequences in which the objects that you are interested in appear contribute to the total count.

[copper ore]

ok

yeah

yeah

TRUE

ok

discrete math is pretty confusing lol

thank you

n!/(n − m)! is there a name for this formula?

[lyric pumice]

@copper ore It is the falling factorial.

[copper ore]

oo okay

[vital dew]

Chmonkey:

[honest barn]

Oh

Oh shoot you’re right

I deleted it since I don’t like having wrong things up people might see and think is true

When it isn’t of value to see where you went wrong

[cyan talon]

Hey

Anyone knows a book about discrete mathematics for graduate level?

Advanced

Not introductory

More like graph theory

[hybrid crown]

How do you do this?

[stray reef]

R^4 with coordinate-wise <= as the order should not admit an embedding into R^3

oh wait

finite poset

mb

[hybrid crown]

mb?

[stray reef]

my bad

[hybrid crown]

Actually that helped I was trying to see if I could map R^4

[hybrid crown]

still haven't found a proper solution :\

[hybrid crown]

@stray reef hey

sorry to bother you