4.2 Combinatorial Analysis

Many problems in probability theory can be solved by simply counting the number of different ways that a certain event can occur. The mathematic theory of counting is often referred to as combinatorial analysis (or combinatorics). In this section, we will cover the basics of combinatorial analysis.

Basic principle of counting: Let $S$ be a set of length-$k$ sequences. If there are

• $n_1$ possible first entries,
• $n_2$ possible second entries for each first entry,
• $n_3$ possible third entries for each combination of first and second entries, etc.

Then there are a total of $n_1\cdot n_2\cdots n_k$ possible outcomes.

Permutation: A rearrangement of objects into distinct sequence (i.e., order matters).

Property: There are $\displaystyle\frac{n!}{n_1!n_2!\cdots n_r!}$ different permutations of $n$ objects, of which $n_1$ are alike, $n_2$ are alike, $\cdots$, $n_r$ are alike.

Combination: An unordered collection of objects (i.e., order doesn’t matter).

Property: There are $\displaystyle\binom nr=\frac{n!}{(n-r)!r!}$ different combinations of $n$ distinct objects taken $r$ at a time.

Binomial theorem: $\displaystyle(x+y)^n=\sum_{k=0}^{n}\binom nk x^k y^{n-k}$

Inclusion-Exclusion Principle: $P(E_1\cup E_2)=P(E_1)+P(E_2)-P(E_1E_2)$

and more generally,

where $\displaystyle\sum_{i_1<i_2<\cdots i_r}P(E_{i_1}E_{i_2}\cdots E_{i_r})$ has $\displaystyle\binom Nr$ terms.

Poker hands

Poker is a card game in which each player gets a hand of 5 cards. There are 52 cards in a deck. Each card has a value and belongs to a suit. There are 13 values, $2,3,4,5,6,7,8,9,10,\overset{\text{jack}}{J},\overset{\text{queen}}{Q},\overset{\text{king}}{K},\overset{\text{ace}}{A}$, and four suits, ♠spade, ♣club, ♥heart, ♦diamond.

What are the probabilities of getting hands with four-of-a-kind (four of the five cards with the same value)? Hands with a full house (three cards of one value and two cards of another value)? Hands with two pairs?

Solution: The number of different hands of a five-card draw is the number of 5-element subsets of a 52-element set, so total number of hands $\displaystyle=\binom{52}{5}=2,598,960$.

Hands with a four-of-a-kind: First we can choose the value of the four cards with the same value, there are 13 choices. The 5th card can be any of the rest 48 cards (12 choices for values and 4 choices for suits). So the number of hands with four-of-a kind is $13\times48=624$.

Hands with a Full House: In sequence we need to choose the value of the triple, 13 choices; the suits of the triple, $\displaystyle\binom43$ choices; the value of the pair, 12 choices; and the suits of the pair, $\displaystyle\binom42$ choices. So the number of hands with full house is $\displaystyle13\times\binom43\times12\times\binom42=13\times4\times12\times6=3,744$.

Hands with Two Pairs: In sequence we need to choose the values of the two pairs, $\displaystyle\binom{13}{2}$ choices; the suits of the first pair, $\displaystyle\binom42$ choices; the suits of the second pair, $\displaystyle\binom42$ choices; and the remaining card, 44 ($52-4\times2$, since the last cards can not have the same value as either pair) choices. So the number of hands with two pairs is $\displaystyle\binom{13}{2}\times\binom42\times\binom42\times44=78\times6\times6\times44=123,552$.

To calculate the probability of each, we only need to divide the number of hands of each kind by the total possible number of hands.

Hopping rabbit

A rabbit sits at the bottom of a staircase with $n$ stairs. The rabbit can hop up only one or two stairs at a time. How many different ways are there for the rabbit to ascend to the top of the stairs?⁵

Solution: Let’s begin with the simplest cases and consider solving the problem for any number of stairs using induction. For $n=1$, there is only one way and $f(1)=1$. For $n=2$, we can have one 2-stair hop or two 1-stair hops. So $f(2)=2$. For any $n>2$, there are always two possibilities for the last hop, either it’s a 1-stair hop or a 2-stair hop. In the former case, the rabbit is at $(n-1)$ before reaching $n$, and it has $f(n-1)$ ways to reach $(n-1)$. In the latter case, the rabbit is at $(n-2)$ before reaching $n$, and it has $f(n-2)$ ways to reach $(n-2)$. So we have $f(n)=f(n-2)+f(n-1)$. Using this function we can calculate $f(n)$ for $n=3,4,\cdots$⁶

Screwy pirates 2

Having peacefully divided the loot (in chapter 2), the pirate team goes on for more looting and expands the group to 11 pirates. To protect their hard-won treasure, they gather together to put all the loot in a safe. Still being a democratic bunch, they decide that only a majority — any majority — of them ($\ge6$) together can open the safe. So they ask a locksmith to put a certain number of locks on the safe. To access the treasure, every lock needs to be opened. Each lock can have multiple keys; but each key only opens one lock. The locksmith can give more than one key to each pirate.

What is the smallest number of locks needed? And how many keys must each pirate carry?⁷

Solution: This problem is a good example of the application of combinatorial analysis in information sharing and cryptography. A general version of the problem was explained in a 1979 paper “How to Share a Secret” by Adi Shamir. Let’s randomly select 5 pirates from the 11-member group; there must be a lock that none of them has the key to. Yet any of the other 6 pirates must have the key to this lock since any 6 pirates can open all locks. In other words, we must have a “special” lock to which none of the 5 selected pirates has a key and the other 6 pirates all have keys. Such 5-pirate groups are randomly selected. So for each combination of 5 pirates, there must be such a “special” lock. The minimum number of locks needed is $\displaystyle\binom{11}{5}=\frac{11!}{5!6!}=462$ locks. Each lock has 6 keys, which are given to a unique 6-member subgroup. So each pirate must have $\displaystyle\frac{462\times6}{11}=252$ keys. That’s surely a lot of locks to put on a safe and a lot of keys for each pirate to carry.

Chess tournament

A chess tournament has $2^n$ players with skills $1>2>\cdots>2^n$. It is organized as a knockout tournament, so that after each round only the winner proceeds to the next round. Except for the final, opponents in each round are drawn at random. Let’s also assume that when two players meet in a game, the player with better skills always wins. What’s the probability that players 1 and 2 will meet in the final?⁸

Solution: There are at least two approaches to solve the problem. The standard approach applies multiplication rule based on conditional probability, while a counting approach is far more efficient. (We will cover conditional probability in detail in the next section.)

Let’s begin with the conditional probability approach, which is easier to grasp. Since there are $2^n$ players, the tournament will have $n$ rounds (including the final). For round 1, players $2,3,\cdots,2^n$ each have $\displaystyle\frac1{2^n-1}$ probability to be 1’s rival, so the probability that 1 and 2 do not meet in round 1 is $\displaystyle\frac{2^n-2}{2^n-1}=\frac{2\times(2^{n-1}-1)}{2^n-1}$. Condition on that 1 and 2 do not meet in round 1, $2^{n-1}$ players proceed to the 2nd round and the conditional probability that 1 and 2 will not meet in round 2 is $\displaystyle\frac{2^{n-1}-2}{2^{n-1}-1}=\frac{2\times(2^{n-2}-1)}{2^{n-1}-1}$. We can repeat the same process until the $(n-1)$th round, in which there are $2^2$ ($=2^n/2^{n-2}$) players left and the conditional probability that 1 and 2 will not meet in round $(n-1)$ is $\displaystyle\frac{2^2-2}{2^2-1}=\frac{2\times(2^{2-1}-1)}{2^2-1}$.

Let $E_1$ be the event that 1 and 2 do not meet in round 1;
$E_2$ be the event that 1 and 2 do not meet in rounds 1 and 2;
…
$E_{n-1}$ be the event that 1 and 2 do not meet in round $1,2,\cdots,n-1$.

Apply the multiplication rule, we have

Now let’s move on to the counting approach. Figure 4.2A is the general case of what happens in the final. Player 1 always wins, so he will be in the final. From the figure, it is obvious that $2^n$ players are separated to two $2^{n-1}$-player subgroups and each group will have one player reaching the final. As shown in Figure 4.2B, for player 2 to reach the final, he/she must be in a different subgroup from 1. Since any of the remaining players in $2,3,\cdots,2^n$ are likely to be one of the $(2^{n-1}-1)$ players in the same subgroup as player 1 or one of the $2^{n-1}$ players in the subgroup different from player 1, the probability that 2 is in a different subgroup from 1 and that 1 and 2 will meet in the final is simply $\displaystyle\frac{2^{n-1}}{2^n-1}$. Clearly, the counting approach provides not only a simpler solution but also more insight to the problem.

Application letters

You’re sending job applications to 5 firms: Morgan Stanley, Lehman Brothers, UBS, Goldman Sachs, and Merrill Lynch. You have 5 envelopes on the table neatly typed with names and addresses of people at these 5 firms. You even have 5 cover letters personalized to each of these firms. Your 3-year-old tried to be helpful and stuffed each cover letter into each of the envelopes for you. Unfortunately she randomly put letters 70 into envelopes without realizing that the letters are personalized. What is the probability that all 5 cover letters are mailed to the wrong firms?⁹

Solution: This problem is a classic example for the Inclusion-Exclusion Principle. In fact, a more general case is an example in Ross’ textbook First Course in Probability.

Let’s denote by $E_i,i=1,\cdots,5$ the event that the $i$-th letter has the correct envelope. Then $\displaystyle P\left(\bigcup_{i=1}^{5}E_i\right)$ is the probability that at least one letter has the correct envelope and $\displaystyle1-P\left(\bigcup_{i=1}^{5}E_i\right)$ is the probability that all letters have the wrong envelopes. $\displaystyle P\left(\bigcup_{i=1}^{5}E_i\right)$ can be calculated using the Inclusion-Exclusion Principle:

It’s obvious that $P(E_i)=\frac15,\ \forall i=1,\cdots,5$. So $\displaystyle\sum_{i=1}^{5}P(E_i)=1$.

$P(E_{i_1}E_{i_2})$ is the event that both letter $i_1$ and letter $i_2$ have the correct envelope. The probability that $i_1$ has the correct envelope is $1/5$; Conditioned on that $i_1$ has the correct envelope, the probability that $i_2$ has the correct envelope is $1/4$ (there are only 4 envelopes left). So $\displaystyle P(E_{i_1}E_{i_2})=\frac15\times\frac1{5-1}=\frac{(5-2)!}{5!}$.

There are $\displaystyle\binom52=\frac{5!}{2!(5-2)!}$ members of $P(E_{i_1}E_{i_2})$ in $\displaystyle\sum_{i_1<i_2}P(E_{i_1}E_{i_2})$, so we have

Similarly we have $\displaystyle\sum_{i_1<i_2<i_3}P(E_{i_1}E_{i_2}E_{i_3})=\frac1{3!}$, $\displaystyle\sum_{i_1<i_2<i_3<i_4}P(E_{i_1}E_{i_2}E_{i_3}E_{i_4})=\frac1{4!}$, and $\displaystyle P(E_1E_2\cdots E_5)=\frac1{5!}$.

So the probability that all 5 letters are mailed to the wrong firms is $\displaystyle1-P\left(\bigcup_{i=1}^{5}E_i\right)=\frac{11}{30}$.

Birthday problem

How many people do we need in a class to make the probability that two people have the same birthday more than $1/2$? (For simplicity, assume 365 days a year.)

Solution: The number is surprisingly small: 23. Let’s say we have $n$ people in the class. Without any restrictions, we have 365 possibilities for each individual’s birthday. The basic principle of counting tells us that there are $365^n$ possible sequences.

We want to find the number of those sequences that have no duplication of birthdays. For the first individual, we can choose any of the 365 days; but for the second, only 364 remaining choices left, …, for the $r$th individual, there are $365-r+1$ choices. So for $n$ people there are $365\times364\times\cdots\times(365-n+1)$ possible sequences where no two individuals have the same birthday. We need to have $\displaystyle\frac{365\times364\times\cdots\times(365-n+1)}{365^n}<1/2$ for the odds to be in our favor. The smallest such $n$ is 23.

100th digit

What is the 100th digit to the right of the decimal point in the decimal representation of $(1+\sqrt2)^{3000}$?¹⁰

Solution: If you still have not figure out the solution from the hint, here is one more hint: $(1+\sqrt2)^n+(1-\sqrt2)^n$ is an integer when $n=3000$.

Applying the binomial theorem for $(x+y)^n$, we have

So $\displaystyle(1+\sqrt2)^n+(1-\sqrt2)^n=2\sum_{\substack{k=2j,\,0\le j\le n/2}}^{n}\binom nk1^{n-k}(\sqrt2)^k$, which is always an integer. It is easy to see that $0<(1-\sqrt2)^{3000}\ll10^{-100}$. So the 100th digit of $(1+\sqrt2)^n$ must be 9.

Cubic of integer

Let $x$ be an integer between 1 and $10^{12}$, what is the probability that the cubic of $x$ ends with 11?¹¹

Solution: All integers can be expressed as $x=a+10b$, where $a$ is the last digit of $x$. Applying the binomial theorem, we have $x^3=(a+10b)^3=a^3+30a^2b+300ab^2+1000b^3$.

The unit digit of $x^3$ only depends on $a^3$. So $a^3$ has a unit digit of 1. Only $a=1$ satisfies this requirement and $a^3=1$. Since $a^3=1$, the tenth digit only depends on $30a^2b=30b$. So we must have that $3b$ ends in 1, which requires the last digit of $b$ to be 7. Consequently, the last two digits of $x$ should be 71, which has a probability of 1% for integers between 1 and $10^{12}$.