L04.7 Partitions

MIT RES.6-012 Introduction to Probability, Spring 2018
Instructor: John Tsitsiklis

License: Creative Commons BY-NC-SA

[ikechukwuuchendu]

Excellent explanation and alternative approach to deriving the multinomial coefficient.

[DeadPool-jtci]

funny thing there's a movie about an indian genious that cracked partitions, it's called " The man who knew infinity"

[offthepathworks]

I've been having the same Q since combinations, why ordered, this was never explicitly explained - ?

[abir]

The proof was not intuitive enough for me ... let me provide a more intuitive proof . Let's say for a set of n distinguishable objects, we want to simply select n1 items and put it in a subset S1, then n2 items from the remaining to S2 and so on till we have exhausted the parent set.

For the sake of simplicity, let's say we selected thrice from the parent set and the parent set got exhausted, i.e r = 3

That is to say that n = n1+n2+n3

# select n1 items from n items : nCn1
# select n2 items from n-n1 items : n-n1Cn2
# select n3 items from n-n1-n2 items : n-n1-n2Cn3

By applying product rule we get the total ways : nCn1 * n-n1Cn2 * n-n1-n2Cn3

Simplifying the above

[ n! / n1! * (n-n1!) ] * [ (n-n1)!/n2! * (n-n1-n2)! ] * [(n-n1-n2)! / n3! * (n-n1-n2-n3)!]
n! / n1! * n2! * n3! * (n-n1-n2-n3)!

recall that n = n1+n2+n3 . So n-n1-n2-n3 = 0 and 0! = 1

So the number of ways is n! / n1! * n2! * n3!

[yiningding]

There is a mistake at the end of this video, the way he writes m1, m2, m3 is wrong because it does not have to follow the specific order.