MATH 302 Lecture 22

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

Multinomial coefficients

Answers the question: How many ways are there to put Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} labeled objects into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} objects into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} boxes

labeled (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ) → labeled (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} ): multinomial coefficients: ${\frac {n!}{n_{1}!\,n_{2}!\,\dots \,n_{k}!}}$
labeled (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ) → unlabeled (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} ): ~~Stirling numbers:~~ Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ) → labeled (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} ): r-Combination with repetition Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(n+k-1,k)}
unlabeled (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ) → unlabeled ( $k$ ): partitions

Matrices

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = \begin{pmatrix}1&0&1\\0&1&0\\0&0&1\end{pmatrix}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B = \begin{pmatrix}1&0&1\\1&0&0\\1&1&1\end{pmatrix}}

Join Method

Perform logical OR with each corresponding cell.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \vee B = \begin{pmatrix}1&0&1\\1&1&0\\1&1&1\end{pmatrix}}

Meet Method

Perform logical AND with each corresponding cell.

$A\wedge B={\begin{pmatrix}1&0&1\\0&0&0\\0&0&1\end{pmatrix}}$