The purpose of this section is to study several combinatorial structures that are of basic importance in probability.
Suppose that \(D\) is a set with \(n\) elements where \(n \in \N\). 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\).
Suppose that \(n \in \N\) and \(k \in \{0, 1, \ldots, n\}\). The number of permutations of length \(k\) from an \(n\) element set is \[ n^{(k)} = n (n - 1) \cdots (n - k + 1) \]
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\).
For \(n \in \N\), 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 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 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 for in Pólya's urn model and the beta-Bernoulli process).
For \(a, \, s \in \R\) and \(k \in \N\), define \[ a^{(s, k)} = a (a + s) (a + 2 s) \cdots [a + (k - 1) s] \]
For \(a \in \R\) and \(k \in \N\), 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 for \( a, \, s \in \R \) and \(k \in \N\), note that \(a^{(s, k)}\) has \(k\) factors, starting at \(a\) and with each subsequent factor obtained by adding \(s\) to the previous factor.
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\).
For \(n, \, k \in \N\) with \(k \le n\), 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)!} \] The number \(\binom{n}{k}\) is called a binomial coefficient.
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 and it follows that \(n^{(k)} = \binom{n}{k} k!\). Hence \( \binom{n}{k} = n^{(k)} / k! = n! / [k! (n - k)!] \).
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. Note also that the first equation in makes sense for any real number \(n\) and nonnegative integer \(k\) since this is true of the generalized permutation formula \(n^{(k)}\).
For \(n \in \R\) and \(k \in \N\), the generalized binomial coefficient is \[ \binom{n}{k} = \frac{n^{(k)}}{k!} = \frac{n (n - 1) \cdots (n - k + 1)}{k!}\]
Here is a special identity for binomial coefficients that will be useful below.
For \(k \in \N\), \[ \binom{-1 / 2}{k} = (-1)^k \binom{2 k}{k} \]
For some of the identities below, there are two possible proofs. An algebraic proof, of course, should be based on combination formula in . 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. We use combinatorial proofs whenever possible.
For \(n \in \N\), \(\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} \]
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} \]
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 Pascal's rule , 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} \]
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}\).
The next result is the generalized binomial theorem, which appropriately enough, uses generalized binomial coefficients.
If \(m \in \R\) and \(x \in (-1, 1)\), \[(1 + x)^m = \sum_{k = 0}^\infty \binom{m}{k} x^k\]
Rather than a combinatorial argument we have to resort to an analytic argument. Define the function \(f\) by \(f(x) = (1 + x)^m\). If \(m \ge 0\) then \(f\) is defined for all \(x \in \R\). If \(m \lt 0\) then \(f\) is defined for \(x \in (-1, \infty)\). The sum on the right is the ordinary Taylor series for \(f\) expanded about 0, since \(f^{(k)}(0) = m^{(k)}\). The ratio test shows that the series has radius of convergence at least 1.
Note that if \(m\) in theorem is a positive integer then the terms in the sum for \(k \in \{m + 1, m + 2, \ldots \}\) are 0, and so the generalized binomial theorem reduces to the ordinary binomial theorem in . Depending on \(m\) the sum in may converge in a larger interval about 0.
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} \]
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 members 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} \]
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}\]
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}\).
The following identity for the sum of the first \(m\) positive integers is a special case of .
If \(m \in \N\) then \[ \sum_{j=1}^m j = \binom{m + 1}{2} = \frac{(m + 1) m}{2} \]
The following result generalizes and is particularly important in the study of order statistics in finite sampling models.
Suppose that \(i, \, n, \, m \in \N_+\) with \(i \le n \le m\). Then \[\sum_{k = i}^{m - n + i} \binom{k - 1}{i - 1} \binom{m - k}{n - i} = \binom{m}{n}\]
Suppose that \(k\) is a positive integer with \(i \le k \le m - n + i\). The following procedure generates a subset of \(\{1, 2, \ldots, m\}\) of size \(n\) with \(k\) as the \(i\)th largest element.
By the multiplication principle, the number of ways selection the subset is \[\binom{k - 1}{i - 1} \cdot 1 \cdot \binom{m - k}{n - i}\]. Summing over \(k \in \{i, i + 1, \ldots, i + m - n\}\) gives the number of subsets of \(\{1, 2, \ldots, m\}\) size \(n\). But of course, this is just \(\binom{m}{n}\).
The following result is important in the study of random walks.
If \(n \in \N\) then \[\sum_{k = 0}^n \binom{2 k}{k} \binom{2 n - 2 k}{n - k} = 2^{2 n}\]
We sketch two proofs.
Suppose that \(n, \, k \in \N\) with \(k \le n\). 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}\).
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
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}\]
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. It is related to the theory of Möbius inversion, named for August Ferdinand Möbius.
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\]
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.
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, where \(n, \, k \in \N\). Let's review what we know so far:
Sampling formulas:
Thus, we have one case left to consider, namely unordered samples with replacement. Such a sample is called a multiset, and is like an ordinary set except that elements may be repeated.
For \(n, \, k \in \N\), there is a one-to-one correspondence between each pair of the following collections:
Each of these collections has \( \binom{n + k - 1}{k} \) members.
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} \).
The following table gives a complete summary of the formulas for the number of samples of size \(k \in \N\) chosen from a population of \(n \in \N\) elements, based on the criteria of order and replacement.
| Replacement | Order | With | Without |
|---|---|---|
| With | \(n^k\) | \(\binom{n + k - 1}{k}\) |
| Without | \(n^{(k)}\) | \(\binom{n}{k}\) |
Recall that for \(n, \, j \in \N\) with \(j \le n\), 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\}\).
Suppose that \(n, \, k \in \N_+\) and that \(n_i \in \N\) for \(i \in \{1, 2, \ldots, k\}\) with \(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!} \] This number is called a multinomial coefficient and is denoted by \[ \binom{n}{n_1 \, n_2 \, \cdots \, n_k} \]
The left side follows from the multiplication principle. 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 multinomial coefficient also makes sense (and has the value 1) if \(n = 0\) and \(n_i = 0\) for \(i \in \{1, 2, \ldots, k\}\). The multinomial coefficient generalizes the binomial coefficient.
If \(n, \, k \in \N\) with \(k \le n\) then \[ \binom{n}{k \; n - k} = \binom{n}{k}\]
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\).
Consider now the set \(T = \{1, 2, \ldots, k\}^n\) where \(n, \, k \in \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\).
Suppose again that \(n, \, k \in \N_+\) and that \(n_i \in \N\) for \(i \in \{1, 2, \ldots, k\}\) with \(n_1 + n_2 + \cdots + n_k = n\). There is a one-to-one correspondence between the following collections:
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!} \]
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\).
Suppose again that \(n, \, k \in \N_+\) and that \(n_i \in \N\) for \(i \in \{1, 2, \ldots, k\}\) with \(n_1 + n_2 + \cdots + n_k = n\).
Suppose 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:
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!} \]
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\).
The following result is the multinomial theorem which is the reason for the name of the coefficients.
Suppose that \(k \in \N_+\), \(n \in \N\) and \(x_1, \, x_2, \ldots, x_k \in \R\). 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.
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 .
In a race with 10 horses, the first, second, and third place finishers are noted. How many outcomes are there?
\(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:
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.
\((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:
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?
\(27\,720\)
A license tag consists of 2 capital letters and 5 digits. Find the number of tags in each of the following cases:
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.
\(9\,777\,287\,520\). Note that the members not on a committee also form one of the sets in the partition.Details:
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:
The game of poker is studied in more 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 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.
\(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.
\( 53\,644\,737\,765\,488\,792\,839\,237\,440\,000 \approx 5.36 \times 10^{28} \)
The staggering number in 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.
\(52! \approx 8.0658 \times 10^{67}\)
The number in 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, 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?
\(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 coefficient of \(x^3 \, y^4\) in \((2 \, x - 4 \, y)^7\).
\(71\,680\)
Find the coefficient of \(x^5\) in \((2 + 3 \, x)^8\).
\(108\,864\)
Find the coefficient of \(x^3 \, y^7 \, z^5\) in \((x + y + z)^{15}\).
\(360\,360\)
Open the Galton board app and set \(n = 20\) rows. Click on the left and right buttons to generate a path in the Galton board. Note the corresponding bit string and subset. Click on a few pegs to see the corresponding binomial coefficients.
Generate Pascal's triangle up to \(n = 10\).
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.
\(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.
For more on this topic, see the section on lotteries.
Explicitly compute each formula in the sampling table in when \(n = 10\) and \(k = 4\).
Suppose there are \(n\) people who shake hands with each other, where \(n \in \N_+\). How many handshakes are there?
\(\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, where \(m, \, n \in \N_+\). The men shake hands with each other; the women hug each other; and each man bows to each woman.
Find the number of integer solutions of \(x_1 + x_2 + x_3 = 10\) in each of the following cases:
Compute each of the following:
Compute each of the following:
Suppose that \(n\) persons are selected and their birthdays noted, where \(n \in \N_+\). (Ignore leap years, so that a year has 365 days.)
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.
Suppose that 20 identical candies are distributed to 4 children. Find the number of distributions in each of the following cases:
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.)
\(364\)
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:
Alabamaand the other team is labeled
Auburn).