discrete-math

[blazing night]

Since I've never seen that symbol in my life

[weary tiger]

Tensor product.

But hm...

[blazing night]

I can also show this if it helps

R1=D1 × D2 so it's a combinations of abc1234...

The result is 7

I THINK

But why

[weary tiger]

Ye, I don't know about tensor products sorry. Might look it up later.

[blazing night]

Is the result atleast 7 ?

I need to make sure if I am atleast 50% correct here

Like if I am on the right track

[vapid light]

There's no way you guys are doing tensor products in discrete math

[pale epoch]

eh, this is certainly not a tensor product in this case

[blazing night]

I am sure it is not a tensor product..

[pale epoch]

a tensor product takes vector spaces as input, those guys are very much not

[blazing night]

It's just a bizarre symbol he uses

[pale epoch]

ye, but he should have defined it somewhere

[vapid light]

I'm sure it's a cartesian product

[blazing night]

It is a product

I believe

[pale epoch]

that's gross

[vapid light]

Yeah, what the hell

[pale epoch]

but even then

what is r1 supposed to be?

a set?

[vapid light]

Yeah does your textbook have a definition for this product

[blazing night]

There is nothing about it

It's just a variable

But this is an assumption

r1 doesn't have to be anything

I guess it would store it

[vapid light]

That's a pretty cs way of thinking

[pale epoch]

so what exactly is the question?

[blazing night]

So we have D1 = {a,b,c} and D2 {1,2,3,4}
D1 * D2 ... how many combinations would it make

[pale epoch]

its weird because if $\otimes$ is cartesian product, r1 should be a set, but all the other sets are written with capital letters

[vital dew]

Lochverstärker:

[blazing night]

Hmm

[vapid light]

Maybe it's just a product of the cardinalities

[pale epoch]

i kinda assume that $A\otimes B \coloneqq \lvert A\times B\rvert$, but that is just gross

[vital dew]

Lochverstärker:

[blazing night]

I'm sorry I wish it would've been defined

Would've made it easier

If it is or not

[pale epoch]

i mean, if you don't know what that means, there is no way anyone can answer that question

[blazing night]

I just think it's a product

And r1 just being a variable

Nothing more to it

[weary tiger]

Do you have an example where he uses it?

[blazing night]

Because I am trying to search that symbol

And I never found it ever in my notebook

[vapid light]

Hmm

Time to ask your professor

[weary tiger]

Maybe he was drunk and instead of writing just × he wrote ⊗. 👀

[blazing night]

I think I can ask him tomorrow

@weary tiger I think so too

Also a friend of mine just assumes it's this:

But without explanations idk how to believe it

[vapid light]

Jesus

[pale epoch]

what does "combination" mean

also that result is most certainly not correct no matter in what way i interpret the word combination

[blazing night]

It should be like a "tuple" or something

[vapid light]

Yeah

[pale epoch]

then it's cartesian product

$$A\times B \coloneqq {(a, b) \mid a\in A\text{, }b\in B}$$

[vital dew]

Lochverstärker:

[vapid light]

Then the question becomes fairly simple, for the number of combinations

Law of Multiplication

[blazing night]

Then..how do I exactly make a tuple in r1?

[weary tiger]

(a, 1), (a, 2), (a, 3)...

[blazing night]

Just 12?

[vapid light]

Yeah, then the number of combinations is the cardinality of r1, if r1 is the cartesian product of the two sets

[weary tiger]

If you follow the definition Loch sent you, you can write all the items and realize the cardinality will be |A| * |B|

[blazing night]

Oohh I see

Gods I made this more difficult than it was xD

[vapid light]

No

I think your prof did

[weary tiger]

^

[blazing night]

Well..it's mostly the symbols

If I knew what everything was

But he just writes them down

And nothing is within my notebook but eh

Thank you guys a bunch

[vapid light]

There's a special place in hell for professors who don't explain new notation on homework

[weary tiger]

No problem mate.

[blazing night]

xD

[pallid lintel]

yo, having a little trouble with inequivilent and equivilent planar embeddings

just the definition

so if we change an incidence relation between vertex and edge its no longer the same graph so its no longer the same planar embedding right? But we can change boundaries and still have the same planar graph?

[vapid light]

What's an incidence relation

I'm not familiar with this terminology

If you mean you change the edge by removing it or replacing it with some other edge between two other vertices then they're not the same graph, so it can't be a planar embedding

As long as the set of vertices and edges don't change, then there are possibly many planar graph embeddings, because you can vary the boundaries

[pallid lintel]

thx

[vapid light]

Yeah

[blazing night]

Can someone help me please?

I have a question
Which ones are terms:

https://cdn.discordapp.com/attachments/536995777981972491/715441105335877633/unknown.png

or

https://cdn.discordapp.com/attachments/536995777981972491/715441154681733191/unknown.png

How do I know?

[vapid light]

What's the definition of a term

[blazing night]

Well the only way I can explain it

Tho I can't tell if the first photo is also a term

Second*

My bad

[vapid light]

P(x,y) is like a proposition, right

My bets on that funky f() thing

[blazing night]

Like an elementary form right?

[vapid light]

What's the definition of elementary form

[blazing night]

Nvm sorry I read it from my notebook

My bad

IWell I only have two questions left..
Most of them are just examples to do the rest of my homework alone, a homework that is kinda huge xD

How do I check if this formula is true?

[vapid light]

Simplify the expression by introducing new symbols, first of all

Then use the definition of the implication arrow to simplify further

[blazing night]

Ah alrighty, thank you

[vapid light]

That looks aids, I'm sorry for you

[blazing night]

It does xD

And my last question...

Now this one...

I don't know why I don't have it in my notebook but I think we've done it..

how do I apply the resolution principle?

[vapid light]

I've never had to use it so idk

[blazing night]

I can kind of explain after what I read online..

So you have the first one

And the second one

You need to transform them into something similar-

To have a NOT for example

Because you can cut a variable with NOT with it's own variable after the coma in the second one

For example.. If I am right

(Not P -> q) -> (r v P) , ((P-> q)-> r)

So it would be...

q->(r v P) , q-> r

I think?

And it would be false

Because there's more variables in the first one

[last timber]

(p or q) -> (r or p) is the same as
not (p or q) or (r or p)

[novel quartz]

Which of the following is not true about languages?

         
Any computational problem with a yes/no answer can be phrased as deciding whether some string is in a language.

         
A language is a relation on the set of strings over some alphabet.

         
A language is a subset of the set of all strings over some alphabet.

         
An example of a language is the binary encoding of all valid C programs.

is my course poorly/trickly worded or am I stupid?

[halcyon ledge]

🤔

the age old question

if you understood what a language is you should be able to answer all of these questions

if not check your defintions again

[novel quartz]

I will find the answer for sure I always do, but am I the only one whos so cynical about these questions sometimes

[halcyon ledge]

experience taught me that after searching for it everywhere, the stupid was inside of me all along

so that's my advice, always look for the stupid inside

only then start searching for it elsewhere

[novel quartz]

You're probably right and I'm sure that's the case most of the time, but I still feel sometimes that there is a case to be made about courses introducing difficulty by virtue of bad wording/trick wording instead of loosely coupling language from the actual subject content. But don't take my above question as a point to my case

but now im just projecting 🙂

[idle cave]

best place to learn discrete math for free online?

[halcyon ledge]

what exactly do you want to learn?

I assume there is something you're thinking of when saying discrete math 🤔

[idle cave]

actually nvm

[halcyon ledge]

😦

introduction to combinatorics by brualdi isn't free but can be found via google

if you're in it for the computer science and don't mind having to do a lot of work you might try concrete mathematics by knuth

[vapid light]

I liked cs 70 from Berkeley

All of the material is online

[tardy pike]

By definition of contrapositive I want to find if x^3 is a rational number, then x is a rational number

Not sure how to start

[pallid lintel]

p then Q=not Q then not P

dont u want to start with saying X is rational and derive X^3 is rational

[tardy pike]

Yes that would be better than the other way around but how do you derive that

[faint narwhal]

that's what the contrapositive means

[tardy pike]

oh right you switch them, forgot about that part

[prisma arch]

"The expected value of a random variable is the sum over all elements in a sample space of the
product of the probability of the element and the value of the random variable at this element". At this moment I knew who ever chose this book for our discrete math class was stupid

[faint narwhal]

because this only works for discrete random variables and not continuous ones?

[prisma arch]

Right but the explanation itself and how its worded is horrible. I cant tell if there was supposed to be commas in there or if those repeated "of the"s are supposed to be like that

[faint narwhal]

I mean, this is a pretty standard way to talk about expected value

[prisma arch]

Is it? Because I still have no clue if youre adding all those different things separated by the "of the" or if its the ending part that contains items to be summed.

I cant tell if its supposed to be "The expected value of a random variable is the sum over all elements in a sample space of the
product, of the probability of the element and, the value of the random variable at this element" or if it should be "The expected value of a random variable is the sum over all elements in a sample space of the
product of the probability of the element and the value of the random variable at this element"

[faint narwhal]

$\sum_{\text{elements of sample space}} \left( \text{probability of element } \times \text{ value of random variable at this element} \right)$

[vital dew]

Zopherus:

[prisma arch]

See now if I had that in my book man that would be easier to understand.

[faint narwhal]

Yeah, I guess different people prefer it different ways

[prisma arch]

I think its more the wording. Who ever wrote the book I need to use definitely did not employ someone to go over the book and see if it made sense to them. If they did they could most definitely have made it less verbose.

[pallid lintel]

what is an infinite family ? It wasn't discussed in class notes. For question c

[faint narwhal]

basically an infinite set of graphs

[pallid lintel]

still not sure what that is

[faint narwhal]

okay maybe I'm misinterpreting this too but

An infinite family of planar graphs is all planar graphs with more than 4 vertices

[cerulean ore]

Why nC2 - (n-1) is not equal to (n-1)C2?

I have computed that (n-1)C2 is actually (n-1)/2 less than nC2.

[vapid light]

What does nc2 - (n-1) mean combinatorially

[cerulean ore]

nC2 is basically choosing 2 objects from N.

and since one object from N was chosen (N-1) times so, for (N-1)Ck we should have (N-1)Ck - (N-1)

Circle got chosen 3 times so, 6-3 should be the number of ways to take 2 objects at a time?

fml

[last timber]

$\frac {n!}{(n-2)!2!} - (n-1) = \frac{(n-1)!}{(n-3)!2!}$?

[vital dew]

Commander Vimes:

[cerulean ore]

I have mistakenly computed (n-1)/2, it should be (n-1) ;_:

Thanks!

[mint shore]

can anyone help me get the base premise of generating functions? i've watched yt tutorials but i don't 100% get it

this is from my powepoints: generating function of sequence of real numbers a0, a1, a2...

why are we multiplying by x^k?

x, x^2, x^3 etc

[stray reef]

why are we multiplying by x^k?
cause then you get a power series

and you pretend that you can do with this series anything you can do with a power series

[mint shore]

o

yea that makes sense

i'm still a little behind on understanding how the conversion from sequence to generating function works

these i more or less get

[stray reef]

i mean

that's all there is to it

if you have an explicit formula, that is

[mint shore]

this is a little

interesting

[stray reef]

the second step is just algebra

the first step is the actual conversion

[mint shore]

it says, generating function of 1, 1, 1, ...

[stray reef]

no

[mint shore]

for 6 1s

[stray reef]

1, 1, 1, 1, 1, 1

and then zeroes forever afterward

[mint shore]

it's Σ k= 0 to 5

(i need to learn how the bot works)

this is only adding 6 elements

so it's using the Σ(k = 0,5) x^k and then you just basic algebra the rest

[stray reef]

$ \sum_{k=0}^{5} x^k $

[vital dew]

Ann:

[velvet maple]

Not sure if I'm missing something here so apologies in advance if this is a dumb question, but isn't the list of courses as given from top to bottom a valid entry for the sequence of courses that allows him to enroll in all courses?

[sinful berry]

Hi all, I have a kind of stupid question: When doing force-directed graph visualization, what term do people generally use to refer to the axes?

Calling them "dimensions" seems wrong.

Someone suggested "component" but that seems even more wrong.

[sullen hazel]

I am wondering how would one write their proof for this

We prove by contradiction, assuming square root of 2 is rational. That is,

the square root of 2 = p/q, where q isn't zero

now could I just square both sides and prove from there

because the textbook's proof is pretty ugly

and well ordering is a set of positive integers with a least element

that ik

lol

[vapid light]

cool proof

[tulip ravine]

oh wow, this is super clean, because this proof immediately implies that sqrt(m) is always irrational or an integer.

(which is usually hard work to get)

[vapid light]

how so

[tulip ravine]

well note, what this proof really hinges on is that b isn't 1

as long as b isn't 1, this proof should work

but b=1 exactly says the square root is an integer.

[vapid light]

Oh ok

[hasty glade]

guys

mcm(a, b) > mcd(a, b)

??

For all a and b

???

Mcm = minimun commun multiple

[tulip ravine]

mcd?

[hasty glade]

minimum commun divisor

[tulip ravine]

isn't the minimum common divisor 1?

[hasty glade]

You dont know

That happens if a and b are coprimes

[drifting halo]

minimum common divisor?

Are you sure you don't mean greatest common divisor?

[hasty glade]

That yeahg

Lol so stupid

[drifting halo]

Also, your statement is false

Take a=b, then your claim would yield a > a which is definitely not the case

[hasty glade]

but if a was the same as a letters would not be the same ?

I tought the same you did

[hasty glade]

a div b means a/b without taking into account residual ?

[prisma arch]

Can I get help with these changing of bases. I plugged it in to a website to find out if I was right and they showed something different

Bottom one is turning to base 10

[prisma arch]

found the answer

[coral totem]

81+18+6+2=107

[prisma arch]

Thanks actually I need some extra help with calculating mod inverse. I did the work just not sure if i am correct.

[sour arrow]

It's not very clear what the question is haha

[prisma arch]

Well my question is if I got this correct. I was calculating the modular inverse of 5mod72

[sour arrow]

There's a quick way to check. It should be the case that
5×14 = 1 (mod 72)

It doesn't seem to work, sadly

[prisma arch]

oh I guess I got it wrong. I thought I had done it correctly

[sour arrow]

What's the method?

[prisma arch]

Extended Euclidean Algorithm

idk if that answers the question

[sour arrow]

Yeah yeah so you're looking to compute a and b in:
72a + 5b = 1

So that way when you have the answer, you can take mod 72 and get a solution of the form
5b = 1 (mod 72)
And b is your inverse

[prisma arch]

I guess I still dont get how to find the correct number then.

to find b what would I do then?

oh man I just realised something

I forgot to multiply the 2 into the 5(14)

[sour arrow]

You can get a solution for
72a + 5b = 1

Using the Euclidean Algo.
72 - (14)5 = 2
5 - (2)2 = 1
But we can sub the first into the second like so:
5 - (2)(72 - (14)5) = 1

5 - (2)72 + (28)5 = 1

(-2)72 + (29)5 = 1

And, using that,
5×29 = 1 (mod 72)

[prisma arch]

quick question but how did that 28 turn into a 29?

[sour arrow]

I added like terms. There's a free 5 floating there

[prisma arch]

ohhhhh

ok thank you that makes more sense I was wondering if it just dropped off

So then I am plugging that which we found which is the decryption factor in this case and follow this example for message that is encrypted as "38 23"

I try to do that but it doesnt get me a real word or phrase.

looks like i found the answer after realizing something

thanks for your help

[ancient sequoia]

Hey guys I’m trying to apply a discrete Fourier transform to a 41x1 array in python using numpy fast Fourier transform. The array is full of displacement values for an extended LK14 protein; the frequencies from the Fourier transform should allow us to get the pitch for the irregular helix, because conventional methods won’t work. When plotting the resulting array, there’s a large peak at 0 and some very small flat peaks elsewhere. I’m not at home so I can’t provide a picture, but i wanted to see if my conceptual understanding of this was correct: the peaks correspond to the frequency amplitude of the irregular helix, and if you added multiple helixes together, each having one of the frequencies from the transform of the irregular helix, you’d get the resulting irregular geometry. (Like adding sine and cosine waves together with different frequencies to get a weird looking curve, like a helix projected onto a 2D plane). That idea comes from how the Fourier transform is commutative (I think that’s the word? Basically Fourier of f(x) + Fourier of g(x) = Fourier of f(x) + g(x) ) is there any logic I’m missing or anything I’m getting incorrect? Thanks ahead of time 🙂

[vapid light]

that property is linearity

not commutativity

[weary tiger]

Can someone explain me the formula for Inclusion–exclusion principle?

I got the idea, but I cant get the formula. https://en.wikipedia.org/wiki/Inclusion–exclusion_principle

this one specifically

[spark oyster]

It's a complicated looking formula, but if you understand the explicit formula for two sets, three sets, four sets.... then it doesn't actually get any more complicated

Do these two formulas make sense to you?

[weary tiger]

yeas

[spark oyster]

Yeah, then that formula you posted is just carrying on the same logic for arbitrarily large n

[weary tiger]

Like i know the principle, but I am not able to get those formulas using the general one

I just dont see in the formula how i iterate first through one-element sets

[spark oyster]

Alright, so let's try the simplest example, n = 2

[weary tiger]

Okey

[spark oyster]

The left hand side is easy, that's just $|A_1 \cup A_2|$ directly

In the right hand side, we have a sum over all nonempty subsets J of {1,2}

[weary tiger]

Yes

[spark oyster]

So we have three choices: J = {1}, J = {2}, J = {1,2}

And then if you insert these three sets, you directly get the three summands, right?

Maybe you can pinpoint the part that confuses you here

[weary tiger]

I thought that if J = {1,2} that in the first iteration of the summation the J = {1}

in the second summation J = {1, 2}

[spark oyster]

Hm, I'm not sure I understand what you're saying

[weary tiger]

well i am not native speaker so maybe thats the problem

[spark oyster]

You only have a single summation; every single J shows up with a single summand

Yeah, don't worry, we'll get there 😄

[weary tiger]

but the J changes during summation

[spark oyster]

Yup, the J changes, it goes through all the different nonempty subsets of {1,2}

[weary tiger]

and the values in J are the indexes of the sets right?

[spark oyster]

Yeah, so if you look at the summand for J = {1,2}, you get the intersection of A_1 and A_2

So, let's maybe more closely interpret the summand for J = {1,2}

If we go to the formula from your screenshot, you get $(-1)^{|J| + 1}$; because J contains two elements, we have $|J| = 2$, so $(-1)^{|J| + 1} = (-1)^3 = -1$, so this summand comes with a negative sign

[vital dew]

Lartomato:

[weary tiger]

Yeah this is clear

[spark oyster]

And then, we have the expression $\left| \bigcap_{j \in J} A_j \right|$ which we need to understand

[vital dew]

Lartomato:

[weary tiger]

Yeah now I am kinda confused what small j will be

[spark oyster]

We are looking at the summand of the big sum, where $J = {1,2}$, so this intersection $\bigcap_{j \in J}$ goes over the elements $j = 1$ and $j = 2$, because those are the two different elements of J

[vital dew]

Lartomato:

[weary tiger]

Since J = {1, 2}

[spark oyster]

Hence, we get $|A_1 \cap A_2|$

[vital dew]

Lartomato:

[weary tiger]

well j has to be a set or no?

[spark oyster]

No, here the small j's are the elements of your set J

Hence the element sign $\in$

[vital dew]

Lartomato:

[weary tiger]

Ah my bad yeah now I understand

[spark oyster]

So that's a difference to be aware of; in the big sum $\sum$, we go over all the subsets of ${1,2}$; in the intersection, we look at all the elements $j \in J$

[vital dew]

Lartomato:

[spark oyster]

Perhaps that was what confused you

[weary tiger]

Yeah now I understand the second part but still get this notation

means going through all the subsets of 1, 2

I know why we are doing that

Becuse how I imaged that summands went is first J = {1}, then J = {1,2}

in case when n = 2

[spark oyster]

Ah, I see. But yeah, this expression asks you to go through aaaall possible subsets J

But I see why this confused you, there's a lot going on in that expression 😄

definitely a bit more complicated than boring olds sums $\sum_{i=1}^n$

[vital dew]

Lartomato:

[weary tiger]

yeah because I found a formula which is same like the previous just written differently

and here the I is binomial coefficient

[spark oyster]

oh man that looks a bit confusing

[weary tiger]

Its basically the same

[spark oyster]

But I guess that binomial coefficient stands for "all the subsets of {1, ... , n} of cardinality k "

Haven't seen that notation before

[weary tiger]

me too but what I dont get here is that I thought that result of binomial coefficient is number

[spark oyster]

Yes, it usually is; this seems to be a different thing

Because usually, you also insert numbers into the binomial coefficient, not sets

[weary tiger]

yeah

[spark oyster]

So you gotta just accept that this is a different notation, which is hopefully explained in the place where that came from

[weary tiger]

Yeah it says that its all k-subsets of set {1,2 ... n}

[spark oyster]

Yeah exactly, that's what I thought

and then it's the same thing

[weary tiger]

so this is how we notate all subsets of some set?

[spark oyster]

Specifically, nonempty subsets, yeah

You should interpret this as two different pieces of information

$I \subset {1,\dots,n}$ denotes that we are summing over all possible subsets

[vital dew]

Lartomato:

[spark oyster]

and $\emptyset \neq I$ denotes that you exclude the empty set

[vital dew]

Lartomato:

[spark oyster]

(that's kinda trivial if you write it like this, but it's good to isolate the different pieces of information)

[weary tiger]

Ok I get it

[spark oyster]

neat!

[weary tiger]

so the result of this: $I \subset {1,\dots,n}$ is {empty set}, {1}, {2}, {1,2}

[vital dew]

Ivo Horák:

[weary tiger]

tried to used TeXit

doesnt work out 😄

but u got the idea right? 😄

[spark oyster]

Yeah, that's right

[weary tiger]

Ok, thank you so much

so basically I just didint understand the notation

[spark oyster]

No problem! You're gonna get used to it, I'm sure 😛

[weary tiger]

Yeah this is first time when i am using summarization and sets together

Thanks once more

[silk mauve]

How many ways can you partition a set of size n into k (potentially empty) subsets?

[pale epoch]

i don't think there is a nice formula for that

[silk mauve]

Yeah, I though so, but maybe a recurrence relation?

[pale epoch]

you can sum up stirling numbers from 0 to k i guess

well, that's how i would calculate it

but it's very ugly

at least the way i'm reading the question

(that is, summing up the number of partitions of the set into exactly j nonempty partitions for j=1 to k)

[silk mauve]

yeah, I guess you can't do much better, ty man

[weary tiger]

Hey, I need to prove that:

[vital dew]

nxue:

[weary tiger]

But I don't have a clue on where to start... I tried proving that:

[stray reef]

is that even true

[weary tiger]

$\mathbb{R}^{\mathbb{N}} \sim \mathbb{R} \sim 2^{\mathbb{N}} \sim \mathcal{P}(\mathbb{N})$

[vital dew]

nxue:

[weary tiger]

I don't have a clue on where to start with that R^N ~ R

[tulip ravine]

I would use the fact that R is equinumerous with (0,1) and then prove that (0,1) is equinumerous with (0,1)^N

(by looking at the decimal expansions)

[weary tiger]

I know that R ~ 2^N

and so R^N ~ (2^N)^N and I also know that it is ~ to 2^(NXN) ~ 2^N ~ R

so R^N ~ R
is it correct? @tulip ravine

[errant bear]

can someone please elaborate of how you arrive at this sum?

the stirling numbers are the coefficients of each successive falling factorial on n up to m, but I don't know at all how to arrive at this, induction?

[brazen tendon]

Question: A witness to a hit-and-run accident tells the police that the license plate of the car in the accident, which contains three letters followed by three digits, starts with the letter A and contains both the digits 1 and 2. How many different license plates can fit this description?

Can you guys help me with this, it's easy but I am having trouble with the number section

[sour arrow]

Count the number of possible third digits
Count the number of ways to permute them

Note that if you pick a 1 or a 2, the ways to permute changes

[brazen tendon]

These 2 graphs don't have a hamilton circuit or path right?

oh wait the one on the right should have a hamilton path

ABCDE

but idk if it has a hamilton circuit

[tulip ravine]

the one on the left has a Hamiltonian path

[upbeat lodge]

im taking on the challenge of self teaching discrete this summer, does anyone have resources they particularly like

[vapid light]

Berkeley has a pretty difficult discrete math course, but the notes and hw are pretty good imo

[upbeat lodge]

do you have a link?

[vapid light]

https://www.eecs70.org/

[upbeat lodge]

ty

[vapid light]

Ye

[last timber]

im taking on the challenge of self teaching discrete this summer, does anyone have resources they particularly like
Rosen Kenneth Discrete Mathematics and Its Applications

[tight shard]

56.44269024, 33.55730976 in the nearest degrees?

[robust mango]

what do you think

[tight shard]

I'm not sure to be honest with u

@robust mango

I'm trying to figure out if it involves

other things

[robust mango]

no no, its very simple

just 56 and 34

[tight shard]

Yikes sounded really confusing in my head tbh

thx tho

[sour dawn]

@silk mauve

How many ways can you partition a set of size n into k (potentially empty) subsets?

$$\binom{n+k-1}{k-1}$$

[vital dew]

tanoshii:

[sour dawn]

oh wait misread the question

try this instead

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

[silk mauve]

yeah, that's what Lochverstärker suggested, seems like the best way to calculate it is to sum the stirling numbers

[sour dawn]

$\frac{1}{k!}\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n$

[vital dew]

tanoshii:

[silk mauve]

yea so we get like a double sum...

not very nice

[sour dawn]

oh are you summing over k

in that case

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

recurrence: $B_{n+1} = \sum_{k=0}^n \binom nk B_k$

[vital dew]

tanoshii:

[silk mauve]

well bell numbers only work in the case where we want n potentially subsets but in my case I want k potentially less than n subsets

[sour dawn]

the cool part is that it has generating function $e^{e^x-1}$

[vital dew]

tanoshii:

[sour dawn]

hm?

are you fixing k or no

[silk mauve]

yes

[sour dawn]

oh then the stirling number is fine right

[silk mauve]

well the sum of stirling numbers

[sour dawn]

there's no double summation

the sum of the first n stirling numbers is the nth bell number

[silk mauve]

so what I think we get is $\sum_1^k S(n,k)$

[vital dew]

Maldor:

[silk mauve]

no wait

umm

hmm

[sour dawn]

oh are you saying

number of ways to split into at most k subsets?

[silk mauve]

yea exactly

[sour dawn]

oh

you mean possibly empty

but without like

distinction?

[vital dew]

Maldor:

[sour dawn]

if you have distinction then it's easy

otherwise good luck

[silk mauve]

yea, no distinction unfortunately

[sour dawn]

yeah ok i don't immediately see any better way than sum spam

[silk mauve]

$\sum_{1=i}^k S(n,i)$

[sour dawn]

you want {}

[vital dew]

Maldor:

[sour dawn]

$\sum_{i=1}^k$

[vital dew]

tanoshii:

[silk mauve]

that's the sum I think

yea

[sour dawn]

and yeah unfortunately idk then

[silk mauve]

well it's fine, it would just be nice it there turned out to be a nicer way u know

[sour dawn]

rip

[pallid lintel]

how do i draw graphs in text

wanna draw complete graph in texit, K6

and label the vertices

[stray reef]

wdym "dont think thats possible"

what do you get when plugging it into your calculator

[faint narwhal]

Do you know how to diagonalize a matrix

[stray reef]

also yeah that
maybe yours is diagonalizable and then it'll be easy

[faint narwhal]

(adjacency matrices are symmetric and thus diagonalizable)

[stray reef]

i mean... idk, you could try exponentiation by repeated squaring or sth

[faint narwhal]

but yeah rip, this question seems like its meant to be done using diagonalization of matrices

usually a discrete math course has linear algebra as a prereq

[last timber]

and how many

?

[faint narwhal]

oh right we're dumb

[stray reef]

now that one looks at it

all walks from V_3 to itself would obviously have been of even length

[faint narwhal]

try to find some paths from V_3 to V_3

and see if you can note a pattern

[mint shore]

does anyone have any good material/explanation on generating functions? i've seen a few vids online and read through my uni's powerpoints but i don't really get it

[last timber]

Knuth explainds generating functions well

Rosen Kenneth Discrete Mathematics and Its Applications

also touches

[mint shore]

knuth?

youtuber or book author

actually i'm just googling it either way

thanks for the info though

[pallid lintel]

whats the font of the fancy D

i need to get the fancy D in latex

[faint narwhal]

$\mathcal{D}$

[vital dew]

Zopherus:

[faint narwhal]

or maybe $\mathscr{D}$

[vital dew]

Zopherus:

[pallid lintel]

what does mathscr stand for?

[faint narwhal]

math script

[pallid lintel]

do i type /mathscrp{D} on one line then for every D i want to be fancy, i put brackets around D like {D} ?

[faint narwhal]

No

It only changes the font of whatever is in the brackets

[pallid lintel]

i did this but get an error

[faint narwhal]

You have to write \mathscr again

It also requires a certain package

[pallid lintel]

do you know which package?

\usepackage{mathrsfs} this one?

looks like i got it working, thx

[prisma osprey]

How does tihs question work?

I'm thinking that we have, say $Phi_{even}, Phi_{N}$, and $Phi_{<100}$, and that the set of 3 part compositions is

$S = \phi_{even}(x)\phi_{N}(x)\phi_{<100}(x)$

[vital dew]

Liria ^(;,;)^:

[prisma osprey]

And that we have that

$T = \phi_{even}(x)\phi_{N}(x)^2\phi_{<100}(x)$

[vital dew]

Liria ^(;,;)^:

[prisma osprey]

And that the resulting generating series is just $\phi_S(x) + \phi_T(x)$

[vital dew]

Liria ^(;,;)^:

[prisma osprey]

But I'm not quite sure whether or not S and T are disjoint?

[pallid lintel]

just wondering do graph theorists who study hypergraphs find colourings that arn't proper colourings interesting?

as in colour all vertices in an edge with a single colour

[lyric pumice]

Yes.

[rancid basin]

Hey

is anyone familiar with discrete math ??

[faint narwhal]

[rancid basin]

what is pigeon hole method ??

@faint narwhal

[faint narwhal]

What are you confused about?

[last timber]

pigeon hole method is that

Given m "objects' and n "boxes" into which objects are to be put, if
\$\lceil \frac{m}{n} \rceil \geq 2$,\ then at least one "box" should contain at least 2 "objects"

[vital dew]

Commander Vimes:

[stray reef]

ceil(m/n) ≥ 2

or in other words

m > n

[weary tiger]

Hello friends
easy but hard af question:

calculate:

now, how tf do i solve it, it depends on n if its even or odd, nothing is given

[vital dew]

nxue:

[weary tiger]

If n is odd, then the last term is +n

so it's 2n - 2(nC2)+3(nC3)-...

but I cant seem to find anything further

[tulip ravine]

Hint: use the binomial theorem

[weary tiger]

what is the binomial theorem 0_0

(x+y)^n ?

[tulip ravine]

I'd suggest writing it as $(1+x)^n = \sum_i {n \choose i} x^i$

[vital dew]

zetamath:

[weary tiger]

but it's alternating with + and - 😿

[tulip ravine]

replace x with -x (-:

[weary tiger]

and what about the coefficient

I mean, it is

$(1+x)^n = \sum_i i \cdot {n \choose i} (-x)^i$

[vital dew]

nxue:

[weary tiger]

zetamath please help me you're my god @tulip ravine

[tulip ravine]

so, if I replace the x with -x in what I wrote, I get : $(1-x)^n = \sum_i {n \choose i} (-x)^i = \sum_i {n \choose i} (-1)^ix^i$

[vital dew]

zetamath:

[tulip ravine]

so we're getting closer!

[weary tiger]

but what about the coefficientsss

[tulip ravine]

yup, agree, we're not quite there

but I bet there is something I can do to an x^i to get an i in front

[weary tiger]

This is the sum

$\sum_{i=1}^{i=n} {n \choose i} (-i)^{i+1}$

[vital dew]

nxue:

[tulip ravine]

that doesn't seem to give you quite what you want

[weary tiger]

but we cant start i to 0

we miss the first number nCn but we can always just add +n to the expression

[tulip ravine]

Hint: consider a derivative

[weary tiger]

is this like a taylor series

[tulip ravine]

Yes, but I wouldn't think of it that way

[weary tiger]

im confused

is this the derivative itself or I need to integrate this

[tulip ravine]

you need to take the derivative of the last equation I displayed

[weary tiger]

but, what is X ? @tulip ravine

$n(1+x)^{n-1}$

[vital dew]

nxue:

[tulip ravine]

it's just a variable for now, but you will want to plug in a value later

[weary tiger]

i still dont get it

[weary tiger]

why are there 5*2/2 = 5 diagonals in a convex pentagon

bc there are 5 points

??

are there 4 diagonals in a square then

no

[tulip ravine]

I'd write it as ${5 \choose 2} - 5$ for what its worth

[vital dew]

zetamath:

[weary tiger]

@tulip ravine but why?

can you explain your reasoning

[tulip ravine]

yeah, there are 5 choose 2 ways to pick two of the five points and draw a line between them

but 5 of those lines are the edges

[weary tiger]

but why -5 I mean

[tulip ravine]

(and edges aren't diagonals)

[weary tiger]

define edges?

[tulip ravine]

the line segments on the pentagon itself

[weary tiger]

like the perimeter?

[tulip ravine]

the sides

[weary tiger]

i mean the lines connecting it

[tulip ravine]

the -5 is subtracting the 5 sides of the pentagon

you'll notice a square has 2 diagonals, which is (4 choose 2) - 4

[weary tiger]

well the diagonals in a square overlap

so

@weary tiger what?

u were like "are there 4 diagonals in a square? no"

this is my response

yeah but you said

there are 5 diagonals in a convex pentagon

because there are 5 points

a square has 4 points

it doesn't have 4 diagonals.

so your logic doesn't make sense

@weary tiger

well do the diagonals in a convex polygon overlap?

no

so

show a picture of "overlap"

in ms paint

ok

@weary tiger

but you definitely have that in a pentagon

wait

um no u dont

in a pentagon the points meet up with the mid way point of its opposite line

@weary tiger

http://sketchtoy.com/69213557

???????

@tulip ravine are you seeing this lol

[tulip ravine]

I do not consider there to be 4 diagonals in a square

I consider there to be 2

[weary tiger]

yes

but i mean

look at his pentagon drawing

lol

theres only 2 diagonals in a square

that pentagon drawing makes no sense at all

[pallid lintel]

\longrightarrow

texit keeps getting error? i want something like this

[weary tiger]

@pallid lintel wrong channel but $n \longrightarrow (2)_5^1$

[vital dew]

polynomial:

[weary tiger]

oh that's an r not a 5

you get the point

[pallid lintel]

thx

[weary tiger]

why are there 12 ways to rotate a tetrahedron

regular

that don't change it if all faces are the same

[last sigil]

Let's consider a triangle first

How many ways can you rotate a triangle to end up with the same "triangle"

@weary tiger

[weary tiger]

3

[last sigil]

Yeah so if we only consider a transformation of a tetrahedron's base, we get that there are 3

Now of all faces are equal, we have 3 equivalent orientations for the 4 faces

[weary tiger]

why?

it feels to me if you fix one of the faces

there's less rotations available to you

[last sigil]

But you aren't fixing one of the faces?

How many rotations do you think the tetrahedron has?

[weary tiger]

idk lol

[last sigil]

Hmmm let's looked at a cube

All edges andvertices are considered equal

How many rotations of a cube result in the same "cube"

[weary tiger]

16

probably

[last sigil]

Don't give me probably lmao

[weary tiger]

[last sigil]

Explain your reasoning

[weary tiger]

i drew a cube

i labeled a face 1

then i imagined rotating it around the x axis

and the z axis

4 rotations in each way

so 4 * 4

[last sigil]

Nah, theres 24

[stray reef]

then i imagined rotating it around the x axis
and the z axis
4 rotations in each way
so 4 * 4

rotations around different axes don't commute

[weary tiger]

if you draw a cube

you can rotate it to the left

[stray reef]

if you rotate around the x axis first and then around the z axis, you'll get a different result than rotating around the z and then the x.

[weary tiger]

and then flip it

and that would be different than just a rotation to the left

[stray reef]

i'm saying that you're trying to encode orientations of the cube in terms of an x-rotation and a z-rotation but this encoding is flawed

[weary tiger]

@stray reef in my mind i drew a tree, like rotation left (or right doesn't matter) but there are 4 ways to rotate it left/right

and then 4 ways to go up down

so 4 * 4

[stray reef]

ok wdym by "4 ways to rotate it left-right" then

[weary tiger]

draw a cube

mark one of the faces as "A"

then in your head

rotate it to the left

so that the A would be to the left of the originally marked "A" face

and then on the opposite side if "A" were the front face originally

then on the right

then back to where it originally was

[stray reef]

so... ok, so what you're describing is rotations about the z-axis

if we assume the x-axis is facing us, the y-axis is facing right, and the z-axis is facing upward

[weary tiger]

yes

now

[stray reef]

and then i guess your "up-down rotations" would be around the y-axis.

[weary tiger]

mark the "bottom side" relative to "A" as "B"

[stray reef]

why you're not counting rotations around the x-axis is beyond me.

[weary tiger]

ok y-axis, x-axis, same thing basically

[stray reef]

also. hold on

i think i see a flaw in your method.

[weary tiger]

let me draw it out

@stray reef http://www.sketchtoy.com/69213817

[stray reef]

here

[last timber]

i think it is 3^3 for tetrahedron

[stray reef]

what's "it"

[weary tiger]

ann well yes but the "A" didn't matter you could've colored it a red face instead

i shouldn't have said "A"

[stray reef]

yes it does matter

[weary tiger]

yes exactly

the A forces orientation

from a certain viewing angle

[stray reef]

these are different

[weary tiger]

exactly that's my point

[stray reef]

your method does not account for the latter

[weary tiger]

that's not good

that's not what we want

[stray reef]

yes that was my point too

[weary tiger]

oh ok

what was your original point?

i mean

how did you word this

without the visual

[stray reef]

you failed to account for some of the possible orientations of the cube

[weary tiger]

no if we don't write "A" on the side, but instead color it red

then i account for all of them

right

[stray reef]

no

[weary tiger]

[stray reef]

because if you just color a face solid

you lose the ability to tell apart orientations of the cube that differ from one another by a rotation in the plane of the colored face

[weary tiger]

ugh i am just confused now

[stray reef]

like if you replaced the A's here with a solid red coloring these would become identical

which is not what we want

[weary tiger]

so how many ways are there to rotate a cube

[stray reef]

24

[weary tiger]

why 24

how would you count this

[stray reef]

okay so NOW i can get to my point of how to count this.

one thing you could keep track of is a vertex and an edge incident to the vertex

you could perhaps imagine painting a small circle around the vertex and a thin line along the edge

then there are 8 possible positions for the vertex, and once the vertex is fixed, 3 possible positions for the edge

[weary tiger]

which edge

[stray reef]

the one you're keeping track of

like for example

you could take a standard six-sided die

and have your marked vertex and edge be the 1-2-3 vertex and the 1-2 edge

[weary tiger]

can you highlight the edge

in your drawing

[stray reef]

like this perhaps

[weary tiger]

ok

why only one edge tho

there are 3 that connect a vertex

[stray reef]

and once the vertex is fixed, [there are] 3 possible positions for the edge

i want to be able to tell these apart

[weary tiger]

ah ok

now i get what you're saying

[stray reef]

if you also keep track of a face incident to the edge you can account for reflections too

and this also works on some other polyhedra

[weary tiger]

ok

so now what

[stray reef]

there are 8 possible positions for the vertex, and once the vertex is fixed, 3 possible positions for the edge

each orientation is uniquely determined by the position of this vertex-and-edge thingy

so there are 8 * 3 = 24 possible orientations

[weary tiger]

interesting

why can't i think of faces though

somehow

if we colored a face red

[stray reef]

i explained above

if your cube only has one solid-colored face then all you can keep track of is what face the solid color is on, which gives you only 6 orientations

each one corresponding to 4 of the 24 orientations of the cube

[weary tiger]

https://www.euclideanspace.com/maths/discrete/groups/categorise/finite/cube/index.htm @weary tiger read this. Maybe you understand

[weary tiger]

@stray reef can you help me

[stray reef]

i don't know, i definitely can't until you tell me what you need help with

[weary tiger]

Our water polo team has 15 members. I want to choose a starting lineup consisting of 7 players, one of whom will be the goalie (the other six positions are interchangeable). In how many ways can I choose my starting lineup?

i know its 15 * $\binom{14}{6}$

[vital dew]

polynomial:

[stray reef]

yes

[weary tiger]

but why aren't we introducing order here

like as in

why don't we have to divide by 2

since we could pick the 6 players first

and then the goalie

or the goalie and then the 6 players

or

[stray reef]

that'd give you $\binom{15}{6} \cdot 9$

which is the same thing

[vital dew]

Ann:

[stray reef]

should be

lemme doublecheck just in case

[weary tiger]

it is

but

aren't we overcounting tho

since we are picking one of them first

but order doesn't matter here

or

[stray reef]

it doesn't matter in what order we account for these positions

they are not interchangeable anyway

[weary tiger]

why not

i mean

why doesn't in matter

what do you mean by interchangeable

[stray reef]

you have two dice. one is a cube and the other is a dodecahedron. how many possible rolls are there?
it doesn't matter if you do 6 * 12 (first counting the rolls on the cube, then on the dodecahedron) or 12 * 6 (dodecahedron first, then the cube)

[weary tiger]

that's not the same thing

we're picking from a pool of people here

it is the same pool

[stray reef]

you could think of it like

pre-aligning all the 15 players in a row (in one fixed arrangement, say by having them line up by height or alphabetically or whatever) and then dsitributing the three roles (goalie, player, not on team)

you have one slot for the goalie, six slots for players and eight slots for non-players

and you get $\frac{15!}{1! \cdot 6! \cdot 8!}$

[vital dew]

Ann:

[stray reef]

same result either way

what do you mean by interchangeable
for example, if you had a pool of say 20 people and you wanted to pick six of them to make into teams of 3

putting alice, bob and carl in team 1 and daniel, emma and fred in team 2
is essentially the same as putting daniel, emma and fred in team 1 and alice, bob and carl in team 2

that is, of course, unless team 1 and team 2 can be distinguished in some context-dependent way

[weary tiger]

yeah ok

[stray reef]

but here, you have two sub-teams
one consists of the goalie, and the other consists of the other 6 players

these are fundamentally different

there's only one goalie but there are six non-goalies

so you can't do the swap thing

and so no division happens when you do the count

[obtuse lance]

I don't think you said this way, but another way that might help is you can pick the whole team first, then pick the goalie from that team

$\binom{15}{7} * \binom{7}{1}$

[vital dew]

Merosity:

[obtuse lance]

since maybe that gets around thinking about "picking the goalie first" vs "picking the rest of the team first" thinking you're double counting somehow

[weary tiger]

that's a nice way to think about it yeah

thanks @stray reef @obtuse lance

[obtuse lance]

yup 👍

[pallid lintel]

is there a terminology for saying 'this set has more colour of this element than any other coloured element'

[pale epoch]

more colour??

[stray reef]

:??

[pallid lintel]

thats too many words, heh. sounds obvious but could shorten it to 1 word or a symbol

[stray reef]

we don't know what you even mean by this

[rain stone]

Your initial statement is rather confusing. What does colour of an element mean? do you have a set of coloured objects, and one colour is more prevalent? If that's the case, you can just say "there are more elements with [colour x] than any other colour"

nothing wrong with words in a math problem

@pallid lintel

[stray reef]

they've refused to clarify

[pallid lintel]

thats what i meant. I just used words. Was wondering if there was notation though

[rain stone]

even if there were, it probably wouldn't be super well known. Sets of coloured items really aren't common enough to warrant it. If your notation isn't known, then someone has to google it and read the words anyways. By just writing it, you save time and energy, and it's so much clearer

[stray reef]

thats what i meant. I just used words. Was wondering if there was notation though
WE DON'T KNOW WHAT YOU MEAN FAM

WE DON'T KNOW WHAT YOU MEAN

[last timber]

[rain stone]

I think they were confirming what I said. They meant that they have a set of coloured elements, and one colour is most prevalent

[pallid lintel]

yes, nicholas has it right

[rain stone]

you need to be sure that your description is as clear as possible. Two people here didn't understand your original wording, so go with something clearer

[hardy remnant]

so i noticed that proposition logics are written this way, but is it ok to write it like (p OR -r) -> q

unless that is wrong because the order would be different?

[robust mango]

@hardy remnant Let's say "q or -r" is Q. So the screenshot says if p, then Q. What you're saying is if Q, then p. Both are different.

[hardy remnant]

ok, so i have to remember to write it differently

[robust mango]

If it was double implification, such as $p \iff q$, then it doesn't matter. It's equivalent to $q \iff p$

[vital dew]

Sup?:

[hardy remnant]

oh ok

thanks

[maiden shell]

Is it the right place to ask about graphs?

[tulip ravine]

@maiden shell This is a fine place to ask about graphs

[maiden shell]

I have a graph with 6 vertexes. I need to find out, how many (in worst possible case) multiplications do I have to make in order to calculate the matrix of distances. I'm supposed to be using repeating squaring method.

Can you give me a hint, where to start?

I'm totally new to graphs

[fading spear]

Induction anyone?

[brazen tendon]

Can you guys please help me with this?

The letter part is easy

26x26 but the number part is really hard

bcs there is a lot of duplicates

when counting

[stray reef]

inclusion-exclusion, perhaps?

[brazen tendon]

thats harder

:/

[stray reef]

is it

[lyric pumice]

@brazen tendon There is almost certainly no nice explicit formula.

[fossil pewter]

Why not count cases with 1,1,2 and 2,2,1 separately and the rest with different numbers

[brazen tendon]

ye I did

You get 54

but it should be 52

so you have to count out the duplicates from the others

I did this

All possibilities are 58

There isn't 54

I wrote a java code

It founds 52

wait

lemme copy paste the output

102
112
120
121
122
123
124
125
126
127
128
129
132
142
152
162
172
182
192
201
210
211
212
213
214
215
216
217
218
219
221
231
241
251
261
271
281
291
312
321
412
421
512
521
612
621
712
721
812
821
912
921
52

Process finished with exit code 0

52 is the count in the last line

[fossil pewter]

Your code doesn't include 012 , 021

[brazen tendon]

yeah I thought number plates can't start with 0's ?

I never saw a number plate on a car

that had 0

at first digit

:&

thats weird

[fossil pewter]

Yea man

[brazen tendon]

can you explain the

8*3!

part

I did

but I thought 0 was like

not ok in the "first" digit lol

I found it

something like this

don't question it

[fossil pewter]

Did you manually count it

[brazen tendon]

no lol

8

3!

ye

ok

Thanks

i was being dumb

Umm I don't get this question, Pelin has an 3/11 chance to pick lemonade at first when transferring to second fridge

what does the rest of the question have to do with that

[brazen tendon]

also this is wrong right? They removed an edge from a graph to get the circuit

[indigo plinth]

Wdym by wrong? The right is an Euler circuit, but just isn't an Euler circuit for the left graph. Dunno your context

[brazen tendon]

Question is this

My answer:

[indigo plinth]

Thats not a question, thats a chart. What are you asking about

[brazen tendon]

That is a question

It asks for me to fill the blanks...

[indigo plinth]

Yeah, but that doesn't at all reference cdebbadc

[brazen tendon]

yeah, I searched for the question online and this site came up

and it showed that for that graph

[indigo plinth]

Source?

[brazen tendon]

http://jlmartin.faculty.ku.edu/~jlmartin/courses/math105-F11/Lectures/chapter5-part2.pdf

[indigo plinth]

I mean, its a presentation. I will tell you that the Euler circuit to the right is not applicable for the figure on the right. Maybe the presenter uses that as an example of just another circuit, or maybe that you are unable to remove edges. I really doubt the slides are meant to be used without the presenters lecture/context

[brazen tendon]

Yeah

So do you think my answer is correct for this question? https://discordapp.com/channels/268882317391429632/496785905474994186/717845067703910412

I couldn't find a hamilton circuit

on the Figure B

[indigo plinth]

The one above is literally another alteration

1s

sbt, I think you're right, I couldnt find one either

[brazen tendon]

ye

unless you can like

drift around E to A

lmao

@indigo plinth btw if ur avaliable can I ask one more question about graphs

[indigo plinth]

whats up

[brazen tendon]

I am thinking a Tree graph

Should be directed

[pale epoch]

why a tree?

[brazen tendon]

The one on the top of a node will be its prerequisite

you read it from top to down

so you know that the top one is the prerequisite for the bottom

[pale epoch]

well, ok, i can see why it should be cycle free

but connected?

[brazen tendon]

well

hmm

no

for example

Math 1 -> Math2

should be seperate from other classes

like

Physics1 -> Physics 2

should have its own lane

[pale epoch]

ye