The purpose of this section is to study several combinatorial structures that are of basic importance in probability.
Consider a set \(D\) with \(n\) elements. A permutation of length \(k\) 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_n)\) where \(x_i \in D\) for each \(i\) and \(x_i \ne x_j\) for \(i \ne j\). Of course, \(k\) cannot be larger than \(n\). 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) \]Use the multiplication principle.
By convention, \(n^{(0)} = 1\). Recall that, in general, a product over an empty index set is 1.
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) \]For \(n \in \N\) and \(k \in \{0, 1, \ldots, n\}\)
\[ n^{(k)} = \frac{n!}{(n - k)!} \]Note that the basic permutation formula 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 section on Pólya's urn and the beta-Bernoulli process). For \(a \in \R\), \(s \in \R\), and \(j \in \N\), define
\[ a^{(s,\,j)} = a \, (a + s) \, (a + 2 \, s) \, \cdots \, [a + (j - 1) \, s] \]Note that
The product \(a^{(-1,\,j)} = a^{(j)}\) is sometimes called the falling power of \(a\) of order \(j\), while \(a^{(1,\,j)}\) is called the rising power of \(a\) of order \(j\). Note that \(a^{(0,\,j)}\) is the ordinary \(j\)th power of \(a\).
Consider again a set \(D\) with \(n\) elements. A combination of size \(k\) 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_n\}\), where \(x_i \in D\) for each \(i\) and \(x_i \ne x_j\) for \(i \ne j\). Again, \(k\) cannot be larger than \(n\). 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}\) or \(C(n, k)\).
The number of combinations of size \(k\) from an \(n\) element set is
\[ \binom{n}{k} = \frac{n^{(k)}}{k!} \]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!\).
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.
If \(n\) and \(k\) are nonnegative integers and \(k \le n\) then
\[ \binom{n}{k} = \frac{n!}{k! \, (n - k)!} \]For some of the identities in the exercises below, there are two possible proofs. An algebraic proof, of course, should be based on the first combination formula or the second combination formula. 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\).
If \(n, \; k \in \N\) with \(k \le n\) then
\[ \binom{n}{k} = \binom{n}{n - k} \]For the combinatorial argument, note that if you select a subset of size \(k\) from a set of size \(n\), then you leave a subset of size \(n - k\) behind.
If \(n, \; k \in \N_+\) with \(k \le n\) then
\[ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} \]For the combinatorial argument, fix an element of the set. Count the number of subsets of size \(k\) that contain the designated element and the number of subsets of size \(k\) that do not contain the designated element.
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 for Blaise Pascal. By the Exercise 9, each interior number in Pascal's triangle is the sum of the two numbers directly above it.
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} \]For the combinatorial argument, 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.
If \(n, \; k \in \N_+\) with \(k \le n\) then
\[ k \binom{n}{k} = n \binom{n - 1}{k - 1} \]For the combinatorial argument, consider two procedures for selecting a committee of size \(k\) from a group of \(n\) persons, with one distinguished member of the committee as chair. For the first procedure, select the committee from the population and then select a member of the committee to act as chair. For the second procedure, select the chair of the committee from the population and then select \(k - 1\) other committee members from the remaining \(n - 1\) members of the population.
If \(m, \; n, \; k \in \N\) with \(k \le m + n\), then
\[ \sum_{j=0}^k \binom{m}{j} \binom{n}{k - j} = \binom{n + m}{k} \]For the combinatorial argument, suppose that a committee of size \(k\) is chosen form a group of \(m + n\) persons, consisting of \(n\) women and \(m\) men. Count the number of committees with \(j\) men and \(k - j\) women, and then sum over \(j\).
If \(m, \; n \in \N\) with \( n \le m \) then
\[ \sum_{j=n}^m \binom{j}{n} = \binom{m + 1}{n + 1}\]For the combinatorial argument, 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\}\), count the number of subsets in which the largest element is \(j + 1\) and sum over \(j\).
For an even more general version of the identity in Exercise 13, see the section on Order Statistics in the chapter on Finite Sampling Models. The identity in Exercise 9 is a special case of the identity in the Exercise 13, as is the following identity for the sum of the first \(m\) positive integers:
If \(m \in \N\) then
\[ \sum_{j=1}^m j = \binom{m + 1}{2} = \frac{(m + 1) m}{2} \]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}\).
If \(n, \; k \in \N\) then
\[ \binom{-n}{k} = (-1)^k \binom{n + k - 1}{k}\]In particular, note that \(\binom{-1}{k} = (-1)^k\).
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:
Thus, we have one case left to consider.
There is a one-to-one correspondence between each pair of the following collections:
Each of the collections in Exercise 17 has \(\binom{n + k - 1}{k}\) elements.
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.
| With Order | Without Order | |
|---|---|---|
| With Replacement | \(n^k\) | \(\binom{n + k - 1}{k}\) |
| Without Replacement | \(n^{(k)}\) | \(\binom{n}{k}\) |
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 such partitions 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!} \]Use the multiplication rule.
This number is called a multinomial coefficient and is denoted by
\[ \binom{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}\]For the combinatorial argument, note that 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\).
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\) in the last section. 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:
It follows that the number of sequences in the second part of the Exercise 21 is
\[ \binom{n}{n_1, \; n_2, \; \cdots, \; n_k} \]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:
It follows that the number of permutations in the second part of the Exercise 22 is
\[ \binom{n}{n_1, \; n_2, \; \cdots, \; n_k} \]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_{n_1 + n_2 + \cdots + n_k = n} \binom{n}{n_1, \; n_2, \; \cdots, \; n_k} x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k} \]For the combinatorial argument, 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 sum in the multinomial theorem is over sequences of nonegative integers \((n_1, n_2, \ldots, n_k)\) with \( n_1 + n_2 + \cdots + n_k = n\). There are \(\binom{n + k - 1}{k - 1}\) terms in this sum.
In a race with 10 horses, the first, second, and third place finishers are noted. How many outcomes are there?
A license tag consists of 2 letters and 5 digits. Find the number of tags with the letters and digits are all different.
Eight persons, consisting of four married couples, are to be seated in a row of eight chairs. How many seating arrangements are there in each of the following cases:
Suppose that \(n\) people are to be seated at a round table. Show that there are \((n - 1)!\) distinct seating arrangements. The mathematical significance of a round table is that there is no dedicated first chair.
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:
Find the number of distinct arrangements of the letters in each of the following words:
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?
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:
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.
The members not on a committee also form one of the sets in the partition.Hint:
A standard card deck can be modeled by the 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 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:
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:
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:
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.
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. The number of bridge deals is
\[ 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.
The number of permutations of the cards in a standard deck is \(52! \approx 8.0658 \times 10^{67}\)
This number is enormous. Indeed if you perform the experiment of dealing all 52 cards from a well-shuffled deck, you may will 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.
Suppose that 5 distinct, standard dice are rolled and the sequence of scores recorded.
Suppose that 5 identical, standard dice are rolled. How many outcomes are there?
Find the coefficient of \(x^3 \, y^4\) in \((2 \, x - 4 \, y)^7\).
Find the coefficient of \(x^5\) in \((2 + 3 \, x)^8\).
Find the coefficient of \(x^3 \, y^7 \, z^5\) in \((x + y + z)^{15}\).
Generate Pascal's triangle up to \(n = 10\).
Suppose that in a group of \(n\) people, each person shakes hands with every other person. Show that there are \(\binom{n}{2}\) different handshakes.
In the \((n, k)\) lottery, \(k\) numbers are chosen without replacement from the set of integers from 1 to \(n\) (where \(k \lt n\) of course). Order does not matter.
For more on this topic, see the section on Lotteries in the chapter on Games of Chance.
In the Galton board game,
A fair coin is tossed 10 times and the outcome is recorded as a bit string (where 1 denotes heads and 0 tails).
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.
Suppose that 20 identical candies are distributed to 4 children. Find the number of distributions are there in each of the following cases:
Find the number of integer solutions of \(x_1 + x_2 + x_3 = 10\) in each of the following cases:
Explicitly compute each formula in the sampling table above when \(n = 10\) and \(k = 4\).
Compute each of the following:
Compute each of the following:
Suppose that \(n\) persons are selected and their birthdays noted.
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. Note that the squares of a chessboard are distinct, and in fact are often identified with the product set
\[ \{a, b, c, d, e, f, g, h\} \times \{1, 2, 3, 4, 5, 6, 7, 8\} \]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.)