discrete-math

[grim oxide]

in that case, there are 3!

[quaint flower]

It's just, I don't know when it's a permutation vs not a permutation

[grim oxide]

it's a permutation if ABC is distinct from ACB

[quaint flower]

I guess...

I suppose I need a problem to see when to use multiplication principle vs permutations

[grim oxide]

permutation is really just a subcase of multiplication principle

[true venture]

Maybe try labeling the boxes ABC and the objects 1,2,3. Using the same labels for both is confusing

[quaint flower]

So for example:

I have 1 green bear, 1 yellow bear and one blue bear, and I want to sort them.

In how many ways can I sort those?

I ask myself: Order matters? Yes

[grim oxide]

by sort you mean place them in some order?

[quaint flower]

Yeah, I suppose my way of using sort is confusing

if it's just, how many ways can I pick one bear? Then, it's three ways.

[grim oxide]

in that case order does matter

[quaint flower]

but is there really just 1 combination?

[grim oxide]

for the first position in the order, you have 3 choices, for the second position, you have 2, for the last you have 1
in total 3x2x1 choices

[grim oxide]

yeah there's a single way to pick three objects when you have three objects

[quaint flower]

I just don't know how to think here.

maybe, the way I ask my questions are too confusing

[quaint flower]

I suppose the culprit is the way I ask questions

the word "sort", gets confusing

[quaint flower]

It's just, I don't know when to use this principle and that principle sometimes

I need a pattern or an algorithm to work things out in problem solving

[true venture]

Yea knowing when order matters is confusing, maybe think if you had an arrangement and someone else had the same but the order was dif. Would you consider both you and them to have the exact same thing

[quaint flower]

I don't really know

You can say:

205 is not the same as 502

So, does this mean. Order absoloutly matters? Sure?

[true venture]

Each case you need to think, does order matter here.

[quaint flower]

So let's say we had a list of names. 10 names.

How many ways can you sort those names?

Wouldn't this mean you had to think: Yes, order matters. So, it's permutations we're dealing with.

And, we'd have to go into this formula of using: n!/((n-k)!) ?

[true venture]

Say 205 represents a pass code, there order matters. But if 2,0,and 5 are labeled balls and you have balls 2,0,and 5 but your friend has balls 5,0,and 2 order doesn't matter

[quaint flower]

Problem is, I can't use this formula here anymore. The answer would no longer make sense:

You have n=10

Then what? k = 9? k = 10?

doesn't make much sense at all

Sure, you have 10! but how the hell?

I think: This formula sucks all of a sudden.

[true venture]

Yes in that case the number of ways to write an ordered list of 10 names is just 10!

[quaint flower]

Yes, but the formula isn't making much sense...

Doesn't k mean, K at a time?

or am I choosing 10 elements from 10 elements

I'm like, huuuh? I am making 1 choice at a time.

[grim oxide]

k means how many objects you pick

in this case you pick 10

0!=1

so it's just 10!

[true venture]

Think of it as choosing 1 name each time

[quaint flower]

Problem is, I am doing that. But K can't be 1

[true venture]

Yes it can 10 choose 1 is 10

[quaint flower]

But then you have 10 choices

because

10!/(9!) is 10

[true venture]

Yes

[quaint flower]

wait... oh

You had 10 choices?

wait what the fuck

[true venture]

Then next name you have 9 choose 1

10, 9,8,.... 10!

[quaint flower]

Yes, but why does the formula SPIT out 10 and not 10!

by this logic

k = 1 (can't be true)

[true venture]

Because the formula is just for 1 choice, whe. You make a list of 10 names you apply the formula 10 times

[quaint flower]

...uh... 10x10x10x10x10... ten times???

no... that can't be it

that would be 10^10

[true venture]

No it reduces each time, since you chose a name previously. Once you chose the first name can you choose it again?

[quaint flower]

I know it's 10!

But I cannot apply this little shit formula

[grim oxide]

yes you can

r=10

you are asking "how many ways to pick an ordering of 10 objects if i am allowed to pick 10 objects in total"

[quaint flower]

How am I supposed to know it's 10 at a time and not one at a time? Where is the framework?

Because here's the key issue: "At a time"

[grim oxide]

it's not "at a time", it's how many you pick in total

if you were pick to 3 names we would have r=3

[true venture]

Maybe try picking a smaller number say 4 names and writing out all lists without thinking about the formula

[quaint flower]

It's just, I want to think:

10x9x8x7x6x5x4x3x2x1...

But the thing that's preventing me from doing this... IS literally something I can't explain

Because the confusion is so ingrained in me

[grim oxide]

[\frac{10!}{(10-10)!}=\frac{10!}{0!}=\frac{10!}{1}=10\cdot9\cdot8\dots 2\cdot 1]

[vital dew]

DaBeast

[quaint flower]

Well, you "Pick" something. Sure.

[grim oxide]

the formula literally gives exactly what you want to think

[quaint flower]

At this point, I am not sure if I will ever understand this.

Because I literally cannot apply a stable framework. It's impossible.

I'm not trolling, I swear, there's something wrong with me

[quaint flower]

I could say:

Oh, I can look at how many choices I have after each iteration

[true venture]

Maybe time to take a break, this stuff is confusing 😂

[quaint flower]

I have done this like multiple times....

I have not come anywhere

So like:

If I had 5 dolls, 10 nuggets.

In how many ways am I supposed to sort them? <--- this is a vague question. A vague ass question.

[quaint flower]

I could say:

Oh, in how many ways could I pick 2 dolls and 1 nugget?

Shouldn't this be like:

5x4 * 10 ways?

[vestal bronze]

@quaint flower 10! is 10p10

you're using all names out of 10

[tidal tinsel]

Suppose someone hands you two graphs (e.g. their vertex and edge sets) G1 = (V1, E1) and G2 = (V2, E2) which both have n vertices and m edges. Devise a method to check if the two graphs are isomorphic.

[frozen mason]

interesting thing i've noticed if you have the adjacency list of two graphs and you treat the coloums as blocks then if we imagine they are designs and show these 2 designs are isomorphic then they also are isomorphic in the graph sense

[rapid kernel]

How I can prove that nC(n/2) is even when n is even

[frozen mason]

what is C?

[grim oxide]

choose

n choose n/2

[rapid kernel]

Yes

[agile magnet]

n choose k = n! / (k! * (n-k)!)

So what is the parity of those terms?

For your situation

[rapid kernel]

I don't get it

[agile magnet]

Do you know what parity is?

[rapid kernel]

Like even and odd ?

[agile magnet]

Yes

So if n is even, is n! even or odd

is (n/2)! even or odd?

then is (n - n/2)! even or odd I guess but n - n/2 = n/2

[blazing rose]

Is 0 always a zerodivisor?

[agile magnet]

What's the definition of a zero divisor

[blazing rose]

0 • x = 0, x being nonzero

In a ring

Or field

[agile magnet]

well that's always true, that's not the definition

x is a zero divisor if there exists a nonzero a such that x * a = 0

What you wrote is almost a proof that 0 is a 0 divisor

[blazing rose]

Yea I already inserted 0 for a my bad

[agile magnet]

You mean for x?

[blazing rose]

Ah yea

[agile magnet]

You haven't found the non-zero a yet

What is a non-zero a that would work?

[blazing rose]

Every number in Z nonzero

[agile magnet]

Yea so let's say 1

so is 0 a zero divisor?

[blazing rose]

Yes

Thanks!!

[agile magnet]

Also #groups-rings-fields next time

yea np

[rapid kernel]

Even

If n not equal to 2

[agile magnet]

Right so you have some case work

[rapid kernel]

Okay

[agile magnet]

Ok say n > 2 and is even

[rapid kernel]

Yeah

[agile magnet]

n! is even or odd?

[rapid kernel]

Even

[agile magnet]

And you have this

[rapid kernel]

Yeah

[agile magnet]

so is n choose n/2 even or odd

Using the formula for computing n choose n/2

[rapid kernel]

Okay

[rapid kernel]

Still I don't figure out

[agile magnet]

What is the formula for n choose n / 2

[agile magnet]

Major hint

[rapid kernel]

.

[agile magnet]

Can u actually write it out with k = n/2

[rapid kernel]

So n!/((n/2)!)^2

[agile magnet]

Perfect

So n! is even

[rapid kernel]

Yes

[agile magnet]

and you said (n/2)! is even

[rapid kernel]

And (n/2)! is even

[agile magnet]

So can you conclude n! / ((n/2)!)^2 is even? Why or why not?

Again, you may have to do casework!

[rapid kernel]

Okay I try now

[agile magnet]

I'm not going to walk though all the case work for you btw

But here's one thing to think about, what if n = 2 * an odd number?

[rapid kernel]

Even but I don't not know how to generalize these wait if I don't make it then I will take help ....thank you

Is it will work?

[rapid kernel]

Not getting

[tidal tinsel]

2.1 ans 1/6
2.2 ans 1/2

need help in 2.3

[weary tiger]

good lord why did u ping me like millions of time

[rich ledge]

Man, what a lovely proof, worth every hour wasted, even though i have a digital design exam after two days.

[agile magnet]

Why give away the whole proof...

[rich ledge]

Because it was fun, that is why

[agile magnet]

This is a learning channel not a give away the answer discord

[rich ledge]

okey, am gonna delete it than, is that okey?

(by the way am new so am not used to the rules here.)

[agile magnet]

It's not an explicit rule it's just a good way to teach

[rich ledge]

good,

by the way, you were mentioning Parity and what not. as in even or odd, what does that have to do with proving that statement?

can you use general integers properties to prove that statement

i.e
even times even = even
even time odd = even
odd time odd = odd
odd plus odd = even
odd plus even = odd

from exploring that statement, i came across a lovely fact, that n! is always even (for n in N)

[agile magnet]

It was just the first idea I had to prove it

[agile magnet]

I mean this is obviously for any n ≥ 2

[rich ledge]

if you forgot that even times odd is even, it wouldn't seem so obvious, though when you notice it, it sticks out like an elaphant.

[agile magnet]

How would you forget that 😭

[rich ledge]

that was a simple fact that was taught once in the indroductory proof section of my discrete math course. i never needed that fact in any of the required proofs of that course.

[agile magnet]

But it's just how numbers work

[haughty garden]

[rich ledge]

Am never the kind of person to care that much about the specfics of numbers, i mostly care about formula's and intuition / proofs of said formula's, noticing pattarns in numbers was never my thing.

for that reason i was suprised when even times odd is even, i had to see it proved in front of me in class to be convinced.

[worn dragon]

A valid password is a sequence of between 6 and 8 symbols. The first symbol must be a letter (lowercase or uppercase), the remaining symbols can be letters or digits. How many different passwords are possible?
in this question. AuBuC is considered disjoint why?

is it cause the first set each element is gonna have 6 symbols second 7 and t hird 8

[fossil mural]

AuBuC is considered disjoint why?
...what are A, B and C?

[haughty garden]

Assuming A represents passwords of length 6, B represents passwords of length 7, C represents passwords of length 8, then yes A, B, C are all disjoint since you can’t have a password that is both 6 characters and 7 characters (or any combination of this)

[rich ledge]

yeah, when you say it that way, this makes since.

[worn dragon]

so is my reasoning correct?

[snow sleet]

yes, this is correct. Like opengangs said. You can't have a password that is both of length 6 & 7, OR a password that is of length 6 & 8, OR a password of length 7&8. I highlighted it this way because I'm explaining that A,B,C are pairwise disjoint. In general, for distinct positive integers x,y, you can't have a password/string of length equal to both x and y. That would contradict the fact that x,y are distinct in the first place.

[odd prism]

How many positive integers less than 10^n use the digit 4 at least once and 5 exactly once?

My thought is to first start with cases

One where 5 is at the right most position and once where 5 is anywhere else

So if 5 is at the rightmost, then there are n-1 positions to fill with digits 0-9 excluding 5, so 9^(n-1)

But then you would need to subtract out the cases where there are no 4s

[odd prism]

Disregard this

[worn dragon]

can someone help me with generating functions in recursion

cause I genuinely dont get it

[worn dragon]

like how do u solve this

[brave rock]

What's your favourite kind of generating function. Ordinary I assume?

If F(x) is the ordinary generating function f_0 + f_1 x + f_2 x^2 + ...

(Which is to say that F(x) is the generating function for f_n)

Then xF(x) is the generating function for f_{n-1} — typo here sorry. Gonna fix some other things

So if you simply rearrange this as saying that f_{n} = 3f_{n-1} — ignoring the zero for now — what can you say about the generating function?

[worn dragon]

what does that mean tho

[brave rock]

I made a typo please note.

[brave rock]

You do know what a generating function is, right

Like I have a series f_0, f_1, ...

And I get a generating function F(x) which corresponds to it

We say that F(x) is the generating function of f_n

Clear? If this isn't clear, I cannot help you in the least.

[worn dragon]

yeah like generating a function for a sequence I done those before

[brave rock]

No, a generating function for a sequence

Is this just a terminology thing? These things are called "generating functions." This is just their name.

[brave rock]

Anyway, what I said up here should make everything clear.

I made a typo but it's fixed now.

[worn dragon]

ok give me a second to try and understand

[worn dragon]

would it be 3xF(x)?

[brave rock]

What's 'it'

[worn dragon]

generating function

[brave rock]

Of f_n?

Yes, indeed. This is saying F(x) = 3xF(x).

Now solve for F(x).

Then you have the generating function of f_n, and you can just convert back.

[worn dragon]

how do I do that

[brave rock]

If I wrote y instead of F(x) and asked you to solve for y in y = 3xy, you'd be able to do it no problem.

[worn dragon]

y would be zero no?

[brave rock]

Yeah, that's right.

F(x) = 0

Now I want you to firstly think about what sequence this is the generating function for, and then look back on the definition and see how that works out.

[tight heart]

ive been banging my head against the table for the past 3 hours please someone help

[true venture]

Hello, let's say I have the g.f. for strict integer partitions.

A(x) = Prod_{k>0} 1 - x^k

Then I add a variable y for the number of parts.

A(x,y) = Prod_{k>0} 1 - yx^k

Obviously then taking m! For some (x^n)(y^m) gives the number of compositions of that partition, but is there a better way to write the factorial step using e^y or something?

[haughty garden]

Since G is cubic (3-regular), G has a cut vertex iff G has a cut edge. So then it suffices to show that a bridgeless cubic graph has a perfect matching. You can check that the graph satisfies Tutte’s theorem (this is just Petersen’s theorem)

[tight heart]

what's a cut edge

[haughty garden]

Just an edge such that its removal creates more connected components

[tight heart]

oh yeah okay 2 seconds of thought later i realised

[tight heart]

cool beans ill consider this 👍

thanks a lot

[haughty garden]

👍

[snow sleet]

have u figured this out yet? Ur on the right track...u can count "the positive numbers < 10^n that have exactly one 5" and then subtract off the ones that satisfy "having exactly one 5 and having no 4's". This will leave u with the ones with "exactly one 5 and at least one 4". Alternatively, you can count this directly by summing over cases where those cases are separated by the number of 4's that are in the positive number < 10^n with exactly one 5.

Try with n=4, your answer should be|| 868||. I've confirmed this by not only counting it up in two ways, but also by enumerating all possibilities via a spreadsheet. feel free to tag me if ur stuck

[amber ridge]

does this work? lol

[tidal tinsel]

7. Students at the City High School are all required to join a club, and every club has at least two
   members. It is also the case that every two clubs have at least one common member. Show
   that students from the high school can be grouped into three groups, where each student is in
   exactly one group and every club is represented in at least two groups.

[cerulean ore]

Would the centroid(s) of a tree always lie on the diameter?

[errant bear]

thanks for sharing

[dire stag]

Sorry, I'm just frustrated.

[patent marlin]

can someone dm me i have a question related to this topic

[agile magnet]

Just ask your question here bruh

[icy swift]

How many possibilities are there for 8 non-attacking colored rooks where 1 is red, 3 are blue, and 4 are yellow

Answer is 8! (8! / 3! 4! 1!)

But how come its not (8! / 3! 4! 1!) ^2

[ancient brook]

[icy swift]

since you have to n-permute the multi-set according to rows and columns?

oh wait

i mightve figured it out

[ancient brook]

Guys
Got a question
I am currently doing BS Mathematics in my national University
Will I be able to do masters in a specialised field such as CS DS or SE ? ( AI )

[ancient brook]

I have this course later on

[icy swift]

intro to combinatorics?

[ancient brook]

Discrete Math

[icy swift]

oh

ive never taken discrete math

[ancient brook]

Answer dis too sir

[ancient brook]

Lol
It's a core course for us in the upcoming semesters

[icy swift]

not sure since im also an undergrad but i'd say you should take some classes specific to one of those 3 fields

[ancient brook]

We do have minors later on for CS and DS

[icy swift]

i dont think just knowing math will give you enough knowledge to pursue masters in CS

[ancient brook]

True dat

[icy swift]

minor is probably the minimum

[ancient brook]

Yep

[icy swift]

im also interested in learning CS

so i might get a minor

[ancient brook]

Us moment

Alright
Nice talking to ya
Bai

[errant bear]

obviously

[distant otter]

Guys I would appreciate some help with a Pigeonhole Principle problem:

A student works a job for 11 weeks. He will work at least 1 hour every day but no more than 12 hours per week. Show that there is a succession of consecutive days during which the student have worked exactly 21 hours.

[dusk oxide]

let $a_n$ be the sum of games played from day 1 to $n$. Then, $1<=a_1<=\dots<=a_n<=\dots<=a_{77}<=132$.
Add 21 to all these
$22<=a_1+21<=\dots<=a_n+21<=\dots<=a_{77}+21<=153$
Hence, we have the following 154 pigeons
$a_1,a_2,\dots,a_{77}, a_1+21,a_2+21,\dots,a_{77}+21$
but only 153 possible values. Two of these numbers must equal each other. Since the sequence $a_i$ is increasing, we have
$a_i=a_j +21, i>j$
hence the number of games day $j$ to $i$ is 21.

[vital dew]

emphatic_wax

[distant otter]

I had a similar approach, thank you!

[elfin furnace]

what does the last bullet point mean?

[elfin furnace]

and ik there's the explanation but can someone further explain, and what does the upside-down A mean

[dusk oxide]

the upside down A means “for all” or “for every”. The statement says that all elements in B are in A and vice versa, i.e., A=B

[elfin furnace]

also where did the 5 come from in the last venn diagram, there are no 5s in the sets A and D

[elfin furnace]

great, thank you

[dusk oxide]

the universal set is {1,2,3,4,5} 5 is in U but not in either A nor D

[elfin furnace]

why is the set {1} not a subset of A. Is it because it is a separate set on its own, and subsets can only be formed from elements and not other sets?

[snow sleet]

suppose {1} is a subset of A, then that would imply that 1 is in A, which 1 isn't in A. Thus {1} isn't a subset of A

Remember for sets $K,L$: $K\subseteq L$ if and only if $\forall k\in K, k\in L$.

[vital dew]

logician

[snow sleet]

1 is in {1}, but 1 isn't in A...so {1} isn't a subset of A

[elfin furnace]

yeah i get it makes sense

thanks

also can someone explain how to get P(A), the answer was provided but I need a guideline

I know the power set of all the subsets

and they got 16 elements, while I got 6

[twilit sundial]

each subset in the power set contains sets as elements

for example {{1,2},{1,2,3}} is one element in the power set

[oblique sigil]

anyone awake and willing to help me with some really basic discrete math homework?

just have to say of 2 implications are valid or invalid arguements

i have answers, but not sure if they're correct

(1) if the fire alarm sounds, then everyone must leave the building. (2) the fire alarm has sounded. (3) therefore everyone must leave the building

i said this arguement is vaid, due to modus ponens

[regal pelican]

Can someone pwez explain permutation and combination asap

I have a test in like 30 mins

just the basic

[stray reef]

nobody can explain the basics to you in half an hour

[thorny hollow]

Can someone help me? What the notations (SoR)(y), R(y), S[R(y)] means? I checked up a more beginner friendly book that also approaches the Relation theory but it also didn't show those notations

[latent cosmos]

looks like it's some sort of notation for composition of relations

(SoR)(y) = x appears to be the combined relation acting on y to produce x

[thorny hollow]

Ic

[latent cosmos]

oh, i get it now

it's supposed to be $S\circ R$

[vital dew]

lifefuel

[latent cosmos]

recall composition of functions where the circle is used too

if the notation $(f\circ g)(x)$ looks familiar, that answers your other concern too

[vital dew]

lifefuel

[calm chasm]

I need to look for three things in a definition. Context, category and a verb. Finding the verbs aren't very difficult. But the context and category I'm not very strong at. Can someone explain the difference between a category and context in a definition?

[fossil mural]

...i have never heard this description before at all
who told you that a definition would contain those things?

[calm chasm]

My discrete math professor

And his book

I'll send you a passage

[fossil mural]

hm
ok yeah it seems like in order to make it all start with "c" they've used some words that aren't really what i would have used

what they're calling a "category" seems to basically just be, a type of thing
so something could be a number, or a polynomial, or a set of numbers, or it could be a statement (that's either true or false), etc.

[calm chasm]

Oooooo

[fossil mural]

and the "context" is just... the assumptions of the definition
so if you're defining what the sum of two numbers, "x + y", is, the context is that x and y are numbers, and the "category" is that x + y is a number

[calm chasm]

That's a good point

I see

Wow okay

[calm chasm]

Can I give you a definition and tell you what I think the context and category are?

[fossil mural]

yeah ok

[calm chasm]

Would S being a set be the context?
The set would be the category?

[onyx vault]

there are `N` total rounds and `N - L` blank rounds, and `L` live rounds (actual bullets that result in game over), the bullets are placed randomly.
the chamber is round, meaning it will rewind back to the first bullet after it has been moved past the last bullet.
a random player between the AI and the user starts the game.
each player can take any of these actions on their turn:
1. shoot themselves. if the shot round is not live, they can play another turn
2. shoot the other player. if the shot round is not live, it will be the other player's turn
3. roll the revolver chamber, results in the current round pointer being randomized. then it will be the other player's turn
4. check the bullet inside the revolver chamber, it tells you whether the next round is blank or live, but it will then be the other player's turn

can someone help me with finding the most optimal playing strategy for this modified version of russian roulette?
flowchart: https://downside.phazor.ir/uploads/ap20t-image.png

[eternal thicket]

Let $l$ be the length of the maximal path in the graph $G$. How to prove that $\chi(G) \leq l$?

[vital dew]

alisas

[young field]

based on this modified version, wouldn’t the optimal strategy be for both players to agree to adhere to rule 3?

both players would survive

unless the goal of the game is to strictly have the other player shoot themself

[amber rivet]

You would need something like a 50 move rule for rolling / checking to avoid the infinite loop

[quaint flower]

I'm having a huge problem with combinatorics and probabilities. According to my answer sheet, this number is wrong. It's supposed to be 0.1 not 0.2.

Here is the question:
If you have 2 red balls and 3 black balls, what's the probability of getting both of red balls?
In other words, P(2 red balls)

I usually think like this:

How many ways is there to getting 2 balls that are red?
Divided by

How many ways is there to getting balls if you could choose two

[fossil mural]

...what are the 2 ways of getting 2 red balls?

[quaint flower]

If I think like that, then my whole understanding of combinatorics falls apart.

Sure, I might be able to think probabilities. But I would no longer be able to be consistant afterwards.

We are choosing 2 balls, and the balls need to be red, both of these choices.

I would assume the result would go: C(2,1) * P(1,1) for the red balls. You have 2 choices first, then you have 1 choice. In such a scenario.

[fossil mural]

...that sounds like you probably didn't understand it to begin with
in what way is the number 2 connected to the act of getting 2 red balls, if it's not "there are 2 ways of doing it"?

[quaint flower]

No idea...

Because it always seems to fall apart.

[fossil mural]

...so basically you're just throwing numbers around and multiplying them for no reason and you have no idea what any of it means?

[quaint flower]

I mean...

If I framed the question like this:

If you have 4 red balls and 4 black balls.

A) How many ways can you get 2 red balls?

Order doesn't matter.

Answer would be: C(4,1)*C(3,1) in my brain.

because, I take the first red ball. Then, you have three balls left to choose from.

[fossil mural]

...and what about the "order doesn't matter"

[quaint flower]

It's a combination

[fossil mural]

(also do you have any idea why multiplication corresponds to "do one thing then another thing"?)

[quaint flower]

Well multiplication is basically:

AND

To put it very simply

I take a red ball and I take an other red ball.

Order does not matter, because taking b1 and b2 is the same as taking b2 and b1. Same result. We don't care about order.

Duplicates do not exist.

[fossil mural]

(but... why?)

[fossil mural]

so what part of C(4,1) * C(3,1) is accounting for that

how would the calculation be different if you did care about the order

[quaint flower]

Well, it is accounting for that...?

[quaint flower]

If order mattered, then we wouldn't be using C

We'd be using permutations

[fossil mural]

so P(4,1) * P(3,1)?

[quaint flower]

yes

and we're not supposed to put the balls back everytime

otherwise, we'd have P(4,1)*P(4,1)

if order mattered

[fossil mural]

...ok well C(4,1) and P(4,1) are the same number, they're both 4
so are C(3,1) and P(3,1)

[quaint flower]

They are, but the reason why I use C and P is to be correct

It's to ensure I do not mix up permutations or combinations, because these shits can be quite sneaky.

It's my way of coping and it has worked.

[fossil mural]

well it hasn't worked

[quaint flower]

But it has

Before I did probabilities

[fossil mural]

well it hasn't worked for getting the right answer

[quaint flower]

And I don't understand why its so inconsistant then

[fossil mural]

your answer for how many ways there are when order doesn't matter is 12, but the correct answer is 6

[quaint flower]

It's different rules everytime, I can't possibly find a good pattern of learning here.

[fossil mural]

it's always the same rules actually, the rules just look absolutely nothing like what you're currently doing

[quaint flower]

Well no it isn't, otherwise I would have had found a pattern.

A long time ago

[fossil mural]

well apparently you didn't

[quaint flower]

For example:

In a code lock there's 4 digits.

And, each digit, you can pick any digit from 0-9.

How many codes exist on this lock?

P(10,1) * P(10,1) * P(10,1) * P(10,1)

10^4

Apperently it works here.

[fossil mural]

to be fair, it's actually a rather complicated pattern if you try to describe it without ever mentioning the idea of counting, given that combinatorics is about counting

[quaint flower]

Well, I don't know then

I can't find a pattern.

Everything is so inconsistant

And I have counted... Problem is, there is no stable ground.

[fossil mural]

ok well let's look at a smaller example

let's say we want to find the number of ordered pairs of letters that are either A, B, or C

we can enumerate these and see that there are nine of them: AA AB AC BA BB BC CA CB CC

[quaint flower]

If I have 4 books of genre A, and 4 books of genre B

In how many ways can I get different books if I pick 2?

That would be: C(4,1)*C(4,1)

The requirement is, that the books are different. Hence why 1.

[quaint flower]

I cannot possibly use this knowledge to generelize anything though.

[fossil mural]

but there's a pattern here - for each possible choice of first letter, we get three different pairs
A: AA AB AC
B: BA BB BC
C: CA CB CC

and there are three choices of first letter

so there are 3 * 3 = 9 pairs in total

if we wanted to find ordered collections of three, then there are 27: 9 that start with A (one for each pair), 9 that start with B (one for each pair), 9 that start with C (one for each pair), 9 + 9 + 9 = 9 * 3 = 27

[quaint flower]

Or, I could think:

P(3,1) * P(2,1)

But that doesn't work either

[fossil mural]

this is why multiplication is relevant to combinatorics: multiplication is how you count a set of ordered pairs

[fossil mural]

that's not a "thought", it's a pile of symbols

the reason you're not finding a pattern is that you're looking for a pattern in piles of symbols

[quaint flower]

I'm literally trying to translate stuff over to math

[fossil mural]

the pattern is deeper than that, it's in the meaning of the problem and it's in the idea of counting

[quaint flower]

And the translation is not working.

[fossil mural]

...that's because you're "translating" it by writing down random symbols

[quaint flower]

Well I cannot understand how to translate this to math. I have no general pattern that can translate this

I have tried multiple times, but it hasn't worked

[fossil mural]

ok well here's the more general statement

when you have two sets, let's call them X and Y

and you want to count the number of things in the set of ordered pairs (x,y), where x is an element of X and y is an element of Y

the number of those pairs is the product of the number of elements of X and the number of elements of Y

[quaint flower]

Okay but this gives me nothing... It's stuff I already have memorized: I make one choice and then an other.

I need to use the symbols, or everything is just going to fall apart.

[fossil mural]

what makes it fall apart isn't a lack of symbols, it's a lack of anything other than symbols

if you only do steps that are justified in terms of actual sets with numbers of things in them, you will get consistent answers

[quaint flower]

Well I can't get consistant answers

So Where is the pattern

[fossil mural]

anyway, yes, this is the precise formulation and justification of a rule that you were already aware of but didn't actually understand: that if you do an X, and then do a Y, that corresponds to multiplication

[fossil mural]

...there isn't just one "the pattern"

[quaint flower]

Well multiple, and I cannot generelize anything.

[fossil mural]

ok well here's a general pattern for you: the size of the cartesian product $X \times Y$ is the product of the size of $X$ and the size of $Y$

[vital dew]

bee [it/its]

[quaint flower]

Right that pattern only works on some questions

but not all questions

[fossil mural]

it always works

it will always be true that |X \times Y| = |X| * |Y|

[quaint flower]

Well it hasn't worked for me, so it's not the right explanation for me.

[fossil mural]

it will not always be true that the set you're trying to find the size of is X \times Y

for instance you might be asked about the set of unordered pairs
(1,2) and (2,1) are distinct ordered pairs, but the same unordered pair, so counting unordered pairs is not the same thing as counting ordered pairs

so if you're asked to count unordered pairs and you count ordered pairs instead, you will get a number that is the correct number of ordered pairs, but it will not be the correct answer to the question, because the question was how many unordered pairs there are

[quaint flower]

For example, if I have 3 letters I can use and 3 numbers of my choice(digits 0-9)

(Assume that there are 26 letters in the alphabet)

Then:

P(26,1) * P(26,1) * P(26,1) * P(10,1) * P(10,1) * P(10,1)

Why P(26,1)?

Because, I can only chose 1 letter from 26 in every iteration.

What I am saying is, the problem is something like this:

AAA-000

^ This is what I am trying to frame here.

[fossil mural]

ok so 26 * 26 * 26 * 10 * 10 * 10
this is the number of ways to choose one of 26 things, then one of 26 things, then one of 26 things, then one of 10 things, then one of 10 things, then one of 10 things

so yep, that would be the number of ways to choose codes like AAA-000

[quaint flower]

right

And there is a problem now, I cannot apply those principles to the ball example

it is impossible (for me)

If I have 4 green balls, 4 red balls

a) How many ways can you take 2 balls?

Ball 1: C(4,1)
Ball 2: C(3,1)

[fossil mural]

a) How many ways can you take 2 balls?
...this question is ambiguous

does order matter, or not?

[quaint flower]

It does not

C(4,1) * C(3,1)

[fossil mural]

ok well we don't know how to count unordered pairs yet

you can't just say "C" and expect that to magically work

if order matters, then the answer is 4 * 3: you pick one of four things, then one of three things

[quaint flower]

so... If order doesn't matter

the answer.

is C(4,2)

?

[fossil mural]

...ok yep that does work
by the definition of C, C(4,2) is the number of ways to choose 2 things from 4 things, with order not mattering

[quaint flower]

Let's stop there.

This is the root issue. When are you not supposed to take away vs not taking away?

That's the confusion

[fossil mural]

...what do you mean by "take away"?

[quaint flower]

like

C(10,1) * C(9,1)
vs
C(10,2)

See what I am trying to show here? It's this weird thing to do with:

I make 1 choice and then 1 choice after

[fossil mural]

not really

i guess i could just tell you what both of those mean

C(10,1) * C(9,1) is the number of ways to choose 1 thing from a set of 10 things, then 1 thing from a set of 9 things, so 90

C(10,2) is the number of ways to choose 2 things from a set of 10 things, with the order of the 2 things not mattering, so 45

if we look at a smaller example so i can write out the sets explicitly

C(4,1) * C(3,1) counts the set (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3) (4,1) (4,2) (4,3)

* counts ordered pairs, C(4,1) is a choice of one thing from a set of 4, C(3,1) is a choice of one thing from a set of 3

C(4,2) counts the set {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
two things from a set of 4, i'm using {} to indicate that the order doesn't matter - {1, 4} and {4, 1} are the same

[quaint flower]

So when order matters, I need to look at each induvidual thing right? Each induvidual thing tells me, how many choice appourtunities do I have?

hence why: We have stuff like: 10x10x10x10 for code combinations.

vs

I have 4 women and I pick out 2. How many ways can I do that, if order doesn't matter?

C(4,2)

[fossil mural]

...well i mean if you expand out what "C(4,2)" is then that also involves counting the choices for each individual thing, just with an extra factor to account for order not mattering

[quaint flower]

not

C(4,1) * C(3,1)

[fossil mural]

but yes it is definitely true that if you do multiple things in sequence, which is equivalent to choosing things with order mattering, then you can count the number of ways to do that by multiplication

[quaint flower]

Yeah I know, it's the combination formula

but the issue is, I want to make sure to not make stupid mistakes, such as:

C(4,1) * C(3,1)

Where, I go:
One choice per iteration:
Alright, for the first choice I can choose 4 things.
Alright, for the second choice I can choose 3 things.

^ Because, this belongs in permutations. Not in combinatorics, right?

[fossil mural]

if we just ignore the fact that we already know a formula for C(4,2) and think about how you'd derive it if you didn't know

the set of ordered pairs of two distinct things from a set of 4 is (1,2) (1,3) (1,4) (2,1) (2,3) (2,4) (3,1) (3,2) (3,4) (4,1) (4,2) (4,3), there's 12 of them

[fossil mural]

yeah that would get you the result with order mattering

[fossil mural]

we want unordered pairs, so this isn't quite right: (1,2) and (2,1) are the same, for instance

[quaint flower]

This is what has gotten me confused the entire time though!

I'm mixing operations from permutations and combinations, hence why I do not get consistant results

I need to make specific rules for each of these operations.

[fossil mural]

but in fact, each unordered pair is represented exactly twice:
(1,2) (2,1)
(1,3) (3,1)
(1,4) (4,1)
(2,3) (3,2)
(2,4) (4,2)
(3,4) (4,3)
so the number of unordered pairs is actually exactly half of the number of ordered pairs, 12 / 2 = 6

[fossil mural]

well you can use them together as long as you're consistent about it

[quaint flower]

Problem is, I cannot do that

otherwise we'd get this paradoxical issue of:

C(4,1) * C(3,1)

But, am I really describing two sets multiplied with eachother?

two different sets

[fossil mural]

...well what are you trying to count

C(4,1) * C(3,1) counts the cartesian product (set of ordered pairs) of a set of 4 things and a set of 3 things

[quaint flower]

so, essensially... we are constructing sets and multiplying them

and we get the total amount of elements

[fossil mural]

well we're counting how many elements sets have, yes
that's what combinatorics is

[quaint flower]

if we go back to the code lock example:

10^4 permutations exist on that lock.

So, if order matters, I can solve this by counting how many digits we can choose in every single digit, right?

[fossil mural]

yep
choosing a lock is the same as choosing the first digit, then choosing the second digit, then choosing the third digit, then choosing the fourth digit

10 * 10 * 10 * 10

which is 10^4

[quaint flower]

Hm, yes

But, if order did not matter.

Would this be simply impossible to compute?

because, it makes no sense

a code lock, must have an order that matters

[fossil mural]

well... well there is an answer, it's just difficult

[fossil mural]

meh
it doesn't have to be a lock, we can just ask about "4 digits, with order not mattering"

[quaint flower]

That would be C(10,4) right?

We have a group of 10 numbers, from 0-9

We choose 4 numbers in this new group.

10 elements

We choose 4

[fossil mural]

C(10, 4) works if we also require the digits to be distinct

since that's what C counts, a choice of 4 distinct things from a set of 10 with order not mattering

[quaint flower]

if they are unique, then that goes down

[fossil mural]

so 1111 would just not be a valid code at all for this lock
and 1234, 4213, 4321, etc. would all be the same code

[quaint flower]

C(10,4) * C(9,4) * C(8,4) * C(7,4)

right?

[fossil mural]

uhhh

...think about what set that actually counts

[quaint flower]

Well, I don't really know how to solve that.

Each digit needs to be unique

so, C(10,1)?

[fossil mural]

it's just C(10, 4)

C(10, 4) counts the number of ways to choose 4 distinct things from a set of 10

[quaint flower]

So I had the right answer all along?

[fossil mural]

the thing which would require us to do weird extra stuff is if we wanted them to not be required to be distinct

[quaint flower]

like, stars and bars stuff?

[fossil mural]

well like, if we wanted to allow 1111 as a code of this lock

[quaint flower]

we'd have C(1,4) no?

we can pick 1 digit only

[fossil mural]

...ok well your notation there is just wrong

C(1,4) is the number of ways to pick 4 distinct things from a set of 1 thing

which is 0 because there are no ways to do that

[quaint flower]

Well, then I would probabaly jump over that example

it...isn't important, I hope?

[fossil mural]

and yes, we can just "pick the first digit, then the second digit, then the third digit, then the fourth digit", but if we do it like that, we end up with order mattering

in fact we'd just get 10^4

[quaint flower]

which would be stupid, it wouldn't be a combination anymore

So bee, can I start applying sets to every "choice appourtunity"?

only in permutations though

while in combinations, I'd treat it as one huge group?

and select a couple of elements from there

[fossil mural]

..."applying sets"?

i guess i have kind of given a lot of advice on how to solve problems but also like, "it's about sets" is less of a technique for answering questions and more just, objectively what the subject is about

[quaint flower]

I am trying to say:

Code lock example:

[10,9,8,7,6,5,4,3,2,1,0] * [10,9,8,7,6,5,4,3,2,1,0] * [10,9,8,7,6,5,4,3,2,1,0] * [10,9,8,7,6,5,4,3,2,1,0]

For every set, chose 1 element.

^ ONLY if order matters.

If order doesn't matter:

Group all elements, (10 elements) and chose 4 of them.

[fossil mural]

i don't really see how that's "applying sets" but yes that is the correct way to compute it

[quaint flower]

Are you seeing what I am trying to describe tho? Like, it's an issue with computation.

[fossil mural]

well you can also do it by thinking about multiplication, you just have to think a bit more about how to handle order not mattering

[quaint flower]

That's the thing, when order does matter. You have slightly different rules. You need to think about each induvidual case.

Because, it's ordered. Like there's a line of people.

[fossil mural]

if we want 4 distinct elements from a set of 10, with order mattering, we have 10 choices for the first one, 9 choices for the second one, 8 choices for the third one, 7 choices for the fourth one
10 * 9 * 8 * 7

[quaint flower]

If order matters, and each element need to be different. Then our amount of choices go down per each iteration

If order doesn't matter, then it's just all about grouping stuff together. Choose a couple of elements.

[fossil mural]

to get 4 distinct elements with order not mattering: observe that for any set of 4 distinct elements, there are exactly 4! = 24 ways to arrange it, so "10 * 9 * 8 * 7" counts each set of 4 distinct elements exactly 24 times
so 10 * 9 * 8 * 7 / 4! counts each set of 4 distinct elements exactly once, which is what we wanted

[quaint flower]

Well, 1111, how many ways are there to arrange that? If we treated these elements as different.

4! times

[fossil mural]

this is how you would actually compute C(10, 4) from first principles, it's how you derive "n!/k!(n-k)!"

[quaint flower]

duplicate elements, they need to be removed

right?

in the example of 1111's

[quaint flower]

I have a memory rule

If order doesn't matter, it's like you're blind picking

right?

[fossil mural]

...?

[quaint flower]

If order doesn't matter, you don't give identity to the elements?

They are just "elements", nothing else?

Or, is it just... About the order they are placed in

[fossil mural]

...not really
you just don't care about the order

so if order does matter, that's the same as like, the first thing you get, you write "1" on it, the second one, you write "2" on it, and so on

[quaint flower]

Yeah, you arrange them in different classes

right?

or, catagories

sorry

[fossil mural]

if order doesn't matter, it's like you just throw them all in a jar and declare that the only thing that matters is what's in the jar, not "what order are the things in the jar" which doesn't even really make sense

[quaint flower]

or just... you just compare if:

Is 1234 the same as 4321?

If no? It's a permutation

[fossil mural]

yep

[quaint flower]

Yeah that's the best way to go about it imo

at least for me

[fossil mural]

yeah i agree

that's just like, directly what it's about
if you put the things in a different order, is that different (order matters), or the same (order doesn't matter)

[quaint flower]

But we need to solve this stupid paradox where I do:

C(4,1) * C(3,1)

xD

Instead of C(4,2)

On that question we talked about

[fossil mural]

i'd say the thing to remember there is just

"C" doesn't magically make the entire expression not care about order

it's just that C itself doesn't care about order

so C(4,1) is the number of ways to choose 1 thing from a set of 4 things, with the order of the 1 thing not mattering

...there's only one order that you can put one thing in so it ends up just being, 4

[quaint flower]

problem is, I am having trouble with these steps ^

[fossil mural]

* always means that order matters

[quaint flower]

I am very afraid to mix up the computation of permutations and combinations

[fossil mural]

you can do stuff like the definition of C where you count how many ways there are to do something with order mattering and then go back and make the order not matter by dividing by the number of ways to arrange a thing, but * just by itself cares about order

[quaint flower]

I could, but, I want to be quick and lazy xD

and just write out C(4,2)

[fossil mural]

yeah writing it as C(4, 2) makes a lot of sense

[quaint flower]

With the understanding, that, order doesn't matter here. So, you don't write multiple expressions. ONLY one.

But that depends if there's one or two sets.

and so on

[fossil mural]

that's like, why the function C even exists, it comes up a lot

[quaint flower]

Yeah, I understand that.

I'm just trying to justify why I would write C(4,2) instead of C(4,1) * C(3,1)

^ XD

[fossil mural]

because in C(4, 1) * C(3, 1), the * means order matters

which is wrong because we want the order there to not matter

[quaint flower]

So, the reason why we multiply is because we choose A and then B.

A and B are distinct automatically, we have automatically applied an order here.

Which we do not want.

[fossil mural]

yep

because * counts ordered pairs

[quaint flower]

So, can I say, if we have 2 groups:

A:
(3 people)

B:
(4 people)

In how many ways can I take one person from group A and group B?:

It would be: C(3,1) * C(4,1)

Because we have two distinct sets.

[fossil mural]

yep

[quaint flower]

But, since we have a multiplication in between and two functions. Can it say something about the order for group A and B?

not the people in it

[fossil mural]

well we're picking a person from group A, then a person from group B

which is fine because given an unordered pair, we can just arbitrarily declare that the person from group A is first

[quaint flower]

Ah

So we can make the order matters, JUST not for the elements in them

err... if you can say so

[fossil mural]

in the case of C(4,2), it's different from 4 * 3 because (1,2) and (2,1) are the same unordered pair but different ordered pairs
but (A1, B2) and (A2, B1) aren't the same unordered pair

[quaint flower]

I haven't gotten into set theory yet

I'm still on the combinatorics part

[fossil mural]

(...that's a somewhat weird order to do things in)

[quaint flower]

yeeaaa

[fossil mural]

well you don't really need to know that much about sets for this, just the intuitive concept of a collection of things should be enough

[quaint flower]

yes

I think I'll try to melt a new understanding of the subject into my head

I want to structure shit in my head, like programming

[fossil mural]

honestly mathematics is pretty similar to programming in some ways

[quaint flower]

I do programming

Python, so

[fossil mural]

they're both "precise" in a way that you don't really see anywhere else

mathematical objects have the same kind of quality that a computer does of, it doesn't care about the context or guessing what you meant or whatever, it just follows some set of rules, with no exceptions

[quaint flower]

And I am usually quite a linear thinker in math

I think in patterns and I can somehow apply them well

hence why I got a B in math 4, before discrete math
^ At school.

there's math 1,2,3,4,5

I have completed all of them, except 5. the one I'm undergoing in.

[fossil mural]

and the fact that there really are no exceptions is what lets you build huge structures - programs that depend on libraries that depend on libraries and so on totalling millions of lines of code; mathematical proofs that refer to previous results that refer to previous results totalling thousands of pages; because at any one location, you don't need to understand the entire system, you just have to understand the interfaces - if you know what a function does, you don't need to know how it achieves that in order to use it; if you know the statement of a theorem, you don't need to know how it's proven in order to use it
if you tried to build something like that out of more "human" things, objects that have any sort of edge case, it would fall apart instantly

[quaint flower]

Well, this is what's happening. I don't understand where those stuff come from. How to derive them.

I just, know how to use them and apply them.

The theoreoms and so on

[fossil mural]

...well the problem with just trying to remember the results and not the justifications, even though it is technically workable, is that you end up not having any checks on whether what you're doing makes any sense

it's a lot easier to misremember the statement of a theorem that you're just thinking of as some mysterious black box, than to misremember a proof and end up with a valid proof of a false result

[quaint flower]

I do have some understanding of the things I'm given, it's just... Yeah.

I'm in HS btw

so

[quaint flower]

By the way, I think I am starting to see something

So with the C(4,2) operation.

You can say that you have 4 people to choose from, then 3 people, then 2 people in an unordered group.

Right?

But with the

P(4,2) operation.

You have 4 people to choose from at first, 3 people to choose from at second. But, in an ordered group.

[cobalt cipher]

nesymerp discrete math god???

[quaint flower]

💀

xD

[upbeat pine]

to answer this do i have to write only the set or the explanation behind it? im not familiar with proofs at all and we were assigned this before seeing something like it in class

so i dont need help with the problem itself just what its askign lol

[cobalt cipher]

Idk it depends on the instructor no

[low tree]

guys, need a suggestion. I need a good source to learn and understand generating functions, and reccurrence relations

[shadow lion]

probably just the set?

[hasty thistle]

Generating Functionology perhaps?

[low tree]

will give it a go

[pastel coral]

The amount of Galois Fields of order less or equal 100 is finite. True or false?
Anyone that could give me a hint? I suppose it's false, but I can't really argument it why that is.

[fossil mural]

...just to check: is the question how many there are up to isomorphism, or are we considering two fields to be "different" if they have different elements even if they're isomorphic

i assume up to isomorphism because otherwise the question isn't interesting at all (there's a proper class of fields isomorphic to GF(2)) but 1. worth checking 2. if it is up to isomorphism then that is an important part of solving the problem

[pastel coral]

We consider them different even if they are isomorphic

[fossil mural]

oh huh

ok well in that case: you can make a field isomorphic to GF(2), and therefore of order 2, from any two objects
so if you can work out how to do that, it's then fairly easy to prove that there are infinitely many of them

[pastel coral]

oh right, makes sense, i'll get to work with this

thanks a lot

[unique spindle]

Working on these kind of questions, somebody has a good source or video to better understand what is going on? ❤️

Or is #proofs-and-logic a better channel for this?

[gritty crescent]

#proofs-and-logic would be more appropriate, but this channel works fine too

[coarse grail]

Let $a_n$ be the number of positive divisors of $n!$ for all $n$, and $(u_n)$ defined for all $n$ by $u_n=\frac{a_{n+1}}{a_n}$. Can you help me to show that the subsequential limits of $(u_n)$ are 1 and the $\frac{k+1}{k}$ with $k\in\mathbb{N}^*$ please ?

[vital dew]

TimourX

[coarse grail]

I've found subsequences that converge to 1 and the $\frac{k+1}{k}$, but I can't manage to show there are no other subsequential limits

[vital dew]

TimourX

[coarse grail]

Maybe it's more appropriate if I post this exercise in #elementary-number-theory

[dire stag]

All of these could be wrong, but I'm particularily stuck on c

How can the cartesian product have a minimum AND maximum cardinality?

Isn't there supposed to be a fixed number of possible doubletons?

[pale monolith]

No one said the minimum can't be equal to the maximum

[dire stag]

How can I find the # of pairs, if I don't know the value of B, when it's just a cardinality?

Do I just do | A | multiplied by | B | ?

Yep that works!

Now I just need to figure out parts a and b

[dire stag]

The last one is confusing me

Top left for some reason is NOT 4

However the maximum is 9

Sorry, top left is not 4

It should be 4 Impossible

A U B is the set containing all elements which are elements of A OR B or both

Set A has the smallest cardinality of 4

Could it by any chance also be 0?

[pale monolith]

B has five elements

Each of those five elements will be in A U B

[dire stag]

Isn't it optional to include B?

Which in this case would make the set of 4?

[fossil mural]

A union B is the set of things that are elements of A or elements of B

anything that is an element of B is either an element of A or an element of B

so every element of B is an element of A union B

[dire stag]

🫠

ahhhhhhhhhh.... Thanks. I'm noting this down. Thank you so much!

[agile magnet]

idk what you mean by optional

maybe you're confusing this with how we use "or" in English sometimes

but what is meant there is logical or

[dire stag]

I assumed that A U B meant: "A or B or both"

[pale monolith]

or in math is never exclusive

[pastel coral]

Given the set $V={1,2,3,\dots,100}$. If we choose a random permutation, what's the chance that this permutation in the cyclic notation only contains cycles with length $\leq 50$?

[vital dew]

cedric_

[pastel coral]

I have no clue at all on how to start this.

Does it have to do with the 100 prisoners riddle?

[haughty garden]

The complement might be easier to deal with. For a given permutation, there is at most one cycle of length > 50. So for a fixed k where k > 50, the probability of a cycle of length k is 1/k

[pastel coral]

Thanks, but I found the answer through this https://www.youtube.com/watch?v=iSNsgj1OCLA&list=TLPQMjAwMTIwMjTZm3giTpiCJw&index=2 video

That was interesting

[vital dew]

cedric_

[pastel coral]

forget this^^

[frozen mason]

I think question 4(ii) is worded incorrectly or wrong because the anwser is n = 10 according to the textbook but clearly there exists codes for n less than 10 which have the property that it can correct and detect up to 1 error

[distant otter]

Practicing some induction proofs, does this look correct to you guys?

[ivory nacelle]

the largest union isnt 9 ?

[ionic lintel]

Is it true that:
(aCb)*((d+1)C(a-b)) = (d+b)Cb
?

nCm is the binomial coefficient.

[fossil mural]

no
set a = 2, b = 1, d = 1, then 2C1 * 2C1 = 4, and 2C1 = 2, and 4 != 2

[fresh hull]

Looks good

You have used p(k) to prove p(k+1) which is correct

[distant otter]

Thanks for the feedback! Love working through these problems

[fresh hull]

Ye math induction is fun :)

[quiet eagle]

How do you usually show that "P = NP implies that a given computational problem has a polynomial (deterministic) algorithm"? Since there are only decision problems in NP I can't reduce that given problem to a problem in NP.

Also is this the correct channel for that?

[raw kindle]

Hello, english is rather difficult for me. Can you help me decipher what "So" indicates in this?
If all wolves are hungry, so are bears. I have the following:
A(x): x is an animal B(x): x is a bear H(x): x is hungry W(x): x is a wolf
(∀x)((W(X) →H(x)) →(∀x (B(x) →H(x))

[iron lake]

Need help asap

[vital dew]

cedric_

[haughty garden]

You can go from the decision problem to the optimisation problem with a binary search. Since P = NP, we solve the decision problem in polynomial-time. By the solution of the decision problem, we decide which half we want to search on with a binary search, giving us a polynomial time algorithm to solve the optimisation problem.

[agile magnet]

do you know what NP-complete means?

combine that with the fact with P = NP and you're basically done (try and if you still can't get it, ping me, but try first)

[hard hazel]

How would I describe a set of the xy plane

would it be {(x, y) | x,y ∈ℝ}

[agile magnet]

x, y means nothing

Do you mean ordered pairs? Then put in parentheses

[hard hazel]

I suppose?

[agile magnet]

What you've described (assuming you change the x, y to (x, y)) is the line y = x

[hard hazel]

yes

[agile magnet]

Not the whole plane

Ok cool as long as we're on the same page

[hard hazel]

wait

but then how to describe the whole plane

[agile magnet]

Well do you need the restriction y = x?

Do you need any restrictions at all?

Other than x, y ∈ ℝ

[hard hazel]

hmmm

yeah I guess the y = x is restricting it to just a line

[agile magnet]

yup

[hard hazel]

I see

thanks

[analog hound]

Question on notation. Does the regular expression 01* represent the language containing epsilon, 01, 0101,... or does it represent 0, 01, 011, 0111,...?

[haughty garden]

epsilon is not in the language

the second one is correct: it represents the language containing 0, 01, 011, etc.

[agile magnet]

The first language you describe would be (01)*

[quiet eagle]

Are "optimisation algorithm" and "computational algorithm" synonymous to you?

[haughty garden]

well, computational algorithm isn't exactly a well-defined term

I assume you're talking about decision, optimisation, search problems

[quiet eagle]

We use "Combinatorial Optimization". It is defined there

[haughty garden]

ok, so how do they usually define "computational algorithm"

[quiet eagle]

Are screenshots ok?

[haughty garden]

sure

[quiet eagle]

@haughty garden So the difference between "computational alg." and "optimisation alg" is that an "optimisation alg." outputs the best of the feasible solutions, while the "computational alg." just outputs one out of the feasible solutions

[quiet eagle]

Hi, I used NP-completeness for the other direction. I proved that that given problem is NP-hard. I don't know how I could use your hint for this direction though.

[analog hound]

I see, thanks

[solar marsh]

I have been able to demonstrate that there exists a perfect matching
that includes $e_{1}$ and that there exists another perfect matching that does not includes $e_{2}$ using Hall's theorem. However, I cannot find a single matching that
satisfies both conditions at the same time.

I appreciate any hints.

[vital dew]

Kevin

[heavy isle]

hey guys, Im trying to self teach some graph theory. it says that a graph G is a set V with an irreflexive symmetric relation. However, this definition would only apply to graphs without self-loops right?

becase a self loop would make it a reflexive relation

[agile magnet]

yup!

exactly right

[heavy isle]

Ok and same for the symmetric part

If we had a directed graph then symmetry wouldn't hold anymore right

[agile magnet]

ya

It could hold

[heavy isle]

Because you might have (v1, v2) but no (v2, v1)

[agile magnet]

but it doesn't necessarily have to

[heavy isle]

Oh right

[agile magnet]

subtle difference there

but yea

[heavy isle]

Ye got it

It could hold

If there's at least one instance of (vn, vm) (vm, vn)

[agile magnet]

not at least one

remember, the definition of a symmetric relation is a for all statement

a universal statement

[calm chasm]

I'm stumped. From the 3 q's I found, what would exclude them from being the inuque q that satisfies those two conditions

[agile magnet]

really couldn't have taken a screenshot or something?

[agile magnet]

only one of those q's is an integer

that's the key

[calm chasm]

I didn't feel the need to download discord on there

Omg

You're right

True

Wait

So the hint they provided is it can't be -33 because the second condition.

Any idea what that's about?

[agile magnet]

what hint?

anyways if q = -33 then what is r?

and is that r in the right range according to the theorem you stated?

[calm chasm]

It's not posted. But that was a hint given. I understand it now.

[quiet eagle]

@agile magnet I'm sorry, but could you please elaborate

[agile magnet]

tell me what you have so far

[calm chasm]

If we let b be 3, r could be 0,1,2 BUT 0 isn't a integer.

[agile magnet]

0 is an integer

the issue with q = -33 is that then you'd have r = -1

which isn't allowed

[quiet eagle]

I guess I could show that it's NP-hard, as that is defined for computational problems as well (edit: I think I'd rather need NP-easy)

[agile magnet]

ok so if you have a computational problem X

actually wait no back up

if P = NP

what does that say about algorithms for NP complete problems?

[quiet eagle]

They can be polynomial

But they dont even have to be NP-complete for that to hold

[agile magnet]

so if we have an NP complete problem, what can we do with an arbitrary problem and that NP complete problem?

(reductions, the complete part of NP completeness is important here)

so I give you an arbitrary decision problem X in NP

and you know you can solve NP complete problems in polynomial time

do a reduction

[quiet eagle]

First thought would be to reduce from any problem in P = NP to my given problem

wait no different direction

[agile magnet]

yea

reduction directions are like plugging in USB sticks, you'll get the direction wrong the first time no matter what you do

[quiet eagle]

lmao that is so true

[agile magnet]

(I literally just googled the definition to make sure I got the direction right)

[quiet eagle]

But can computational problems be NP-complete? Or is that just for decision problems too?

[agile magnet]

by computational problems they meant decision problems

is that the hold up here?

[quiet eagle]

relatable

[agile magnet]

everything we are talking about right now is decision problems

[quiet eagle]

Wait, who said that

[agile magnet]

counting problems are beyond our scope rn

I mean it's just implied by the question

reducing from a counting problem to a decision problem / vice versa makes no sense

[quiet eagle]

But I need to show it for a computation problem

To be clear it's not an abstract theorem but a concrete problem, which I shortened to "given computational problem"

NP = P should imply that my given problem has a polynomial algorithm

[agile magnet]

Is your given problem a decision problem?

(all the details would have been good to know)

[quiet eagle]

It's a computation/optimisation problem, which finds a subset X of the vertex set of a graph, such that X+N(X) = V(G), where N(X) are the neighbours. X should be minimal

[agile magnet]

Does this subset have a specific property?

So that I can actually talk about it?

Ok

I have class now but I'll give a hint

First formulate a decision version of this problem

We know we can solve this decision version in polynomial time right?

Now using this poly time decision version as a black box, come up with an algorithm to solve the optimization problem

[quiet eagle]

"A given X with these properties is minimal?" as that related decision problem

But thanks very much for your help while busy. I'll look into that

[calm chasm]

Anyone see a problem with my proof?

[random vine]

looks good to me

[calm chasm]

Perfect

[ruby verge]

So for context, I've been out of math since my Jr. College (over 4 years ago at this point) and I'm feeling a tiny bit out of my depth understanding basics of discrete math I believe. This is the current problem I hate:

P(x,y): x2y≥4, Q(x,y): x+2y≤4, R(x,y): xy >1.

Find positive integer values for each of x and y such that all of the statements resulting from these open sentences are true but when the values of x and y are interchanged, all of the statements are false.

I'm not entirely sure where to begin or how to approach this problem if I'm being perfectly honest, so any and all insight here would be greatly appreciated for someone trying to re-integrate into a math environment!

[random vine]

What does “x2y >= 4” mean?

[prisma jolt]

I had this question in a book: how many strings of 3 upper case letters and digits are there? I figured it meant 3 letters and 1 digits, which would be 26^3*10, but the book said 46656?

Im not sure hoe that is, i tried asking bing, but it just said i was correct

[ruby verge]

Disregard, I got it!

[stray reef]

do you remember exactly how it was worded

"strings of 3 uppercase letters and digits" is slippery

but judging solely by their answer, they meant strings of 3 characters, in which each character may be an uppercase letter or a digit.

[warm fog]

Hello,

I am reading this paper (https://arxiv.org/pdf/2209.14148.pdf) and feel a little lost. Why are the constraints of this form (highlighted in yellow)?

[prisma jolt]

Yeah thats what they meant

36^3 is the answer given by the book

The question was kinda wierdly written so it took me some time to figure out

[dire stag]

What causes 1 to go to 2, 2 to go to 1, and 3 to go to 3?

[cerulean radish]

That's what the given graph of f states though

[prisma jolt]

Wjat is that tiny v after the set E?

The book doesnt explain it yet and bing is dumb

[cerulean radish]

The definition seems to be in the picture that you have sent

Look at the first line

[weary tiger]

how many ways are there to arrange a 0's, b 1's, and c 2's into a line where no two of the same number are adjacent?

no 00, no 11, no 22

this problem likely does not have a nice closed form since simpler variants I was playing around with don't have one either

but is there any way I can get an answer as a coefficient of a generating function or a summation

alternately what would be the number of ways to fill in a line of length n with 0's, 1's, and 2's according to the adjacency constraints

[weary tiger]

oh nevermind this version is just 3*2^(n-1)

[prisma jolt]

No def of the tiny v

[cerulean radish]

``Let [ E^v(b) = { a \in A \mid (a, b) \in E } ]"

[vital dew]

孤独な豆

[cerulean radish]

Can you guess what this is then?

[prisma jolt]

No?

[cerulean radish]

It's the definition of E^v

If you are thinking that v separately means something, that's not the case

The definition that you are looking for is of E^v

Which, again, is present on that page

[prisma jolt]

Ohh

So Ev is a different set ?

[cerulean radish]

Yeah, given a b from B, E^v of b is the set of all a in A such that (a, b) is in the relation E

[prisma jolt]

Ok, thanks

[weary tiger]

ahh nevermind I think I figured it out

A = x(B+C+1), B= y(A+C+1), C=z(A+B+1), and we seek the coefficient of x^a y^b z^c in [1+A+B+C]

easy enough to solve for A, B, C as three-variable functions of x, y ,z

[twilit sundial]

in case you still needed any help for the general case: PIE is probably the way to go

[pastel coral]

I had this statement on my exam today:
$$x \in (A \cap B) \Leftrightarrow (x \in A) \wedge (x \in B)$$
I said it was false, because if B is empty it is not part of B. Is this correct to say?

[vital dew]

cedric_

[agile magnet]

but if B is empty, is x in A \cap B?

remember, False iff False evaluates to True

[pastel coral]

ohhhh fuck me 🤣

yup alright, thanks

[distant otter]

Hey guys, would appreciate some help with the following problem. Not looking for the solution just some hints as to how to approach problems like this?

[agile magnet]

First thing is give some variable names and notation for these operations

I find that once you can write stuff down, rather than have it float in your head, stuff becomes clearer (duh)

[distant otter]

Some of my thoughts so far:

Only action 1 changes the total number of beads (it removes one bead from the total) so action 1 would need to occur 17 times.
Also, it seems like the difference between red and green always changes by 5. So we start with a difference of 3 between red and green and action 1. will either increase or decrease that difference by 5.
So if we need to reach a difference of zero between red and green, that would be impossible since the difference starts at 3 and can only go to 8 or -2 (or other multiples of 5 beyond it)

[hybrid mortar]

"In how many arrangements of the letters in the word DAUNTLESS do the two S's appear side by side?
"

what is the rule I can use for that question?

[agile magnet]

Hint: think about the two S's side by side as a single letter

Now answer the question, this should be easier

[hybrid mortar]

I'm aware that this makes the options less

because we have already chosen basically 2 letters

now there are only 7 spaces to fill

[agile magnet]

Not even

Even easier

Ok so let's call SS the letter θ

How many ways are there to arrange the letters in the word DAUNTLEθ?

[hybrid mortar]

7!

that's what i'm thinking?

[agile magnet]

Yup!

So you see how that answers the original question?

[hybrid mortar]

Yes, I tried that but it told me that i got the wrong answer

the answer i put in was "5040"

[agile magnet]

Wait I can't count

It's 8!

There are 8 distinct letters not 7 lol

[hybrid mortar]

oh so we count it as one letter

[agile magnet]

How else would we count it lol

[hybrid mortar]

so 8!

thank you so much

[hybrid mortar]

i thought we would neglect it since we already chose it

so it would be like

7C7

as a combination

[agile magnet]

Nowhere did we choose it

We just rewrote it as a new symbol

We never decided where that symbol went

[hybrid mortar]

That makes a lot of sense

i don't understand what's required in this question

i kinda understand now

I tried with them

first set is {2,4,6,8,10}
second is {1, 4,7,10,13}
third starts with {5, 11}

i think 9 should be an example but it says that's incorrect

i've also tried 3

[brave rock]

9 is in fact a correct example, so is 3.

Sometimes automated assessments are just wrong.

[white wagon]

Can some one help me with part d of this problem

🙏

[haughty garden]

inclusion exclusion

[tepid pecan]

can someone explain what is going on in the solution? the question is asking for the ring normal form of A by using expansion rule 4 which is the rule in the 2nd picture but the solution doesnt seem to use the rule directly

[blazing rose]

I’ve had this proof in my discmat course early on but I forgot how to do it

Prove that x^4 = y^2 - 3 has no integer solutions

I tried some case distinction with even and odd but that doesn’t cover all cases

And I believe it was smth with mod congruence

[weary tiger]

how does $10^i$ being relatively prime to 2003 imply that $a_{j-i}$ is divisible by 2003?

[vital dew]

Alex Turner

[stray reef]

d | ab and b coprime to d => d | a

[weary tiger]

can you give some more details?

maybe a concrete example?

for some reason it's not clicking

oh nvm

[plush valley]

hi i have a rly dumb q: how do i find a, b s.t. 69 * a + 80 * b = 75?

this is part of extended euclid algo

[distant otter]

proof by induction?

[calm chasm]

Anyone have any thoughts on a hint here?

[pale monolith]

What are your axioms

[brave rock]

Hint: Use the fact that 0 = c - c.

Follow the example that the proof makes.

[cerulean ore]

Hi, isn't the node from 10 to 4 is a bridge because if that is deleted then it increases number of total components in the graph?

[stray reef]

it would appear so, yes.

who is saying otherwise?

and what is the context of this?

[cerulean ore]

I ran this algorithm https://ide.usaco.guide/Np4uA8My7RJaH_Il8S6 (extended from https://cp-algorithms.com/graph/bridge-searching.html) on this graph. (Vertices are 0 indexed) The only bridge I find is from 2 to 4 ( 1 to 3 when 0 indexed).

[stray reef]

This file is private.

also there are plenty more bridges lol

well, 5->2 and 5->6 specifically

are two that i see immediately

[cerulean ore]

Yeah, I just input the following:
First line is number of vertices, and total edges:
Then all the following lines denote u->v there is a directed edge. 5 5 0 1 1 3 1 2 2 0 4 3

The file must be visible to you now.

[stray reef]

what's the input format

[cerulean ore]

Pardon me, just updated.

[stray reef]

that... doesn't answer my question

[cerulean ore]

That's the input format?

[cerulean ore]

The outlined part is my input (0 indexed)

[stray reef]

ok here is my grievance

i do not know what the numbers in your input are supposed to mean

what number stands for what?

[cerulean ore]

Let me draw a neat graph and also explain the input format.

[cerulean ore]

This is the neat graph, and the input is:

5 edges are below:
from vertex 0 to vertex 1
from vertex 1 to 3
similarly for below:
1 2
2 0
4 3```

[stray reef]

ok so then your input format is "the first line contains the number of nodes followed by the number of edges, and each subsequent line describes an edge."

[cerulean ore]

Yes

[stray reef]

i fail to see why this could not be communicated right away.

but ok

[cerulean ore]

I believe this explains it clearly.

[stray reef]

oh, you edited your message.

sorry. didn't see that.

[cerulean ore]

No problem!

[cerulean ore]

I must be missing something from the above graph that the Tarjan's algorithm might not be applicable on this graph.

So, I found out the reason: https://www.programming-algorithms.net/article/44220/Tarjan's-algorithm
Tarjan's algorithm is a procedure for finding strongly connected components of a directed graph. A strongly connected component is a maximum set of vertices, in which exists at least one oriented path between every two vertices.

[stray reef]

in other words, the problem was insufficient RTFM.

[cerulean ore]

self studying algorithms from online blogs and books, I am supposed to miss things since not every information is present at a place.

[shell jewel]

How is a "pairing" P of a set {k1, ..., kl} formally defined?

for example, what's k_P_1?

[ancient ermine]

Any suggestions on places to find 1st year university level discrete maths problems?

I am struggling to learn this module entirely and think I need more examples / workings etc to understand how to utilise the methods

[cerulean ore]

Any specific topics that you want to practice on?

[ancient ermine]

The following;

Combinations
Arrangements and Permutations
Pigeon hole principle
Proof by induction
Inclusion exclusion
Recursive relations
Generating functions
Graph theory: (What Is a graph?, Eulerian graphs and Planar graphs)

[agile magnet]

does your course have a textbook?

if so which one

that'd be the place to get definitions and problems and such

[frozen mason]

Discrete Mathematics By Biggs Chapters 10, 15, 19 (optional), 25 and 26.1 - 26.4 (optional but good practice for applications of generating functions)

[vapid drift]

hello

any videos explaing these ones

[viral wharf]

graham priest's book goes over very similar problems in the first few chapters. Highly recommend

[vapid drift]

No textbook please only videos

[hasty terrace]

Probably a simple proof but for all positive real numbers a, b, does the following always hold true?
if (x > a + b) then x > a and x > b always

thinking of a counter example for this