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(\genfrac{}{}{0ex}{}{j}{i})(j-i{)}^n$

unlabeled ($n$) → labeled ($k$)

r-Combination with repetition $C(n+k-1,k)$

unlabeled ($n$) → unlabeled ($k$)

partitions

Matrices

Zero-One matrices (each cell is either 0 or 1)

$A=\left(\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$

$B=\left(\begin{array}{ccc}1& 0& 1\\ 1& 0& 0\\ 1& 1& 1\end{array}\right)$

Join Method

Perform logical OR with each corresponding cell.

$A\vee B=\left(\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 1& 1& 1\end{array}\right)$

Meet Method

Perform logical AND with each corresponding cell.

$A\wedge B=\left(\begin{array}{ccc}1& 0& 1\\ 0& 0& 0\\ 0& 0& 1\end{array}\right)$