Content check — Probability (Grinstead and Snell), Chapter 3: Combinatorics

Every problem in the chapter beside the book’s answer, a chapter at a time as you scroll.

Chapter 3: Combinatorics

31 problems · 0 figures

Exercise 3.1.1 §3.1 source ↗

Four people are to be arranged in a row to have their picture taken. In how many ways can this be done?

Answer

$24$

Exercise 3.1.3 §3.1 source ↗

In a digital computer, a bit is one of the integers {0,1}, and a word is any string of 32 bits. How many different words are possible?

Answer

$2^{32}$

Exercise 3.1.5 §3.1 source ↗

There are three different routes connecting city A to city B. How many ways can a round trip be made from A to B and back? How many ways if it is desired to take a different route on the way back?

Answer

$9$ ⁠, $6$ ⁠.

Exercise 3.1.7 §3.1 source ↗

Five people get on an elevator that stops at five floors. Assuming that each has an equal probability of going to any one floor, find the probability that they all get off at different floors.

Answer

$\frac{5!}{5^{5}}$ ⁠.

Exercise 3.1.11 §3.1 source ↗

There are $n$ applicants for the director of computing. The applicants are interviewed independently by each member of the three-person search committee and ranked from 1 to $n$ ⁠. A candidate will be hired if he or she is ranked first by at least two of the three interviewers. Find the probability that a candidate will be accepted if the members of the committee really have no ability at all to judge the candidates and just rank the candidates randomly. In particular, compare this probability for the case of three candidates and the case of ten candidates.

Answer

$\frac{3 n - 2}{n^{3}}$ ⁠, $\frac{7}{27}$ ⁠, $\frac{28}{1000}$ ⁠.

Exercise 3.1.13 §3.1 source ↗

A certain state has license plates showing three numbers and three letters. How many different license plates are possible

(a) if the numbers must come before the letters?

(b) if there is no restriction on where the letters and numbers appear?

Answer

(a) $26^{3} \times 10^{3}$

(b) $(\frac{6}{3}) \times 26^{3} \times 10^{3}$

Exercise 3.1.15 §3.1 source ↗

A computing center has 3 processors that receive $n$ jobs, with the jobs assigned to the processors purely at random so that all of the $3^{n}$ possible assignments are equally likely. Find the probability that exactly one processor has no jobs.

Answer

$\frac{(\frac{3}{1}) \times (2^{n} - 2)}{3^{n}}$ ⁠.

Exercise 3.1.17 §3.1 source ↗

Find a formula for the probability that among a set of $n$ people, at least two have their birthdays in the same month of the year (assuming the months are equally likely for birthdays).

Answer

$1 - \frac{12 \cdot 11 \cdot \dots \cdot (12 - n + 1)}{12^{n}}$ ⁠, if $n \leq 12$ ⁠, and $1$ ⁠, if $n > 12$ ⁠.

Exercise 3.1.21 §3.1 source ↗

Modify the program AllPermutations to count the number of permutations of $n$ objects that have exactly $j$ fixed points for $j = 0$ ⁠, 1, 2, …, $n$ ⁠. Run your program for $n = 2$ to 6. Make a conjecture for the relation between the number that have 0 fixed points and the number that have exactly 1 fixed point. A proof of the correct conjecture can be found in Wilf. (H. S. Wilf, “A Bijection in the Theory of Derangements," Mathematics Magazine, vol. 57, no. 1 (1984), pp. 37–40. )

Answer

They are the same.

Exercise 3.1.23 §3.1 source ↗

Barbara Smith is interviewing candidates to be her secretary. As she interviews the candidates, she can determine the relative rank of the candidates but not the true rank. Thus, if there are six candidates and their true rank is 6, 1, 4, 2, 3, 5, (where 1 is best) then after she had interviewed the first three candidates she would rank them 3, 1, 2. As she interviews each candidate, she must either accept or reject the candidate. If she does not accept the candidate after the interview, the candidate is lost to her. She wants to decide on a strategy for deciding when to stop and accept a candidate that will maximize the probability of getting the best candidate. Assume that there are $n$ candidates and they arrive in a random rank order.

(a) What is the probability that Barbara gets the best candidate if she interviews all of the candidates? What is it if she chooses the first candidate?

(b) Assume that Barbara decides to interview the first half of the candidates and then continue interviewing until getting a candidate better than any candidate seen so far. Show that she has a better than 25 percent chance of ending up with the best candidate.

Answer

(a) $\frac{1}{n}$ ⁠, $\frac{1}{n}$

(b) She will get the best candidate if the second best candidate is in the first half and the best candidate is in the secon half. The probability that this happens is greater than $1 / 4$ ⁠.

Exercise 3.2.1 §3.2 source ↗

Compute the following:

(a) $(\frac{6}{3})$

(b) $b (5, .2,4)$

(d) $(\frac{26}{26})$

(e) $b (4, .2,3)$

(f) $(\frac{6}{2})$

(g) $(\frac{10}{9})$

(h) $b (8, .3, 5)$

Answer

(a) $20$

(b) $.0064$

(d) $1$

(e) $.0256$

(f) $15$

(g) $10$

Exercise 3.2.3 §3.2 source ↗

How many seven-element subsets are there in a set of nine elements?

Answer

$(\frac{9}{7}) = 36$

Exercise 3.2.5 §3.2 source ↗

Use the program BinomialProbabilities to find the probability that, in 100 tosses of a fair coin, the number of heads that turns up lies between 35 and 65, between 40 and 60, and between 45 and 55.

Answer

$.998$ ⁠, $.965$ ⁠, $.729$

Exercise 3.2.7 §3.2 source ↗

Show that $b (n, p, j) = \frac{p}{q} (\frac{n - j + 1}{j}) b (n, p, j - 1),$ for $j \geq 1$ ⁠. Use this fact to determine the value or values of $j$ which give $b (n, p, j)$ its greatest value. Hint: Consider the successive ratios as $j$ increases.

Answer

$\begin{matrix} \frac{b (n, p, j)}{b (n, p, j - 1)} & = \frac{(\frac{n}{j}) p^{j} q^{n - j}}{(\frac{n}{j - 1}) p^{j - 1} q^{n - j + 1}} = \frac{n!}{j! (n - j)!} \frac{(n - j + 1)! (j - 1)!}{n!} \frac{p}{q} \\ = \frac{(n - j + 1)}{j} \frac{p}{q} . \end{matrix}$ But $\frac{(n - j + 1)}{j} \frac{p}{q} \geq 1$ if and only if $j \leq p (n + 1)$ ⁠, and so $j = [p (n + 1)]$ gives $b (n, p, j)$ its largest value. If $p (n + 1)$ is an integer there will be two possible values of $j$ ⁠, namely $j = p (n + 1)$ and $j = p (n + 1) - 1$ ⁠.

Exercise 3.2.9 §3.2 source ↗

Find integers $n$ and $r$ such that the following equation is true: $(\frac{13}{5}) + 2 (\frac{13}{6}) + (\frac{13}{7}) = (\frac{n}{r}) .$

Answer

$n = 15$ ⁠, $r = 7$

Exercise 3.2.11 §3.2 source ↗

A restaurant offers apple and blueberry pies and stocks an equal number of each kind of pie. Each day ten customers request pie. They choose, with equal probabilities, one of the two kinds of pie. How many pieces of each kind of pie should the owner provide so that the probability is about .95 that each customer gets the pie of his or her own choice?

Answer

Eight pieces of each kind of pie.

Exercise 3.2.13 §3.2 source ↗

If a set has $2 n$ elements, show that it has more subsets with $n$ elements than with any other number of elements.

Answer

The number of subsets of $2 n$ objects of size $j$ is $(\frac{2 n}{j})$ ⁠. $\frac{(\frac{2 n}{i})}{(\frac{2 n}{i - 1})} = \frac{2 n - i + 1}{i} \geq 1 \Rightarrow i \leq n + \frac{1}{2} .$ Thus $i = n$ makes $(\frac{2 n}{i})$ maximum.

Exercise 3.2.15 §3.2 source ↗

A baseball player, Smith, has a batting average of $.300$ and in a typical game comes to bat three times. Assume that Smith’s hits in a game can be considered to be a Bernoulli trials process with probability .3 for success. Find the probability that Smith gets 0, 1, 2, and 3 hits.

Answer

$.3443$ ⁠, $.441$ ⁠, $.181$ ⁠, $.027$ ⁠.

Exercise 3.2.17 §3.2 source ↗

Using the technique of Exercise 16, show that the number of ways that one can put $n$ different objects into three boxes with $a$ in the first, $b$ in the second, and $c$ in the third is $n! / (a! b! c!)$ ⁠.

Exercise 3.2.16 in the book ↗

The Siwash University football team plays eight games in a season, winning three, losing three, and ending two in a tie. Show that the number of ways that this can happen is $(\frac{8}{3}) (\frac{5}{3}) = \frac{8!}{3! 3! 2!} .$

Answer

There are $(\frac{n}{a})$ ways of putting $a$ different objects into the 1st box, and then $(\frac{n - a}{b})$ ways of putting $b$ different objects into the 2nd and then one way to put the remaining objects into the 3rd box. Thus the total number of ways is $(\frac{n}{a}) (\frac{n - a}{b}) = \frac{n!}{a! b! (n - a - b)!} .$

Exercise 3.2.19 §3.2 source ↗

A gin hand consists of 10 cards from a deck of 52 cards. Find the probability that a gin hand has

(a) all 10 cards of the same suit.

(b) exactly 4 cards in one suit and 3 in two other suits.

Answer

(a) $\frac{(\frac{4}{1}) (\frac{13}{10})}{(\frac{52}{10})} =$ $7.23 \times 10^{- 8}$ ⁠.

(b) $\frac{(\frac{4}{1}) (\frac{3}{2}) (\frac{13}{4}) (\frac{13}{3}) (\frac{13}{3})}{(\frac{52}{10})} =$ $.044$ ⁠.

Exercise 3.2.21 §3.2 source ↗

A lady wishes to color her fingernails on one hand using at most two of the colors red, yellow, and blue. How many ways can she do this?

Answer

$3 (2^{5}) - 3 = 93$ (We subtract 3 because the three pure colors are each counted twice.)

Exercise 3.2.23 §3.2 source ↗

Using the method for the hint in Exercise 22, show that $r$ indistinguishable objects can be put in $n$ boxes in $(\frac{n + r - 1}{n - 1}) = (\frac{n + r - 1}{r})$ different ways.

Exercise 3.2.22 in the book ↗

How many ways can six indistinguishable letters be put in three mail boxes? Hint: One representation of this is given by a sequence $|$ ⁠LL⁠ $|$ ⁠L⁠ $|$ ⁠LLL⁠ $|$ where the $|$ ⁠’s represent the partitions for the boxes and the L’s the letters. Any possible way can be so described. Note that we need two bars at the ends and the remaining two bars and the six L’s can be put in any order.

Answer

To make the boxes, you need $n + 1$ bars, 2 on the ends and $n - 1$ for the divisions. The $n - 1$ bars and the $r$ objects occupy $n - 1 + r$ places. You can choose any $n - 1$ of these $n - 1 + r$ places for the bars and use the remaining $r$ places for the objects. Thus the number of ways this can be done is $(\frac{n - 1 + r}{n - 1}) = (\frac{n - 1 + r}{r}) .$

Exercise 3.2.25 §3.2 source ↗

An elevator takes on six passengers and stops at ten floors. We can assign two different equiprobable measures for the ways that the passengers are discharged: (a) we consider the passengers to be distinguishable or (b) we consider them to be indistinguishable (see Exercise 23 for this case). For each case, calculate the probability that all the passengers get off at different floors.

Exercise 3.2.23 in the book ↗

Using the method for the hint in Exercise 22, show that $r$ indistinguishable objects can be put in $n$ boxes in $(\frac{n + r - 1}{n - 1}) = (\frac{n + r - 1}{r})$ different ways.

Exercise 3.2.22 in the book ↗

Answer

(a) $6! (\frac{10}{6}) / 10^{6} \approx .1512$

(b) $(\frac{10}{6}) / (\frac{15}{6}) \approx .042$

Exercise 3.2.27 §3.2 source ↗

John claims that he has extrasensory powers and can tell which of two symbols is on a card turned face down (see Example 3.11). To test his ability he is asked to do this for a sequence of trials. Let the null hypothesis be that he is just guessing, so that the probability is 1/2 of his getting it right each time, and let the alternative hypothesis be that he can name the symbol correctly more than half the time. Devise a test with the property that the probability of a type 1 error is less than .05 and the probability of a type 2 error is less than .05 if John can name the symbol correctly 75 percent of the time.

Example 3.11 in the book ↗

Suppose that ordinary aspirin has been found effective against headaches 60 percent of the time, and that a drug company claims that its new aspirin with a special headache additive is more effective. We can test this claim as follows: we call their claim the alternate hypothesis, and its negation, that the additive has no appreciable effect, the null hypothesis. Thus the null hypothesis is that $p = .6$ ⁠, and the alternate hypothesis is that $p > .6$ ⁠, where $p$ is the probability that the new aspirin is effective.

We give the aspirin to $n$ people to take when they have a headache. We want to find a number $m$ ⁠, called the critical value for our experiment, such that we reject the null hypothesis if at least $m$ people are cured, and otherwise we accept it. How should we determine this critical value?

First note that we can make two kinds of errors. The first, often called a type 1 error in statistics, is to reject the null hypothesis when in fact it is true. The second, called a type 2 error, is to accept the null hypothesis when it is false. To determine the probability of both these types of errors we introduce a function $α (p)$ ⁠, defined to be the probability that we reject the null hypothesis, where this probability is calculated under the assumption that the null hypothesis is true. In the present case, we have $α (p) = \sum_{m \leq k \leq n} b (n, p, k) .$

Note that $α (.6)$ is the probability of a type 1 error, since this is the probability of a high number of successes for an ineffective additive. So for a given $n$ we want to choose $m$ so as to make $α (.6)$ quite small, to reduce the likelihood of a type 1 error. But as $m$ increases above the most probable value $n p = .6 n$ ⁠, $α (.6)$ ⁠, being the upper tail of a binomial distribution, approaches 0. Thus increasing $m$ makes a type 1 error less likely.

Now suppose that the additive really is effective, so that $p$ is appreciably greater than .6; say $p = .8$ ⁠. (This alternative value of $p$ is chosen arbitrarily; the following calculations depend on this choice.) Then choosing $m$ well below $n p = .8 n$ will increase $α (.8)$ ⁠, since now $α (.8)$ is all but the lower tail of a binomial distribution. Indeed, if we put $β (.8) = 1 - α (.8)$ ⁠, then $β (.8)$ gives us the probability of a type 2 error, and so decreasing $m$ makes a type 2 error less likely.

The manufacturer would like to guard against a type 2 error, since if such an error is made, then the test does not show that the new drug is better, when in fact it is. If the alternative value of $p$ is chosen closer to the value of $p$ given in the null hypothesis (in this case $p = .6$ ⁠), then for a given test population, the value of $β$ will increase. So, if the manufacturer’s statistician chooses an alternative value for $p$ which is close to the value in the null hypothesis, then it will be an expensive proposition (i.e., the test population will have to be large) to reject the null hypothesis with a small value of $β$ ⁠.

What we hope to do then, for a given test population $n$ ⁠, is to choose a value of $m$ ⁠, if possible, which makes both these probabilities small. If we make a type 1 error we end up buying a lot of essentially ordinary aspirin at an inflated price; a type 2 error means we miss a bargain on a superior medication. Let us say that we want our critical number $m$ to make each of these undesirable cases less than 5 percent probable.

We write a program PowerCurve to plot, for $n = 100$ and selected values of $m$ ⁠, the function $α (p)$ ⁠, for $p$ ranging from .4 to 1. The result is shown in Figure 3.7. We include in our graph a box (in dotted lines) from .6 to .8, with bottom and top at heights .05 and .95. Then a value for $m$ satisfies our requirements if and only if the graph of $α$ enters the box from the bottom, and leaves from the top (why?—which is the type 1 and which is the type 2 criterion?). As $m$ increases, the graph of $α$ moves to the right. A few experiments have shown us that $m = 69$ is the smallest value for $m$ that thwarts a type 1 error, while $m = 73$ is the largest which thwarts a type 2. So we may choose our critical value between 69 and 73. If we’re more intent on avoiding a type 1 error we favor 73, and similarly we favor 69 if we regard a type 2 error as worse. Of course, the drug company may not be happy with having as much as a 5 percent chance of an error. They might insist on having a 1 percent chance of an error. For this we would have to increase the number $n$ of trials (see Exercise 28).

Figure 3.7: The power curve. — Figure 3.7 in the book ↗

Exercise 3.2.28 in the book ↗

In Example 3.11 assume the alternative hypothesis is that $p = .8$ and that it is desired to have the probability of each type of error less than .01. Use the program PowerCurve to determine values of $n$ and $m$ that will achieve this. Choose $n$ as small as possible.

Answer

Ask John to make 42 trials and if he gets 27 or more correct accept his claim. Then the probability of a type I error is $\sum_{k \geq 27} b (42, .5, k) = .044,$ and the probability of a type II error is $1 - \sum_{k \geq 27} b (42, .75, k) = .042.$

Exercise 3.2.29 §3.2 source ↗

A drug is assumed to be effective with an unknown probability $p$ ⁠. To estimate $p$ the drug is given to $n$ patients. It is found to be effective for $m$ patients. The method of maximum likelihood for estimating $p$ states that we should choose the value for $p$ that gives the highest probability of getting what we got on the experiment. Assuming that the experiment can be considered as a Bernoulli trials process with probability $p$ for success, show that the maximum likelihood estimate for $p$ is the proportion $m / n$ of successes.

Answer

$b (n, p, m) = (\frac{n}{m}) p^{m} {(1 - p)}^{n - m}$ ⁠. Taking the derivative with respect to $p$ and setting this equal to 0 we obtain $m (1 - p) = p (n - m)$ and so $p = m / n$ ⁠.

Exercise 3.2.31 §3.2 source ↗

Each of the four engines on an airplane functions correctly on a given flight with probability .99, and the engines function independently of each other. Assume that the plane can make a safe landing if at least two of its engines are functioning correctly. What is the probability that the engines will allow for a safe landing?

Answer

$.999996$ ⁠.

Exercise *3.2.33 §3.2 source ↗

$2 n$ balls are chosen at random from a total of $2 n$ red balls and $2 n$ blue balls. Find a combinatorial expression for the probability that the chosen balls are equally divided in color. Use Stirling’s formula to estimate this probability. Using BinomialProbabilities, compare the exact value with Stirling’s approximation for $n = 20$ ⁠.

Answer

By Stirling’s formula, $\frac{{(\frac{2 n}{n})}^{2}}{(\frac{4 n}{2 n})} = \frac{{(2 n!)}^{2} {(2 n!)}^{2}}{n!^{4} (4 n)!} \sim \frac{{(\sqrt{4 π n} {(2 n)}^{2 n} e^{- 2 n})}^{4}}{{(\sqrt{2 π n} (n^{n}) e^{- n})}^{4} \sqrt{2 π} (4 n) {(4 n)}^{4 n} e^{- 4 n}} = \sqrt{\frac{2}{π n}} .$

Exercise *3.2.35 §3.2 source ↗

Prove the following binomial identity $(\frac{2 n}{n}) = \sum_{j = 0}^{n} {(\frac{n}{j})}^{2} .$ Hint: Consider an urn with $n$ red balls and $n$ blue balls inside. Show that each side of the equation equals the number of ways to choose $n$ balls from the urn.

Answer

Consider an urn with $n$ red balls and $n$ blue balls inside. The left side of the identity $(\frac{2 n}{n}) = \sum_{j = 0}^{n} {(\frac{n}{j})}^{2} = \sum_{j = 0}^{n} (\frac{n}{j}) (\frac{n}{n - j})$ counts the number of ways to choose $n$ balls out of the $2 n$ balls in the urn. The right hand counts the same thing but breaks the counting into the sum of the cases where there are exactly $j$ red balls and $n - j$ blue balls.

Exercise 3.2.38 §3.2 source ↗

Lucas (E. Lucas, “Théorie des Functions Numériques Simplement Periodiques," American J. Math., vol. 1 (1878), pp. 184-240, 289-321.) proved the following general result relating to Exercise 37. If $p$ is any prime number, then $(\frac{n}{j}) (mod p)$ can be found as follows: Expand $n$ and $j$ in base $p$ as $n = s_{0} + s_{1} p + s_{2} p^{2} + \dots + s_{k} p^{k}$ and $j = r_{0} + r_{1} p + r_{2} p^{2} + \dots + r_{k} p^{k}$ ⁠, respectively. (Here $k$ is chosen large enough to represent all numbers from 0 to $n$ in base $p$ using $k$ digits.) Let $s = (s_{0}, s_{1}, s_{2}, \dots, s_{k})$ and $r = (r_{0}, r_{1}, r_{2}, \dots, r_{k})$ ⁠. Then $(\frac{n}{j}) (mod p) = \prod_{i = 0}^{k} (\frac{s_{i}}{r_{i}}) (mod p) .$ For example, if $p = 7$ ⁠, $n = 12$ ⁠, and $j = 9$ ⁠, then

$\begin{matrix} 12 & = 5 \cdot 7^{0} + 1 \cdot 7^{1}, \\ 9 & = 2 \cdot 7^{0} + 1 \cdot 7^{1}, \end{matrix}$

so that

$\begin{matrix} s & = (5, 1), \\ r & = (2, 1), \end{matrix}$

and this result states that $(\frac{12}{9}) (mod p) = (\frac{5}{2}) (\frac{1}{1}) (mod 7) .$ Since $(\frac{12}{9}) = 220 = 3 (mod 7)$ ⁠, and $(\frac{5}{2}) = 10 = 3 (mod 7)$ ⁠, we see that the result is correct for this example.

Show that this result implies that, for $p = 2$ ⁠, the $(p^{k} - 1)$ ⁠st row of your triangle in Exercise 37 has no zeros.

Exercise 3.2.37 in the book ↗

Let $n (mod m)$ denote the remainder when the integer $n$ is divided by the integer $m$ ⁠. Write a computer program to compute the numbers $(\frac{n}{j}) (mod m)$ where $(\frac{n}{j})$ is a binomial coefficient and $m$ is an integer. You can do this by using the recursion relations for generating binomial coefficients, doing all the arithmetic using the basic function mod( $n, m$ ⁠). Try to write your program to make as large a table as possible. Run your program for the cases $m = 2$ to 7. Do you see any patterns? In particular, for the case $m = 2$ and $n$ a power of 2, verify that all the entries in the $(n - 1)$ ⁠st row are 1. (The corresponding binomial numbers are odd.) Use your pictures to explain why this is true.

Answer

Consider the Pascal triangle (mod 3) for example. $\begin{matrix} 0 & 1 \\ 1 & 1 1 \\ 2 & 1 2 1 \\ 3 & 1 0 0 1 \\ 4 & 1 1 0 1 1 \\ 5 & 1 2 1 1 2 1 \\ 6 & 1 0 0 2 0 0 1 \\ 7 & 1 1 0 2 2 0 1 1 \\ 8 & 1 2 1 2 1 2 1 2 1 \\ 9 & 1 0 0 0 0 0 0 0 0 1 \\ 10 & 1 1 0 0 0 0 0 0 0 1 1 \\ 11 & 1 2 1 0 0 0 0 0 0 1 2 1 \\ 12 & 1 0 0 1 0 0 0 0 0 1 0 0 1 \\ 13 & 1 1 0 1 1 0 0 0 0 1 1 0 1 1 \\ 14 & 1 2 1 1 2 1 0 0 0 1 2 1 1 2 1 \\ 15 & 1 0 0 2 0 0 1 0 0 1 0 0 2 0 0 1 \\ 16 & 1 1 0 2 2 0 1 1 0 1 1 0 2 2 0 1 1 \\ 17 & 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 \\ 18 & 1 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 1 \end{matrix}$ Note first that the entries in the third row are 0 for $0 < j < 3$ ⁠. Lucas notes that this will be true for any $p$ ⁠. To see this assume that $0 < j < p$ ⁠. Note that $(\frac{p}{j}) = \frac{p (p - 1) \dots p - j + 1}{j (j - 1) \dots 1}$ is an integer. Since $p$ is prime and $0 < j < p$ ⁠, $p$ is not divisible by any of the terms of $j!$ ⁠, and so $(p - 1)!$ must be divisible by $j!$ ⁠. Thus for $0 < j < p$ we have $(\frac{p}{j}) = 0 mod p$ ⁠. Let us call the triangle of the first three rows a basic triangle. The fact that the third row is $1 0 0 1$ produces two more basic triangles in the next three rows and an inverted triangle of 0’s between these two basic triangles. This leads to the 6’th row $1 0 0 2 0 0 1$ .

This produces a basic triangle, a basic triangle multiplied by 2 (mod 3), and then another basic triangle in the next three rows. Again these triangles are separated by inverted 0 triangles. We can continue this way to construct the entire Pascal triangle as a bunch of multiples of basic triangles separated by inverted 0 triangles. We need only know what the mutiples are. The multiples in row $n p$ occur at positions $0, p, 2 p, . . ., n p$ ⁠. Looking at the triangle we see that the multiple at position $(m p, j p)$ is the sum of the multiples at positions $(j - 1) p$ and $j p$ in the $(m - 1) p$ ⁠’th row. Thus these multiples satisfy the same recursion relation $(\frac{n}{j}) = (\frac{n - 1}{j - 1}) + (\frac{n - 1}{j})$ that determined the Pascal triangle. Therefore the multiple at position $(m p, j p)$ in the triangle is $(\frac{m}{j})$ ⁠. Suppose we want to determine the value in the Pascal triangle mod $p$ at the position $(n, j)$ ⁠. Let $n = s p + s_{0}$ and $j = r p + r_{0}$ ⁠, where $s_{0}$ and $r_{0}$ are $< p$ ⁠. Then the point $(n, j)$ is at position $(s_{0}, r_{0})$ in a basic triangle multiplied by $(\frac{s}{r})$ ⁠.

Thus $(\frac{n}{j}) = (\frac{s}{r}) (\frac{s_{0}}{r_{0}}) .$ But now we can repeat this process with the pair $(s, r)$ and continue until $s < p$ ⁠. This gives us the result: $(\frac{n}{j}) = \prod_{i = 0}^{k} (\frac{s_{i}}{r_{j}}) (mod p),$ where $s = s_{0} + s_{1} p^{1} + s_{2} p^{2} + \dots + s_{k} p^{k},$ $j = r_{0} + r_{1} p^{1} + r_{2} p^{2} + \dots + r_{k} p^{k} .$ If $r_{j} > s_{j}$ for some $j$ then the result is 0 since, in this case, the pair $(s_{j}, r_{j})$ lies in one of the inverted 0 triangles.

If we consider the row $p^{k} - 1$ then for all $k$ ⁠, $s_{k} = p - 1$ and $r_{k} \leq p - 1$ so the product will be positive resulting in no zeros in the rows $p^{k} - 1$ ⁠. In particular for $p = 2$ the rows $p^{k} - 1$ will consist of all 1’s.

Exercise 3.2.39 §3.2 source ↗

Prove that the probability of exactly $n$ heads in $2 n$ tosses of a fair coin is given by the product of the odd numbers up to $2 n - 1$ divided by the product of the even numbers up to $2 n$ ⁠.

Answer

$\begin{matrix} b (2 n, \frac{1}{2}, n) & = 2^{- 2 n} \frac{2 n!}{n! n!} = \frac{2 n (2 n - 1) \dots 2 \cdot 1}{2 n \cdot 2 (n - 1) \dots 2 \cdot 2 n \cdot 2 (n - 1) \dots 2} \\ = \frac{(2 n - 1) (2 n - 3) \dots 1}{2 n (2 n - 2) \dots 2} . \end{matrix}$

Exercise 3.3.3 §3.3 source ↗

Theorem 3.9 in the book ↗

Let $a$ and $b$ be two positive integers. Let $S_{a, b}$ be the set of all ordered pairs in which the first entry is an $a$ ⁠-shuffle and the second entry is a $b$ ⁠-shuffle. Let $S_{a b}$ be the set of all $a b$ ⁠-shuffles. Then there is a 1-1 correspondence between $S_{a, b}$ and $S_{a b}$ with the following property. Suppose that $(T_{1}, T_{2})$ corresponds to $T_{3}$ ⁠. If $T_{1}$ is applied to the identity ordering, and $T_{2}$ is applied to the resulting ordering, then the final ordering is the same as the ordering that is obtained by applying $T_{3}$ to the identity ordering. Proof. The easiest way to describe the required correspondence is through the idea of an unshuffle. An $a$ ⁠-unshuffle begins with a deck of $n$ cards. One by one, cards are taken from the top of the deck and placed, with equal probability, on the bottom of any one of $a$ stacks, where the stacks are labelled from 0 to $a - 1$ ⁠. After all of the cards have been distributed, we combine the stacks to form one stack by placing stack $i$ on top of stack $i + 1$ ⁠, for $0 \leq i \leq a - 1$ ⁠. It is easy to see that if one starts with a deck, there is exactly one way to cut the deck to obtain the $a$ stacks generated by the $a$ ⁠-unshuffle, and with these $a$ stacks, there is exactly one way to interleave them to obtain the deck in the order that it was in before the unshuffle was performed. Thus, this $a$ ⁠-unshuffle corresponds to a unique $a$ ⁠-shuffle, and this $a$ ⁠-shuffle is the inverse of the original $a$ ⁠-unshuffle.

If we apply an $a b$ ⁠-unshuffle $U_{3}$ to a deck, we obtain a set of $a b$ stacks, which are then combined, in order, to form one stack. We label these stacks with ordered pairs of integers, where the first coordinate is between 0 and $a - 1$ ⁠, and the second coordinate is between 0 and $b - 1$ ⁠. Then we label each card with the label of its stack. The number of possible labels is $a b$ ⁠, as required. Using this labelling, we can describe how to find a $b$ ⁠-unshuffle and an $a$ ⁠-unshuffle, such that if these two unshuffles are applied in this order to the deck, we obtain the same set of $a b$ stacks as were obtained by the $a b$ ⁠-unshuffle.

To obtain the $b$ ⁠-unshuffle $U_{2}$ ⁠, we sort the deck into $b$ stacks, with the $i$ ⁠th stack containing all of the cards with second coordinate $i$ ⁠, for $0 \leq i \leq b - 1$ ⁠. Then these stacks are combined to form one stack. The $a$ ⁠-unshuffle $U_{1}$ proceeds in the same manner, except that the first coordinates of the labels are used. The resulting $a$ stacks are then combined to form one stack.

The above description shows that the cards ending up on top are all those labelled $(0, 0)$ ⁠. These are followed by those labelled $(0, 1), (0, 2),$ $\dots,$ $(0, b - 1),$ $(1, 0),$ $(1,1),$ $\dots,$ $(a - 1, b - 1)$ ⁠. Furthermore, the relative order of any pair of cards with the same labels is never altered. But this is exactly the same as an $a b$ ⁠-unshuffle, if, at the beginning of such an unshuffle, we label each of the cards with one of the labels $(0, 0),$ $(0, 1),$ $\dots,$ $(0, b - 1),$ $(1, 0),$ $(1,1),$ $\dots,$ $(a - 1, b - 1)$ ⁠. This completes the proof.

Let $D$ be a deck of $n$ cards. We have seen that there are $a^{n}$ $a$ ⁠-shuffles of $D$ ⁠. A coding of the set of $a$ ⁠-unshuffles was given in the proof of Theorem 3.9. We will now give a coding of the $a$ ⁠-shuffles which corresponds to the coding of the $a$ ⁠-unshuffles. Let $S$ be the set of all $n$ ⁠-tuples of integers, each between 0 and $a - 1$ ⁠. Let $M = (m_{1}, m_{2}, \dots, m_{n})$ be any element of $S$ ⁠. Let $n_{i}$ be the number of $i$ ⁠’s in $M$ ⁠, for $0 \leq i \leq a - 1$ ⁠. Suppose that we start with the deck in increasing order (i.e., the cards are numbered from 1 to $n$ ⁠). We label the first $n_{0}$ cards with a 0, the next $n_{1}$ cards with a 1, etc. Then the $a$ ⁠-shuffle corresponding to $M$ is the shuffle which results in the ordering in which the cards labelled $i$ are placed in the positions in $M$ containing the label $i$ ⁠. The cards with the same label are placed in these positions in increasing order of their numbers. For example, if $n = 6$ and $a = 3$ ⁠, let $M = (1, 0, 2, 2, 0, 2)$ ⁠. Then $n_{0} = 2, n_{1} = 1,$ and $n_{2} = 3$ ⁠. So we label cards 1 and 2 with a 0, card 3 with a 1, and cards 4, 5, and 6 with a 2. Then cards 1 and 2 are placed in positions 2 and 5, card 3 is placed in position 1, and cards 4, 5, and 6 are placed in positions 3, 4, and 6, resulting in the ordering $(3, 1, 4, 5, 2, 6)$ ⁠.

(a) Using this coding, show that the probability that in an $a$ ⁠-shuffle, the first card (i.e., card number 1) moves to the $i$ ⁠th position, is given by the following expression: $\frac{{(a - 1)}^{i - 1} a^{n - i} + {(a - 2)}^{i - 1} {(a - 1)}^{n - i} + \dots + 1^{i - 1} 2^{n - i}}{a^{n}} .$

(b) Give an accurate estimate for the probability that in three riffle shuffles of a 52-card deck, the first card ends up in one of the first 26 positions. Using a computer, accurately estimate the probability of the same event after seven riffle shuffles.

Answer

(a) $96.99 %$

(b) $55.16 %$

Loading chapter 4…

Exercises and answers are adapted from Grinstead and Snell's Introduction to Probability by The CHANCE Project, which is free to read and download, and are used under the GNU FDL licence. They are taken from the GNU version’s LaTeX source (4 July 2006), with answers from the authors’ published answers to the odd-numbered exercises, and set for the web, so they may differ slightly from the printed page. This adaptation is released under the same licence and is neither affiliated with nor endorsed by Grinstead and Snell or American Mathematical Society. Copyright (C) 2006 Peter G. Doyle. This work is a version of Grinstead and Snell's ‘Introduction to Probability, 2nd edition’, published by the American Mathematical Society, Copyright (C) 2003 Charles M. Grinstead and J. Laurie Snell.