Questions

Story Proof Practice

Story proofs are a fundamental and useful way that we will go about proving important results, especially later in the course. To that end, provide story proofs for each of the following results:

Q

$$\sum_{k=0}^n {n \choose k } = 2^n$$

A

Suppose we want to figure out all possible numbers we can represent using n bits. (Bits are binary, taking on a value of either 0 or 1).

(RHS) Since each bit can be either 1 or 0, there are $2^n$ possible bits. Because bits take on 2 values of being either a 1 or 0, there would be $2^n$ total possible sequences.

(LHS) ${n \choose k}$ represents the number of different bit combinations where there are $k$ 1's we can make from $n$ bits. ${n \choose 0}$ represents all bits with no 1's, ${n \choose 1}$ represents all bits with two 1's, and so on. Therefore, $\sum_{k=0}^n {n \choose k}$ represents all possible bits.

Q

$$\left(\begin{array}{l} n \\ k \end{array}\right)+\left(\begin{array}{c} n \\ k-1 \end{array}\right)=\left(\begin{array}{c} n+1 \\ k \end{array}\right)$$

A

Suppose we have a group of $n$ people and a celebrity, and we have to select a committee of $k$ people.

(RHS) The straightforward way is to just choose $k$ people from the group of $n+1,$ giving us ${n+1 \choose k}$ possible committees.

(LHS) Suppose we must have the celebrity on the committee. Then there are ${n \choose k-1}$ ways to choose who else will be on the committee. Also, suppose that we don't want to have the celebrity on the committee. Then there are ${n \choose k}$ ways to choose who is on the committee. This gives us a total of ${n \choose k-1} + {n \choose k}$ ways to pick the committee.

Recall that these two expressions both represent ${n \choose k}$ or the number of ways to choose a committee of size $k$ from $n$ people.

Q

$$\frac{n!}{(n-k)!k!} = \frac{n \cdot (n-1) \dotsm (n-k+1)}{k\cdot (k-1)\dotsm 1}$$

A

Recall that these two expressions both represent ${n \choose k}$ or the number of ways to choose a committee of size $k$ from $n$ people.

(LHS) We first permute the $n$ people and then select the first $k$ people in the permutation. While there $n!$ total permutations, we must deal with the overcounting within the committee and the people not selected for the committee. The $k$ people in the committee can be ordered in $k!$ ways and the people not in the committee can be ordered in $(n-k)!$ ways, which indicates that we have overcounted by a factor of $k!(n-k)!$. Therefore, we observe that

$${n \choose k} = \frac{n!}{k!(n-k)!}$$

(RHS) Alternatively, we can select the committee directly without permuting the $n$ people. We have $n$ choices for the first person on the committee, $n-1$ choices for the second person, and so on. We know by the multiplication rule that there are $n \cdot (n-1) \dotsm (n-k+1)$ committees of size $k$. However, since order doesn't matter within the committee, we have overcounted by a factor of $k!$. Therefore, we observe that

$${n\choose k} = \frac{n \cdot (n-1) \dotsm (n-k+1)}{k \cdot(k-1)\dots1}$$

Poker Probabilities

Suppose we have a standard 52-card deck, from which you are dealt five cards. Compute the probability of each of the following hands:

Q

A royal flush (getting 10, Jack, Queen, King, and Ace of the same suit)

A

For each of the four suits, there is only one way to obtain a royal flush. Therefore, the probability is simply $\frac{4}{{52 \choose 5}} \approx 0.0002$.

Q

A flush (all of the cards are of the same suit)

A

To obtain a flush, we must first choose a suit and then choose 5 cards from that suit. Therefore, the probability is $\frac{4 {13 \choose 5}}{{52 \choose 5}} \approx 0.0019$.

Q

A straight (all five cards are in consecutive order)

A

To obtain a straight, we first consider what the first card in our straight can be. Since the five cards must be in consecutive order, we have 10 possibilities for the first card in our straight (that is, a straight cannot begin with a Jack, Queen, or King). However, once we know what the first card in the straight is, the next four cards are determined. All that remains is deciding which suit each card will be! Therefore, the probability is $\frac{10 \cdot 4^5}{{52 \choose 5}} \approx 0.0039$.

Q

A three-of-a-kind (three cards show the same number, and the other two cards do not form a pair)

A

We first decide which value we want our three-of-a-kind to show, which gives us 13 options. From there, we have a choice of which 3 of the 4 suits we want it to be. For the next two cards, we require that they show different values, which means there are ${12 \choose 2}$ choices for what they can be, and each of these cards can be any suit. Therefore, the probability is $\frac{13{4\choose 3}{12 \choose 2}4^2}{{52\choose 5}} \approx 0.021$.

Q

A two-pair (two cards form a pair and another two cards form a different pair)

A

We first decide which two values we want on each pair, which gives us ${13 \choose 2}$ options. Within each pair, we have the choice of two suits, or ${4 \choose 2}^2$ ways to choose the suits of the two pair. The last card must be a different value from either of the pairs, and there are 11 choices with 4 choices of suit. Therefore, the probability is $\frac{{13\choose 2}{4\choose 2}^2 11 \cdot 4}{{52 \choose 5}} \approx 0.047$.

Complementary Cars

Suppose the probability of at least one car passing you at an intersection over the course of twenty minutes is given by 0.9. Assume that time intervals of the same length have the same probability of observing at least one car.

Q

What is the probability that at least one car passes you over the course of five minutes?

A

We know that

$$P(\text{at least one car in twenty minutes}) = 1 - P(\text{no cars in twenty minutes})$$

However, we also know that

$$P(\text{no cars in twenty minutes}) = (1-P(\text{at least one car in five minutes}))^4$$

Plugging in 0.9 and solving, we find that the probability that at least one car passes over the course of five minutes is approximately 0.44.