How Many Ways Could This Happen?

Twenty coin tosses have a million or so possible sequences. Yet when we ask how many contain exactly ten heads, counting each sequence by hand becomes an irritating way to spend an afternoon.

Fortunately, mathematicians noticed this problem before we did.

Multiply when decisions happen in stages

If there are three shirt choices and four independent trouser choices, there are $3\times4=12$ outfits. The multiplication principle counts a sequence of decisions when each step has a specified number of options.

If repetition is allowed, selecting a four-digit PIN with digits 0–9 gives $10^4=10,000$ possible strings. If digits must be distinct, the count is $10\times9\times8\times7=5,040$.

These count ordered selections. The sequence 1234 is not the same PIN as 4321.

Order sometimes does not matter

A committee containing Alice and Bob is the same committee regardless of which name we write first. Selecting $k$ people from $n$ without caring about order is counted by a combination:

$$\binom nk=\frac{n!}{k!(n-k)!}.$$

A factorial $n!$ is the product of positive integers through $n$, with $0!=1$.

For eight volunteers selecting a four-person experimental group,

$$\binom84=\frac{8!}{4!4!}=70.$$

That number was the entire reference distribution for our exact randomization laboratory.

Return to the coin

Each sequence of 20 independent fair tosses has probability $2^{-20}$. For exactly ten heads, the heads can occupy any choice of ten of the twenty positions. Therefore,

$$P(X=10)=\binom{20}{10}2^{-20}.$$

The probability calculation is valid under the fair independent-toss model. It would be a mistake to use equal sequence probabilities for a biased coin without modification.

Counting isn’t always the best tool

When events overlap, naive addition double-counts. With sampling without replacement, probabilities change after each draw. Sometimes conditional probability or simulation is more direct than heroic combinatorics.

Counting rules serve a model; they do not excuse us from specifying the model.

Check yourself

1. How many three-letter codes can be made from A–Z if repetition is allowed?
2. In how many ways can three people be chosen from seven when order doesn’t matter?
3. Why is $\binom{10}{3}$ relevant to the probability of exactly three heads in ten fair tosses?

Worked responses

1. $26^3=17,576$.

2. $\binom73=35$.

3. It counts which three toss positions contain heads. Each specific sequence has probability $2^{-10}$.

Derive combinations and distinguish sampling models

For $k$ distinct selections from $n$ objects, ordered selection without replacement gives $n(n-1)\cdots(n-k+1)=n!/(n-k)!$ possibilities. Each unordered subset appears in $k!$ different orders. Dividing gives $\binom nk$. The reasoning, not the factorial button, determines when the formula applies.

Suppose a fictional box contains 5 red and 7 blue counters. Draw 4 without replacement. Every four-counter subset is equally likely under simple random drawing, and exactly two red counters can be chosen in $\binom52\binom72$ ways. Therefore

$$P(X=2)=\frac{\binom52\binom72}{\binom{12}4}=\frac{210}{495}=\frac{14}{33}\approx0.42424.$$

This is a hypergeometric calculation. A binomial model with success probability $5/12$ would instead assume replacement or independent trials with constant success probability. Without replacement, the chance of a red counter on the next draw changes with what has already been removed. Independence is a probability assumption; the ability to count outcomes does not create it.

For a binomial count, $\binom nk$ counts the possible positions of $k$ successes in $n$ trials. Each particular sequence has probability $p^k(1-p)^{n-k}$ under independent constant-probability trials. Multiplying gives the binomial mass function. “There are two outcomes” does not imply they are equally probable, nor does it establish independence.

Further problems

1. How many ordered three-letter strings can be formed from five distinct letters without repetition? How many unordered three-letter subsets?
2. In the counter example, calculate the probability all four are blue.
3. Why does shuffling an existing sample not create new independent participants?

Worked further solutions

1. $5\cdot4\cdot3=60$ strings and $\binom53=10$ subsets.
2. $\binom74/\binom{12}4=35/495=7/99$.
3. It changes ordering, not the units observed or their data-generating dependence. Randomization of labels and independent data collection are different operations.