# 1.8: Combinatorial Structures

- Page ID
- 10123

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)The purpose of this section is to study several combinatorial structures that are of basic importance in probability.

## Permutations

Suppose that \(D\) is a set with \(n \in \N\) elements. A permutation of length \(k \in \{0, 1, \ldots, n\}\) from \(D\) is an ordered sequence of \(k\) distinct elements of \(D\); that is, a sequence of the form \((x_1, x_2, \ldots, x_k)\) where \(x_i \in D\) for each \(i\) and \(x_i \ne x_j\) for \(i \ne j\).

Statistically, a permutation of length \(k\) from \(D\) corresponds to an ordered sample of size \(k\) chosen without replacement from the population \(D\).

The number of permutations of length \(k\) from an \(n\) element set is \[ n^{(k)} = n (n - 1) \cdots (n - k + 1) \]

## Proof

This follows easily from the multiplication principle. There are \(n\) ways to choose the first element, \(n - 1\) ways to choose the second element, and so forth.

By convention, \(n^{(0)} = 1\). Recall that, in general, a product over an empty index set is 1. Note that \(n^{(k)}\) has \(k\) factors, starting at \(n\), and with each subsequent factor one less than the previous factor. Some alternate notations for the number of permutations of size \(k\) from a set of \(n\) objects are \(P(n, k)\), \(P_{n,k}\), and \({_n}P_k\).

The number of permutations of length \(n\) from the \(n\) element set \(D\) (these are called simply permutations of \(D\)) is \[ n! = n^{(n)} = n (n - 1) \cdots (1) \]

The function on \( \N \) given by \( n \mapsto n! \) is the factorial function. The general permutation formula in (2) can be written in terms of factorials:

For \(n \in \N\) and \(k \in \{0, 1, \ldots, n\}\) \[ n^{(k)} = \frac{n!}{(n - k)!} \]

Although this formula is succinct, it's not always a good idea numerically. If \( n \) and \( n - k \) are large, \( n! \) and \( (n - k)! \) are enormous, and division of the first by the second can lead to significant round-off errors.

Note that the basic permutation formula in (2) is defined for every real number \(n\) and nonnegative integer \(k\). This extension is sometimes referred to as the generalized permutation formula. Actually, we will sometimes need an even more general formula of this type (particularly in the sections on Pólya's urn and the beta-Bernoulli process).

For \(a \in \R\), \(s \in \R\), and \(k \in \N\), define \[ a^{(s, k)} = a (a + s) (a + 2 s) \cdots [a + (k - 1) s] \]

- \(a^{(0, k)} = a^k\)
- \(a^{(-1, k)} = a^{(k)}\)
- \(a^{(1, k)} = a (a + 1) \cdots (a + k - 1)\)
- \(1^{(1, k)} = k!\)

The product \(a^{(-1, k)} = a^{(k)}\) (our ordinary permutation formula) is sometimes called the falling power of \(a\) of order \(k\), while \(a^{(1, k)}\) is called the rising power of \(a\) of order \(k\), and is sometimes denoted \( a^{[k]} \). Note that \(a^{(0, k)}\) is the ordinary \(k\)th power of \(a\). In general, note that \(a^{(s, k)}\) has \(k\) factors, starting at \(a\) and with each subsequent factor obtained by adding \(s\) to the previous factor.

## Combinations

Consider again a set \(D\) with \(n \in \N\) elements. A combination of size \(k \in \{0, 1, \ldots, n\}\) from \(D\) is an (unordered) subset of \(k\) distinct elements of \(D\). Thus, a combination of size \(k\) from \(D\) has the form \(\{x_1, x_2, \ldots, x_k\}\), where \(x_i \in D\) for each \(i\) and \(x_i \ne x_j\) for \(i \ne j\).

Statistically, a combination of size \(k\) from \(D\) corresponds to an unordered sample of size \(k\) chosen without replacement from the population \(D\). Note that for each combination of size \(k\) from \(D\), there are \(k!\) distinct orderings of the elements of that combination. Each of these is a permutation of length \(k\) from \(D\). The number of combinations of size \(k\) from an \(n\)-element set is denoted by \(\binom{n}{k}\). Some alternate notations are \(C(n, k)\), \(C_{n,k}\), and \({_n}C_k\).

The number of combinations of size \(k\) from an \(n\) element set is \[ \binom{n}{k} = \frac{n^{(k)}}{k!} = \frac{n!}{k! (n - k)!} \]

## Proof

An algorithm for generating all permutations of size \(k\) from \(D\) is to first select a combination of size \(k\) and then to select an ordering of the elements. From the multiplication principle it follows that \(n^{(k)} = \binom{n}{k} k!\). Hence \( \binom{n}{k} = n^{(k)} / k! = n! / [k! (n - k)!] \).

The number \(\binom{n}{k}\) is called a binomial coefficient. Note that the formula makes sense for any real number \(n\) and nonnegative integer \(k\) since this is true of the generalized permutation formula \(n^{(k)}\). With this extension, \(\binom{n}{k}\) is called the generalized binomial coefficient. Note that if \(n\) and \(k\) are positive integers and \(k \gt n\) then \(\binom{n}{k} = 0\). By convention, we will also define \(\binom{n}{k} = 0\) if \(k \lt 0\). This convention sometimes simplifies formulas.

### Properties of Binomial Coefficients

For some of the identities below, there are two possible proofs. An algebraic proof, of course, should be based on (5). A combinatorial proof is constructed by showing that the left and right sides of the identity are two different ways of counting the same collection.

\(\binom{n}{n} = \binom{n}{0} = 1\).

Algebraically, the last result is trivial. It also makes sense combinatorially: There is only one way to select a subset of \(D\) with \(n\) elements (\(D\) itself), and there is only one way to select a subset of size 0 from \(D\) (the empty set \(\emptyset\)).

If \(n, \, k \in \N\) with \(k \le n\) then \[ \binom{n}{k} = \binom{n}{n - k} \]

## Combinatorial Proof

Note that if we select a subset of size \(k\) from a set of size \(n\), then we leave a subset of size \(n - k\) behind (the complement). Thus \(A \mapsto A^c\) is a one-to-one correspondence between subsets of size \(k\) and subsets of size \(n - k\).

The next result is one of the most famous and most important. It's known as Pascal's rule and is named for Blaise Pascal.

If \(n, \, k \in \N_+\) with \(k \le n\) then \[ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} \]

## Combinatorial Proof

Suppose that we have \(n\) persons, one named Fred, and that we want to select a committee of size \(k\). There are \(\binom{n}{k}\) different committees. On the other hand, there are \(\binom{n - 1}{k - 1}\) committees with Fred as a member, and \(\binom{n - 1}{k}\) committees without Fred as a member. The sum of these two numbers is also the number of committees.

Recall that the Galton board is a triangular array of pegs: the rows are numbered \(n = 0, 1, \ldots\) and the pegs in row \(n\) are numbered \(k = 0, 1, \ldots, n\). If each peg in the Galton board is replaced by the corresponding binomial coefficient, the resulting table of numbers is known as Pascal's triangle, named again for Pascal. By (8), each interior number in Pascal's triangle is the sum of the two numbers directly above it.

The following result is the binomial theorem, and is the reason for the term *binomial coefficient*.

If \(a, \, b \in \R\) and \(n \in \N\) is a positive integer, then \[ (a + b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k} \]

## Combinatorial Proof

Note that to get the term \(a^k b^{n-k}\) in the expansion of \((a + b)^n\), we must select \(a\) from \(k\) of the factors and \(b\) from the remaining \(n - k\) factors. The number of ways to do this is \(\binom{n}{k}\).

If \(j, \, k, \, n \in \N_+\) with \(j \le k \le n\) then \[ k^{(j)} \binom{n}{k} = n^{(j)} \binom{n - j}{k - j} \]

## Combinatorial Proof

Consider two procedures for selecting a committee of size \(k\) from a group of \(n\) persons, with \(j\) distinct members of the committee as officers (chair, vice chair, etc.). For the first procedure, select the committee from the population and then select the member of the committee to be the officers. The number of ways to perform the first step is \(\binom{n}{k}\) and the number of ways to perform the second step is \(k^{(j)}\). So by the multiplication principle, the number of ways to choose the committee is the left side of the equation. For the second procedure, select the officers of the committee from the population and then select \(k - j\) other committee members from the remaining \(n - j\) members of the population. The number of ways to perform the first step is \(n^{(j)}\) and the number of ways to perform the second step is \(\binom{n - j}{k - j}\). So by the multiplication principle, the number of committees is the right side of the equation.

The following result is known as Vandermonde's identity, named for Alexandre-Théophile Vandermonde.

If \(m, \, n, \, k \in \N\) with \(k \le m + n\), then \[ \sum_{j=0}^k \binom{m}{j} \binom{n}{k - j} = \binom{m + n}{k} \]

## Combinatorial Proof

Suppose that a committee of size \(k\) is chosen form a group of \(m + n\) persons, consisting of \(m\) men and \(n\) women. The number of committees with exactly \(j\) men and \(k - j\) women is \(\binom{m}{j} \binom{n}{k - j}\). The sum of this product over \(j\) is the total number of committees, which is \(\binom{m + n}{k}\).

The next result is a general identity for the sum of binomial coefficients.

If \(m, \, n \in \N\) with \( n \le m \) then \[ \sum_{j=n}^m \binom{j}{n} = \binom{m + 1}{n + 1}\]

## Combinatorial Proof

Suppose that we pick a subset of size \(n + 1\) from the set \(\{1, 2, \ldots m + 1\}\). For \(j \in \{n, n + 1, \ldots, m\}\), the number of subsets in which the largest element is \(j + 1\) is \(\binom{j}{n}\). Hence the sum of these numbers over \(j\) is the total number of subsets of size \(n + 1\), which is also \(\binom{m + 1}{n + 1}\).

For an even more general version of the last result, see the section on Order Statistics in the chapter on Finite Sampling Models. The following identity for the sum of the first \(m\) positive integers is a special case of the last result.

If \(m \in \N\) then \[ \sum_{j=1}^m j = \binom{m + 1}{2} = \frac{(m + 1) m}{2} \]

## Proof

Let \(n = 1\) in previous result.

There is a one-to-one correspondence between each pair of the following collections. Hence the number objects in each of these collection is \(\binom{n}{k}\).

- Subsets of size \(k\) from a set of \(n\) elements.
- Bit strings of length \(n\) with exactly \(k\) 1's.
- Paths in the Galton board from \((0, 0)\) to \((n, k)\).

## Proof

Let \(S = \{x_1, x_2, \ldots, x_n\}\) be a set with \(n\) elements. A one-to-one correspondence between the subsets \(A\) of \(S\) with \(k\) elements and the bit strings \(\bs{b} = b_1 b_2 \ldots b_n\) of length \(n\) with \(k\) 1's can be constructed by the rule that \(x_i \in A\) if and only if \(b_i = 1\). In turn, a one-to-one correspondence between the bit strings \(\bs{b}\) in part (b) and the paths in Galton board in part (c) can be constructed by the rule that in row \(i \in \{0, 1, \ldots, n - 1\}\), turn right if \(b_{i+1} = 1\) and turn left if \(b_{i+1} = 0\).

The following identity is known as the alternating sum identity for binomial coefficients. It turns out to be useful in the Irwin-Hall probability distribution. We give the identity in two equivalent forms, one for falling powers and one for ordinary powers.

If \( n \in \N_+ \), \( j \in \{0, 1, \ldots n - 1\} \) then

- \[ \sum_{k=0}^n \binom{n}{k}(-1)^k k^{(j)} = 0\]
- \[ \sum_{k=0}^n \binom{n}{k}(-1)^k k^j = 0\]

## Proof

- We use the identity above and the binomial theorem binomial theorem: \begin{align*} \sum_{k=0}^n (-1)^k k^{(j)} \binom{n}{k} & = \sum_{k=j}^n (-1)^k k^{(j)} \binom{n}{k} = \sum_{k=j}^n (-1)^k n^{(j)} \binom{n - j}{k - j} \\ & = n^{(j)} (-1)^j \sum_{k=j}^n (-1)^{k-j} \binom{n - j}{k - j} = n^{(j)} (-1)^j \sum_{i=0}^{n-j} (-1)^i \binom{n - j}{i} \\ & = n^{(j)} (-1)^j (-1 + 1)^{n - j} = 0. \end{align*} Note that it's the last step where we need \( j \lt n \).
- This follows from (a), since \( k^j \) is a linear combination of \( k^{(i)} \) for \( i \in \{0, 1, \ldots j\} \). That is, there exists \( c_i \in \R \) for \( i \in \{0, 1, \ldots, j\} \) such that \( k^j = \sum_{i=0}^j c_i k^{(i)} \). Hence \[ \sum_{k=0}^n (-1)^k k^j \binom{n}{k} = \sum_{i=0}^j c_i \sum_{k=0}^n (-1)^k k^{(i)} \binom{n}{k} = 0 \]

Our next identity deals with a generalized binomial coefficient.

If \(n, \, k \in \N\) then \[ \binom{-n}{k} = (-1)^k \binom{n + k - 1}{k}\]

## Proof

Note that \begin{align} \binom{-n}{k} & = \frac{(-n)^{(k)}}{k!} = \frac{(-n)(-n - 1) \cdots (-n - k + 1)}{k!}\\ & = (-1)^k \frac{(n + k - 1)(n + k - 2) \cdots (n)}{k!} = (-1)^k \frac{(n + k - 1)^{(k)}}{k!} = (-1)^k \binom{n + k - 1}{k} \end{align}

In particular, note that \(\binom{-1}{k} = (-1)^k\). Our last result in this discussion concerns the binomial operator and its inverse.

The binomial operator takes a sequence of real numbers \(\bs a = (a_0, a_1, a_2, \ldots)\) and returns the sequence of real numbers \(\bs b = (b_0, b_1, b_2, \ldots)\) by means of the formula \[b_n = \sum_{k=0}^n \binom{n}{k} a_k, \quad n \in \N\] The inverse binomial operator recovers the sequence \(\bs a\) from the sequence \(\bs b\) by means of the formula \[a_n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} b_k, \quad n \in \N\]

## Proof

Exponential generating functions can be used for an elegant proof. Exponential generating functions are the combinatorial equivalent of moment generating functions for discrete probability distributions on \(\N\). So let \(G\) and \(H\) denote the exponential generating functions of the sequences \(\bs a\) and \(\bs b\), resepectively. Then \begin{align*} H(x) & = \sum_{n=0}^\infty \frac{b_n}{n!} x^n = \sum_{n=0}^\infty \frac{1}{n!} \sum_{k=0}^n \binom{n}{k} a_k x^n = \sum_{k=0}^\infty \sum_{n=k}^\infty \frac{1}{n!} \frac{n!}{k! (n - k)!} a_k x^n \\ & = \sum_{k=0}^\infty \frac{1}{k!} a_k x^k \sum_{n=k}^\infty \frac{1}{(n-k)!} x^{n-k} = e^x \sum_{k=0}^\infty \frac{1}{k!} a_k x^k = e^x G(x) \end{align*} So it follows that \begin{align*} G(x) & = e^{-x} H(x) = \sum_{k=0}^\infty \frac{1}{k!} b_k x^k \sum_{n=k}^\infty \frac{1}{(n - k)!} (-1)^{n-k} x^{n-k} \\ & = \sum_{k=0}^\infty \sum_{n=k}^\infty \frac{1}{n!} \frac{n!}{k! (n - k)!} (-1)^{n-k} b_k x^n = \sum_{n=0}^\infty \frac{1}{n!} \sum_{k = 0}^n \binom{n}{k} (-1)^{n-k} b_k x^n \end{align*} But by definition, \[G(x) = \sum_{n=0}^\infty \frac{a_n}{n!} x^n\] and so the inverse formula follows.

## Samples

The experiment of drawing a sample from a population is basic and important. There are two essential attributes of samples: whether or not order is important, and whether or not a sampled object is replaced in the population before the next draw. Suppose now that the population \(D\) contains \(n\) objects and we are interested in drawing a sample of \(k\) objects. Let's review what we know so far:

- If order is important and sampled objects are replaced, then the samples are just elements of the product set \(D^k\). Hence, the number of samples is \(n^k\).
- If order is important and sample objects are not replaced, then the samples are just permutations of size \(k\) chosen from \(D\). Hence the number of samples is \(n^{(k)}\).
- If order is not important and sample objects are not replaced, then the samples are just combinations of size \(k\) chosen from \(D\). Hence the number of samples is \(\binom{n}{k}\).

Thus, we have one case left to consider.

### Unordered Samples With Replacement

An unordered sample chosen *with* replacement from \(D\) is called a multiset. A multiset is like an ordinary set except that elements may be repeated.

There is a one-to-one correspondence between each pair of the following collections:

- Mulitsets of size \(k\) from a population \(D\) of \(n\) elements.
- Bit strings of length \(n + k - 1\) with exactly \(k\) 1s.
- Nonnegative integer solutions \((x_1, x_2, \ldots, x_n)\) of the equation \(x_1 + x_2 + \cdots + x_n = k\).

Each of these collections has \( \binom{n + k - 1}{k} \) members.

## Proof

Suppose that \(D = \{d_1, d_2, \ldots, d_n\}\). Consider a multiset of size \(k\). Since order does not matter, we can list all of the occurrences of \(d_1\) (if any) first, then the occurrences of \(d_2\) (if any), and so forth, until we at last list the occurrences of \(d_n\) (if any). If we know we are using this data structure, we don't actually have to list the actual elements, we can simply use 1 as a placeholder with 0 as a seperator. In the resulting bit string, 1 occurs \(k\) times and 0 occurs \(n - 1\) times. Conversely, any such bit string uniquely defines a multiset of size \(k\). Next, given a multiset of size \( k \) from \( D \), let \(x_i\) denote the number of times that \( d_i \) occurs, for \( i \in \{1, 2, \ldots, n\} \). Then \((x_1, x_2, \ldots, x_n)\) satisfies the conditions in (c). Conversely, any solution to the equation in (c) uniquely defines a multiset of size \( k \) from \( D \). We already know how to count the collection in (b): the number of bit strings of length \( n + k - 1 \) with 1 occurring \( k \) times is \( \binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1} \).

### Summary of Sampling Formulas

The following table summarizes the formulas for the number of samples of size \(k\) chosen from a population of \(n\) elements, based on the criteria of order and replacement.

Number of Samples | With order | Without |
---|---|---|

With replacement | \(n^k\) | \(\binom{n + k - 1}{k}\) |

Without | \(n^{(k)}\) | \(\binom{n}{k}\) |

## Multinomial Coefficients

### Partitions of a Set

Recall that the binomial coefficient \(\binom{n}{j}\) is the number of subsets of size \(j\) from a set \(S\) of \(n\) elements. Note also that when we select a subset \(A\) of size \(j\) from \(S\), we effectively *partition* \(S\) into two disjoint subsets of sizes \(j\) and \(n - j\), namely \(A\) and \(A^c\). A natural generalization is to partition \(S\) into a union of \(k\) distinct, pairwise disjoint subsets \((A_1, A_2, \ldots, A_k)\) where \(\#(A_i) = n_i\) for each \(i \in \{1, 2, \ldots, k\}\). Of course we must have \(n_1 + n_2 + \cdots + n_k = n\).

The number of ways to partition a set of \( n \) elements into a sequence of \( k \) sets of sizes \( (n_1, n_2, \ldots, n_k) \) is \[ \binom{n}{n_1} \binom{n - n_1}{n_2} \cdots \binom{n - n_1 - \cdots - n_{k-1}}{n_k} = \frac{n!}{n_1! n_2! \cdots n_k!} \]

## Proof

The left side follows from the multiplication rule. There are \(\binom{n}{n_1}\) ways to select the first set in the partition, \(\binom{n - n_1}{n_2}\) ways to select the second set in the partition, and so forth. The right side follows by writing the binomial coefficients on the left in terms of factorials and simplifying.

The number in (18) is called a multinomial coefficient and is denoted by \[ \binom{n}{n_1, n_2, \cdots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!} \]

If \(n, \, k \in \N\) with \(k \le n\) then \[ \binom{n}{k, n - k} = \binom{n}{k}\]

## Combinatorial Proof

As noted before, if we select a subset of size \(k\) from an \(n\) element set, then we partition the set into two subsets of sizes \(k\) and \(n - k\).

### Sequences

Consider now the set \(T = \{1, 2, \ldots, k\}^n\). Elements of this set are sequences of length \(n\) in which each coordinate is one of \(k\) values. Thus, these sequences generalize the bit strings of length \(n\). Again, let \((n_1, n_2, \ldots, n_k)\) be a sequence of nonnegative integers with \(\sum_{i=1}^k n_i = n\).

There is a one-to-one correspondence between the following collections:

- Partitions of \(S\) into pairwise disjoint subsets \((A_1, A_2, \ldots, A_k)\) where \(\#(A_j) = n_j\) for each \(j \in \{1, 2, \ldots, k\}\).
- Sequences in \(\{1, 2, \ldots, k\}^n\) in which \(j\) occurs \(n_j\) times for each \(j \in \{1, 2, \ldots, k\}\).

## Proof

Suppose that \(S = \{s_1, s_2, \ldots, s_n\}\). A one-to-one correspondence between a partition \((A_1, A_2, \ldots, A_k)\) of the type in (a) and a sequence \(\bs{x} = (x_1, x_2, \ldots, x_n)\) of the type in (b) can be constructed by the rule that \(s_i \in A_j\) if and only if \(x_i = j\).

It follows that the number of elements in both of these collections is \[ \binom{n}{n_1, n_2, \cdots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!} \]

### Permutations with Indistinguishable Objects

Suppose now that we have \(n\) object of \(k\) different types, with \(n_i\) elements of type \(i\) for each \(i \in \{1, 2, \ldots, k\}\). Moreover, objects of a given type are considered identical. There is a one-to-one correspondence between the following collections:

- Sequences in \(\{1, 2, \ldots, k\}^n\) in which \(j\) occurs \(n_j\) times for each \(j \in \{1, 2, \ldots, k\}\).
- Distinguishable permutations of the \(n\) objects.

## Proof

A one-to-one correspondence between a sequence \(\bs{x} = (x_1, x_2, \ldots, x_n)\) of the type in (a) and a permutation of the \(n\) objects can be constructed by the rule that we put an object of type \(j\) in position \(i\) if and only if \(x_i = j\).

Once again, it follows that the number of elements in both collections is \[ \binom{n}{n_1, n_2, \cdots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!} \]

### The Multinomial Theorem

The following result is the multinomial theorem which is the reason for the name of the coefficients.

If \(x_1, \, x_2, \ldots, x_k \in \R\) and \(n \in \N\) then \[ (x_1 + x_2 + \cdots + x_k)^n = \sum \binom{n}{n_1, n_2, \cdots, n_k} x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k} \] The sum is over sequences of nonnegative integers \((n_1, n_2, \ldots, n_k)\) with \( n_1 + n_2 + \cdots + n_k = n\). There are \(\binom{n + k - 1}{n}\) terms in this sum.

## Combinatorial Proof

Note that to get \(x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}\) in the expansion of \((x_1 + x_2 + \cdots x_k)^n\), we must chose \(x_i\) in \(n_i\) of the factors, for each \(i\). The number of ways to do this is the multinomial coefficient \(\binom{n}{n_1, n_2, \ldots, n_k}\). The number of terms in the sum follows from the formula above.

## Computational Exercises

### Arrangements

In a race with 10 horses, the first, second, and third place finishers are noted. How many outcomes are there?

## Answer

\(720\)

Eight persons, consisting of four male-female couples, are to be seated in a row of eight chairs. How many seating arrangements are there in each of the following cases:

- There are no other restrictions.
- The men must sit together and the women must sit together.
- The men must sit together.
- Each couple must sit together.

## Answer

- \(40 \, 320\)
- \(1152\)
- \(2880\)
- \(384\)

Suppose that \(n\) people are to be seated at a round table. How many seating arrangements are there? The mathematical significance of a round table is that there is no dedicated *first* chair.

## Answer

\((n - 1)!\). Seat one, distinguished person arbitrarily. Every seating arrangement can then be specified by giving the position of a person (say clockwise) relative to the distinguished person.

Twelve books, consisting of 5 math books, 4 science books, and 3 history books are arranged on a bookshelf. Find the number of arrangements in each of the following cases:

- There are no restrictions.
- The books of each type must be together.
- The math books must be together.

## Answer

- \(479 \, 001 \, 600\)
- \(103 \, 680\)
- \(4 \, 838 \, 400\)

Find the number of distinct arrangements of the letters in each of the following words:

- statistics
- probability
- mississippi
- tennessee
- alabama

## Answer

- \(50 \, 400\)
- \(9\,979\,200\)
- \(34\,650\)
- \(3780\)
- \(210\)

A child has 12 blocks; 5 are red, 4 are green, and 3 are blue. In how many ways can the blocks be arranged in a line if blocks of a given color are considered identical?

## Answer

\(27\,720\)

### Code Words

A license tag consists of 2 capital letters and 5 digits. Find the number of tags in each of the following cases:

- There are no other restrictions
- The letters and digits are all different.

## Answer

- \(67\,600\,000\)
- \(19\,656\,000\)

### Committees

A club has 20 members; 12 are women and 8 are men. A committee of 6 members is to be chosen. Find the number of different committees in each of the following cases:

- There are no other restrictions.
- The committee must have 4 women and 2 men.
- The committee must have at least 2 women and at least 2 men.

## Answer

- \(38\,760\)
- \(13\,860\)
- \(30\,800\)

Suppose that a club with 20 members plans to form 3 distinct committees with 6, 5, and 4 members, respectively. In how many ways can this be done.

## Answer

\(9\,777\,287\,520\). Note that the members *not* on a committee also form one of the sets in the partition.

### Cards

A standard card deck can be modeled by the Cartesian product set \[ D = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, j, q, k\} \times \{\clubsuit, \diamondsuit, \heartsuit, \spadesuit\} \] where the first coordinate encodes the denomination or kind (ace, 2-10, jack, queen, king) and where the second coordinate encodes the suit (clubs, diamonds, hearts, spades). Sometimes we represent a card as a *string* rather than an ordered pair (for example \(q \heartsuit\)).

A poker hand (in draw poker) consists of 5 cards dealt without replacement and without regard to order from a deck of 52 cards. Find the number of poker hands in each of the following cases:

- There are no restrictions.
- The hand is a full house (3 cards of one kind and 2 of another kind).
- The hand has 4 of a kind.
- The cards are all in the same suit (so the hand is a flush or a straight flush).

## Answer

- \(2\,598\,960\)
- \(3744\)
- \(624\)
- \(5148\)

The game of poker is studied in detail in the chapter on Games of Chance.

A bridge hand consists of 13 cards dealt without replacement and without regard to order from a deck of 52 cards. Find the number of bridge hands in each of the following cases:

- There are no restrictions.
- The hand has exactly 4 spades.
- The hand has exactly 4 spades and 3 hearts.
- The hand has exactly 4 spades, 3 hearts, and 2 diamonds.

## Answer

- \(635\,013\,559\,600\)
- \(151\,519\,319\,380\)
- \(47\,079\,732\,700\)
- \(11\,404\,407\,300\)

A hand of cards that has no cards in a particular suit is said to be void in that suit. Use the inclusion-exclusion formula to find each of the following:

- The number of poker hands that are void in at least one suit.
- The number of bridge hands that are void in at least one suit.

## Answer

- \(1\,913\,496\)
- \(32\,427\,298\,180\)

A bridge hand that has no honor cards (cards of denomination 10, jack, queen, king, or ace) is said to be a Yarborough, in honor of the Second Earl of Yarborough. Find the number of Yarboroughs.

## Answer

\(347\,373\,600\)

A bridge deal consists of dealing 13 cards (a bridge hand) to each of 4 distinct players (generically referred to as north, south, east, and west) from a standard deck of 52 cards. Find the number of bridge deals.

## Answer

\( 53\,644\,737\,765\,488\,792\,839\,237\,440\,000 \approx 5.36 \times 10^{28} \)

This staggering number is about the same order of magnitude as the number of atoms in your body, and is one of the reasons that bridge is a rich and interesting game.

Find the number of permutations of the cards in a standard deck.

## Answer

\(52! \approx 8.0658 \times 10^{67}\)

This number is even more staggering. Indeed if you perform the experiment of dealing all 52 cards from a well-shuffled deck, you may well generate a pattern of cards that has never been generated before, thereby ensuring your immortality. Actually, this experiment shows that, in a sense, rare events can be very common. By the way, Persi Diaconis has shown that it takes about seven standard riffle shuffles to thoroughly randomize a deck of cards.

### Dice and Coins

Suppose that 5 distinct, standard dice are rolled and the sequence of scores recorded.

- Find the number of sequences.
- Find the number of sequences with the scores all different.

## Answer

- \(7776\)
- \(720\)

Suppose that 5 identical, standard dice are rolled. How many outcomes are there?

## Answer

\(252\)

A coin is tossed 10 times and the outcome is recorded as a bit string (where 1 denotes heads and 0 tails).

- Find the number of outcomes.
- Find the number of outcomes with exactly 4 heads.
- Find the number of outcomes with at least 8 heads.

## Answer

- \( 1024 \)
- \(210\)
- \(56\)

### Polynomial Coefficients

Find the coefficient of \(x^3 \, y^4\) in \((2 \, x - 4 \, y)^7\).

## Answer

\(71\,680\)

Find the coefficient of \(x^5\) in \((2 + 3 \, x)^8\).

## Answer

\(108\,864\)

Find the coefficient of \(x^3 \, y^7 \, z^5\) in \((x + y + z)^{15}\).

## Answer

\(360\,360\)

### The Galton Board

In the Galton board game,

- Move the ball from \((0, 0)\) to \((10, 6)\) along a path of your choice. Note the corresponding bit string and subset.
- Generate the bit string \(0011101001\). Note the corresponding subset and path.
- Generate the subset \(\{1, 4, 5, 7, 8, 10\}\). Note the corresponding bit string and path.
- Generate all paths from \((0, 0)\) to \((5, 3)\). How many paths are there?

## Answer

- 10

Generate Pascal's triangle up to \(n = 10\).

### Samples

A shipment contains 12 good and 8 defective items. A sample of 5 items is selected. Find the number of samples that contain exactly 3 good items.

## Answer

\(6160\)

In the \((n, k)\) lottery, \(k\) numbers are chosen without replacement from the set of integers from 1 to \(n\) (where \( n, \, k \in \N_+ \) and \(k \lt n\)). Order does not matter.

- Find the number of outcomes in the general \((n, k)\) lottery.
- Explicitly compute the number of outcomes in the \((44, 6)\) lottery (a common format).

## Answer

- \(\binom{n}{k}\)
- \(7\,059\,052\)

For more on this topic, see the section on Lotteries in the chapter on Games of Chance.

Explicitly compute each formula in the sampling table above when \(n = 10\) and \(k = 4\).

## Answer

- Ordered samples with replacement: \(10\,000\)
- Ordered samples without replacement: \(5040\)
- Unordered samples with replacement: \(715\)
- Unordered samples without replacement: \(210\)

### Greetings

Suppose there are \(n\) people who shake hands with each other. How many handshakes are there?

## Answer

\(\binom{n}{2}\). Note that a handshake can be thought of as a subset of size 2 from the set of \( n \) people.

There are \( m \) men and \( n \) women. The men shake hands with each other; the women hug each other; and each man bows to each woman.

- How many handshakes are there?
- How many hugs are there?
- How many bows are there?
- How many greetings are there?

## Answer

- \( \binom{m}{2} \)
- \( \binom{n}{2} \)
- \( m n \)
- \( \binom{m}{2} + \binom{n}{2} + m n = \binom{m + n}{2} \)

### Integer Solutions

Find the number of integer solutions of \(x_1 + x_2 + x_3 = 10\) in each of the following cases:

- \(x_i \ge 0\) for each \(i\).
- \(x_i \gt 0\) for each \(i\).

## Answer

- \(66\)
- \(36\)

### Generalized Coefficients

Compute each of the following:

- \((-5)^{(3)}\)
- \(\left(\frac{1}{2}\right)^{(4)}\)
- \(\left(-\frac{1}{3}\right)^{(5)}\)

## Answer

- \(-210\)
- \(-\frac{15}{16}\)
- \(-\frac{3640}{243}\)

Compute each of the following:

- \(\binom{1/2}{3}\)
- \(\binom{-5}{4}\)
- \(\binom{-1/3}{5}\)

## Answer

- \(\frac{1}{16}\)
- \(70\)
- \(-\frac{91}{729}\)

### Birthdays

Suppose that \(n\) persons are selected and their birthdays noted. (Ignore leap years, so that a year has 365 days.)

- Find the number of outcomes.
- Find the number of outcomes with distinct birthdays.

## Answer

- \(365^n\).
- \(365^{(n)}\).

### Chess

Note that the squares of a chessboard are distinct, and in fact are often identified with the Cartesian product set \[ \{a, b, c, d, e, f, g, h\} \times \{1, 2, 3, 4, 5, 6, 7, 8\} \]

Find the number of ways of placing 8 rooks on a chessboard so that no rook can capture another in each of the following cases.

- The rooks are distinguishable.
- The rooks are indistinguishable.

## Answer

- \(1\,625\,702\,400\)
- \(40\,320\)

### Gifts

Suppose that 20 identical candies are distributed to 4 children. Find the number of distributions in each of the following cases:

- There are no restrictions.
- Each child must get at least one candy.

## Answer

- \(1771\)
- \(969\)

In the song The Twelve Days of Christmas, find the number of gifts given to the singer by her true love. (Note that the singer starts afresh with gifts each day, so that for example, the true love gets a new partridge in a pear tree each of the 12 days.)

## Answer

\(364\)

### Teams

Suppose that 10 kids are divided into two teams of 5 each for a game of basketball. In how many ways can this be done in each of the following cases:

- The teams are distinguishable (for example, one team is labeled
Alabama

and the other team is labeledAuburn

). - The teams are not distinguishable.

## Answer

- \(252\)
- \(126\)