MATH 302 Lecture 22

« previous | Wednesday, November 16, 2011 | next »

Multinomial coefficients

Answers the question: How many ways are there to put $n$ labeled objects into $k$ labeled containers?

There are $a_{1}$ objects in container 1. Thre are $a_{2}$ objects in container 2. (etc, etc.)

This is such that $\sum _{i}a_{i}=n\,\!$ .

{\frac {n!}{a_{1}!a_{2}!a_{3}!\dots a_{k}!}}

Example

How many ways are there to deal 5 cards to 4 players (from a deck of 52 cards)?

Each of the 4 players acts like a container that will receive 5 objects (cards). There is another "container": the remaining cards in the deck, which will have 32 cards:

${\frac {52!}{5!5!5!5!32!}}$

Partititons

Answers the questions: How many ways are there to break $n$ into $k$ parts?

No formula to do this, but here's an example:

How many ways are there to put 6 identical balls into 4 identical boxes (unlabeled → unlabeled)

6
5	1
4	2
4	1	1
3	3
3	2	1
3	1	1	1
2	2	2
2	2	1	1

Notice that in all cases, it is the same as writing the sum of 4 integers that equal 6 in decreasing order.

Cases for Objects to Boxes

Distributing $n$ objects into $k$ boxes

labeled ( $n$ ) → labeled ( $k$ ): multinomial coefficients: ${\frac {n!}{n_{1}!\,n_{2}!\,\dots \,n_{k}!}}$
~~labeled ( $n$ ) → unlabeled ( $k$ )~~: ~~Stirling numbers:~~ $\sum _{j=0}^{k}S(n,j)=\sum _{j=1}^{k}{\frac {1}{j!}}\sum _{i=0}^{j-1}(-1)^{i}{\binom {j}{i}}(j-i)^{n}$
unlabeled ( $n$ ) → labeled ( $k$ ): r-Combination with repetition $C(n+k-1,k)$
unlabeled ( $n$ ) → unlabeled ( $k$ ): partitions