Let us begin with an example.

Example 1. A jar contains 11 marbles. In how many ways can they be placed in four boxes, with 3 marbles in the first box, 4 marbles in the second box, 2 marbles in the third box, and the 2 remaining marbles in the fourth box?

Solution. The total number of outcomes is $$\begin{pmatrix}11\\3\end{pmatrix}\cdot \begin{pmatrix}8\\4\end{pmatrix}\cdot \begin{pmatrix}4\\2\end{pmatrix}\cdot \begin{pmatrix}2\\2\end{pmatrix}=\frac{11!}{3!8!}\cdot\frac{8!}{4!4!}\cdot\frac{4!}{2!2!}\cdot\frac{2!}{2!0!}=\frac{11!}{3!4!2!2!}=69,300$$

This example can be generalized to the following question. A set of $n$ distinct items is to be divided into $r$ distinct groups of respective sizes $n_1, n_2, \cdots, n_r$ such that $\sum_{i=1}^r n_i=n$. How many different divisions are possible? There are $\begin{pmatrix}n\\n_1\end{pmatrix}$ possible choices for the first group, there are $\begin{pmatrix}n-n_1\\n_2\end{pmatrix}$ possible choices for the second group, there are $\begin{pmatrix}n-n_1-n_2\\n_3\end{pmatrix}$ possible choices for the third group, …, there are $\begin{pmatrix}n-n_1-n_2-\cdots-n_{r-1}\\n_r\end{pmatrix}$ possible choices for the $r$-th group. Therefore the total number of coutcomes is \begin{align*}\begin{pmatrix}n\\n_1\end{pmatrix}\begin{pmatrix}n-n_1\\n_2\end{pmatrix}\begin{pmatrix}n-n_1-n_2\\n_3\end{pmatrix}\cdots\begin{pmatrix}n-n_1-n_2-\cdots -n_{r-1}\\n_r\end{pmatrix}\\=\frac{n!}{(n-n_1)!n_1!}\frac{(n-n_1)!}{(n-n_1-n_2)!n_2!}\cdots\frac{(n-n_1-n_2\cdots-n_{r-1})!}{0!n_r!}\\=\frac{n!}{n_1!n_2!\cdots n_r!}\end{align*}

The number of divisions of $n$ distinct items into $r$ distinct groups of respective sizes $n_1,n_2,\cdots,n_r$ is denoted by $\begin{pmatrix}n\\n_1,n_2,\cdots,n_r\end{pmatrix}$. That is, \begin{equation}\label{eq:multcoeff}\begin{pmatrix}n\\n_1,n_2,\cdots,n_r\end{pmatrix}=\frac{n!}{n_1!n_2!\cdots n_r!}\end{equation} where $n=n_1+n_2+\cdots+n_r$.

Example 2. A police department in a small city consists of 10 officers. If the department policy is to have 5 of the officers patrolling the streets, 2 of the officers working full time at the station, and 3 of the officers on reserve at the station, how many different divisions of the 10 offices into the 3 groups are possible?

Solution. $\frac{10!}{5!2!3!}=2,520$.

Example 3. Ten children are to be divided into an A team and a B team of 5 each. The A team and a B team of 5 each. The A team will play in one league and the B team in another. How many different divisions are possible?

Solution. $\frac{10!}{5!5!}=252$.

Example 4. In order to play a game of basketball, 10 children at a playground divide themselves into two teams of 5 each. How many different divisions are possible?

Solution. Compare Example 4 with Example 3. In this example, the order of the two teams is irrelevant. Hence, the answer is $\frac{\frac{10!}{5!5!}}{2!}=126$.

Let us consider more about the cases like Example 4. In Example 1, it was implicitly indicated that the four boxes are distinguishable as they are specified as the first box, the second box, and so on so forth. For example, if we assume that the marbles were labeled 1 through 11, the following two would be two different outcomes: \begin{align*}\{1,2,3\},\{4,5,6,7\},\{8,9\},\{10,11\}\\\{1,2,3\},\{4,5,6,7\},\{10,11\},\{8,9\}\end{align*} because the marbles placed in the third and the fourth boxed are swapped in the second row. But what if these boxes were indistinguishable? Then the two outcomes would’ve been regarded as the same.

Example. A jar contains 11 marbles. In how many ways can they be placed in 4 unmarked boxes, with 1 box containing 3 marbles, 1 box containing 4 marbles, and 2 boxes containing 2 marbles each?

Solution. We first choose the marbles for each box as in the case boxes are ordered just like Example 1: $$\begin{pmatrix}11\\3\end{pmatrix}\cdot\begin{pmatrix}8\\4\end{pmatrix}\cdot\begin{pmatrix}4\\2\end{pmatrix}\cdot\begin{pmatrix}2\\2\end{pmatrix}=\frac{11!}{3!4!2!2!}$$ Now, any boxes that have the same number of marbles can be swapped with each other. So we will have to divide the above total by $1!1!2!$ to get the final result: $$\frac{\frac{11!}{3!4!2!2!}}{1!1!2!}=34,650$$

The formula in \eqref{eq:multcoeff} is called multinomial coefficient as it is related to the Multinomial Theorem.

Theorem. \begin{equation}\label{eq:multinomial}(x_1+x_2+\cdots+x_r)^n=\sum_{(n_1,\cdots,n_r)\\n_1+n_2+\cdots+n_r=n}\begin{pmatrix}n\\n_1,n_2,\cdots,n_r\end{pmatrix}x_1^{n_1}x_2^{n_2}\cdots x_r^{n_r}\end{equation}

Example. Expand $(x_1+x_2+x_3)^2$.

Solution. There are 6 partitions of 2: \begin{align*}2&=2+0+0=0+2+0=0+0+2\\&=1+1+0=1+0+1=0+1+1\end{align*} Thus, \begin{align*}(x_1+x_2+x_3)^2&=\begin{pmatrix}2\\2,0,0\end{pmatrix}x_1^2x_2^0x_3^0+\begin{pmatrix}2\\0,2,0\end{pmatrix}x_1^0x_2^2x_3^0+\begin{pmatrix}2\\0,0,2\end{pmatrix}x_1^0x_2^0x_3^2\\&+\begin{pmatrix}2\\1,1,0\end{pmatrix}x_1^1x_2^1x_3^0+\begin{pmatrix}2\\1,0,1\end{pmatrix}x_1^1x_2^0x_3^1+\begin{pmatrix}2\\0,1,1\end{pmatrix}x_1^0x_2^1x_3^1\\&=x^1_2+x_2^2+x_3^2+2x_1x_2+2x_1x_3+2x_2x_3\end{align*}

By the basic principle of counting, there are $r^n$ possible outcomes when $n$ distinguishable balls are to be distributed into $r$ distinguishable urns. What is the balls are indistinguishable? Let us consider a vector $(x_1,x_2,\cdots,x_r)$, where $x_i$ represents the number of balls that are distributed into the $i$-th urn. Then the problem boils down to counting the number of vectors $(x_1,x_2,\cdots,x_r)$ such that the $x_i$’s are nonnegative, integer-valued and $x_1+x_2+\cdots+x_r=n$. First let us consider the number of such vectors with the $x_i$’s being all positive integer-valued. Imagine that we lined up $n$ balls and divide them into $r$ nonempty groups. For $n=8$ and $r=3$, the following is an example of the divisions: ooo|ooo|oo. There are 7 spaces between 8 balls so the number of all possible 3 such divisions is $\begin{pmatrix}7\\2\end{pmatrix}$. By a similar arugument, we obtain:

Proposition 1. There are $\begin{pmatrix}n-1\\r-1\end{pmatrix}$ distinct vectors $(x_1,\cdots,x_r)$ such that the $x_i$’s are all positive, integer-valued and $x_1+\cdots+x_r=n$.

Now suppose that the $x_i$’s are nonnegative (positive or zero). Let $y_i=x_i+1$. Then $y_i>0$ and $y_1+y_2+\cdots+y_r=n+r$. It follows from the above proposition that:

Proposition 2. There are $\begin{pmatrix}n+r-1\\r-1\end{pmatrix}$ distinct vectors $(x_1,\cdots,x_r)$ such that the $x_i$’s are nonnegative, integer-valued and $x_1+\cdots+x_r=n$.

Example. How many distinct solutions of $x_1+x_2=3$, where $x_1$ and $x_2$ are nonnegative and integer-valued, are possible?

Solution. $\begin{pmatrix}3+2-1\\2-1\end{pmatrix}=4$. In fact, they are $(0,3)$, $(1,2)$, $(2,1)$, $(3,0)$.

Example. An investor has \$20,000 to invest among 4 possible investments. Each investment must be in units of a thousand dollars. If the total $20,000 is to be invested, how many different investment strategies are possible? What if not all the money need to be invested?

Solution. Let $x_i$ denote the number of thousands in dollars invested in ivestment number $i$. Then $$x_1+x_2+x_3+x_4=20,\ x_i\geq 0$$ and there are $\begin{pmatrix}20+4-1\\4-1\end{pmatrix}=1,771$ possible investment strategies. If not all the money need to be invested, let $x_5$ denote the amount kept in reserve. Now, a strategy is a vector $(x_1,x_2,x_3,x_4,x_5)$ such that the $x_i$’s are nonnegative, integer-valued and $x_1+x_2+x_3+x_4+x_5=20$. Hence, there are $\begin{pmatrix}20+5-1\\5-1\end{pmatrix}=10,626$ possible strategies.

Remark. Using proposition 2, we can also answer how many terms there are in the multinomial expansion of $(x_1+x_2+\cdots+x_r)^n$. In the multinomial expansion formula \eqref{eq:multinomial}, $n_1+n_2+\cdots+n_r=n$. Hence there are $\begin{pmatrix}n+r-1\\r-1\end{pmatrix}$ terms.

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998

[3] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019