Combinatorial Probability - Examples and Constructions

Combinatorial probability problems span diverse applications from card games to quality control. Mastering these requires recognizing problem patterns and applying appropriate counting techniques.

Card Problems

A standard deck has 52 cards: 4 suits (spades, hearts, diamonds, clubs) with 13 ranks each.

Example

Poker Hands: What is the probability of being dealt a full house (three of one rank, two of another)?

Total 5-card hands: $\binom{52}{5} = 2,598,960$

To count full houses:

Choose the rank for three cards: 13 ways
Choose 3 cards from that rank: $\binom{4}{3} = 4$ ways
Choose the rank for two cards: 12 remaining ways
Choose 2 cards from that rank: $\binom{4}{2} = 6$ ways

Number of full houses: $13 \times 4 \times 12 \times 6 = 3,744$

Probability: $\frac{3,744}{2,598,960} \approx 0.00144 \approx 0.144\%$

Sampling With and Without Replacement

With Replacement: After selecting an object, it is returned before the next selection. Order matters → $n^r$ ways to select $r$ objects from $n$ .

Without Replacement, Ordered: $P(n,r) = \frac{n!}{(n-r)!}$ ways.

Without Replacement, Unordered: $\binom{n}{r}$ ways.

Example

Drawing 3 balls from an urn containing 10 balls numbered 1-10:

With replacement, order matters: $10^3 = 1,000$ outcomes
Without replacement, order matters: $10 \times 9 \times 8 = 720$ outcomes
Without replacement, order doesn't matter: $\binom{10}{3} = 120$ outcomes

Birthday Problem

Example

Classic Birthday Problem: In a group of $n$ people, what is the probability that at least two share a birthday?

Assume 365 days and birthdays uniformly distributed. Use the complement: $P(\text{at least one match}) = 1 - P(\text{all different})$

If all birthdays are different: $P(\text{all different}) = \frac{365 \times 364 \times \cdots \times (365-n+1)}{365^n} = \frac{P(365,n)}{365^n}$

For $n = 23$ : $P(\text{match}) \approx 1 - 0.493 = 0.507 > 50\%$

Surprisingly, with just 23 people, there's a better than even chance of a shared birthday!

Occupancy Problems

Definition

Occupancy problems involve distributing $n$ distinguishable balls into $r$ distinguishable boxes. The number of ways depends on whether order matters and whether multiple balls can occupy the same box.

Each box holds at most one ball: $P(r,n)$ ways (if $n \leq r$ )
Boxes can hold multiple balls: $r^n$ ways
Exactly one ball per box (matching problem): $n!$ ways (if $n = r$ )

Example

Secretary Problem: Assigning 5 letters to 5 envelopes randomly. What's the probability exactly 3 letters go to the correct envelope?

This is impossible! If 3 letters are correct, the remaining 2 must also be correct. So $P(\text{exactly 3 correct}) = 0$ .

Hypergeometric Distribution

Definition

Draw $n$ objects without replacement from a population of $N$ objects containing $K$ successes. The probability of exactly $k$ successes is: $P(X = k) = \frac{\binom{K}{k} \binom{N-K}{n-k}}{\binom{N}{n}}$

Example

A committee of 5 is selected from 6 men and 4 women. Probability of exactly 3 women: $P(3 \text{ women}) = \frac{\binom{4}{3}\binom{6}{2}}{\binom{10}{5}} = \frac{4 \times 15}{252} = \frac{60}{252} = \frac{5}{21} \approx 0.238$

Remark

The key to solving combinatorial probability problems is careful problem decomposition: identify what is being counted, whether order matters, whether sampling is with or without replacement, and then apply the appropriate counting formula.