Counting Principles and Combinatorial Identities

Part 15, Chapter 15: Combinatorics and Probability

Learning objectives

Apply the multiplication and addition principles to multi-stage selections
Distinguish ordered (permutation) from unordered (combination) counts and pick the right formula
Compute and manipulate binomial coefficients $\binom{n}{k}$ using Pascal's recurrence
Recognise the binomial theorem as the algebraic shadow of counting subsets
Apply inclusion-exclusion to count unions of overlapping sets

Counting is harder than it looks, and it underlies every probability calculation you will ever do. The question "in how many ways can this happen?" sounds elementary, but it secretly drives every result downstream, the probability of a poker hand, the expected runtime of a randomised algorithm, the number of training examples a neural network can in principle distinguish. The trick is to spot which of two structural moves you are making: a sequence of decisions (multiplication), or a partition into cases (addition). Permutations, combinations, the binomial theorem, and inclusion-exclusion are all built from those two atoms.

The multiplication and addition principles

The multiplication principle says: if a process consists of $k$ sequential stages with $n_1, n_2, \ldots, n_k$ independent choices at each stage, the total number of outcomes is the product $n_1 \cdot n_2 \cdots n_k$ . Use it whenever your decisions are made in sequence and the count at each stage does not depend on previous choices.

The addition principle says: if a process can be split into mutually exclusive cases with $m_1, m_2, \ldots, m_j$ outcomes each, the total is $m_1 + m_2 + \cdots + m_j$ . Use it when you partition the possibilities by some discrete attribute (which suit was drawn, whether the first toss was heads, etc.).

A typical counting argument interleaves both rules: split into disjoint cases (addition), count each case by stages (multiplication), then sum.

Permutations and combinations

A permutation of $k$ objects chosen from $n$ is an ORDERED selection: there are $P(n,k) = \frac{n!}{(n-k)!}$ of them. A combination is an UNORDERED selection: there are $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ . The connecting identity is $P(n,k) = k!\binom{n}{k}$ , every unordered choice of $k$ items can be ordered in $k!$ ways, so dividing by $k!$ collapses permutations down to combinations.

When you read a problem, ask: does swapping two items give a different outcome? Yes → permutation. No → combination. Card hands are combinations (a hand is a set of cards); seating arrangements are permutations (who sits next to whom matters).

Binomial coefficients and Pascal's triangle

The number $\binom{n}{k}$ has a wealth of algebraic identities, but the load-bearing one is Pascal's recurrence: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ . Combinatorial proof: to choose $k$ items from $n$ , either the last item is in the chosen set (and we need $k-1$ from the first $n-1$ ) or it is not (and we need $k$ from the first $n-1$ ). These cases are disjoint, so by the addition principle we sum. Pascal's triangle is exactly this recurrence laid out as a number wall.

The binomial theorem states $(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k}$ k=0nbinomnkan−kbk. Why does the coefficient of $a^{n-k}b^{k}$ equal $\binom{n}{k}$ ? Because when you expand $(a+b)(a+b)\cdots(a+b)$ , each term comes from choosing $b$ in $k$ of the $n$ factors and $a$ in the remaining $n-k$ . The number of such choices is exactly $\binom{n}{k}$ . Setting $a = b = 1$ gives the satisfying identity $\sum_{k=0}^{n} \binom{n}{k} = 2^{n}$ k=0nbinomnk=2n: an $n$ -element set has $2^{n}$ subsets in total.

The widget above lets you select small $n$ and $k$ values and enumerate every ordered (or unordered) selection. Notice that toggling between "order matters" and "order does not matter" divides the count by exactly $k!$ , the formula $P(n,k) = k!\binom{n}{k}$ made visible.

Inclusion-exclusion

When two sets overlap, the naive sum $|A| + |B|$ double-counts the intersection. The inclusion-exclusion principle corrects this: $|A \cup B| = |A| + |B| - |A \cap B|$ . For three sets the formula adds back the triple intersection: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ . In general the signs alternate by the size of the intersection.

Where this shows up

Cryptography: The security of a password depends on the size of the keyspace. A 12-character password from a 94-character alphabet gives $94^{12} \approx 4.7 \times 10^{23}$ possibilities, pure multiplication principle. An 80-bit key space ( $2^{80}$ ) is the modern minimum-acceptable security level; smaller spaces fall to exhaustive search.

Machine learning, train/test splits: Picking a held-out test set of size $k$ from $n$ examples is $\binom{n}{k}$ ways. Cross-validation schemes pick disjoint folds, and the variance of the estimator depends on these combinatorial counts.

Lottery odds: A "pick 6 of 49" lottery has $\binom{49}{6} = 13{,}983{,}816$ tickets. Probability of jackpot is one over that, under one in 13 million. Combinations, not permutations, because the order of drawn numbers does not matter.

Genomics and combinatorial chemistry: A short DNA primer of length 20 has $4^{20} \approx 10^{12}$ possible sequences. Library design (which primers to synthesise, which compounds to test) starts from these counts.

Birthday-paradox attacks: Collisions in a hash function with $n$ outputs become likely after roughly $\sqrt{n}$ random queries, a counting fact about pairs ( $\binom{k}{2} \approx n$ when $k \approx \sqrt{n}$ ). This shapes hash-output-length choice in every cryptographic protocol.

Pause and think: In how many ways can the letters of the word "BANANA" be arranged? Why is the answer $\frac{6!}{3!\,2!}$ rather than $6!$ ? (Hint: identical letters cannot be distinguished by position.)

Try it

Predict first: how many 5-card poker hands are there? Now compute $\binom{52}{5}$ and check.

How many ways can 8 distinct books be split into two unordered piles of 4? Why is the answer $\binom{8}{4}/2$ rather than $\binom{8}{4}$ ?

Use Pascal's recurrence to compute $\binom{6}{2}$ from $\binom{5}{1}$ and $\binom{5}{2}$ . Verify against the direct formula.

True or false: $\binom{n}{k} = \binom{n}{n-k}$ . Give a one-sentence combinatorial proof.

In a class of 30 students, 18 study calculus, 14 study probability, and 8 study both. How many study at least one? How many study neither?

A trap to watch for

The most common counting mistake is double-counting indistinguishable arrangements. If you count by stages (first choose the captain, then choose the 4 other team members), you are imposing an order on a team that has none, and your count will be too large by a factor of $k!$ . The fix is either to count unordered from the start (use $\binom{n}{k}$ ), or to count ordered and divide by the over-count factor. Another classic trap: when sampling without replacement, the number of choices at each stage decreases, $P(n,k) = n(n-1)(n-2)\cdots(n-k+1)$ , whereas with-replacement counts give $n^{k}$ . Mixing these up turns birthday paradoxes into nonsense and inflates poker probabilities by orders of magnitude.

What you now know

You can pick the right counting tool by checking ordered-vs-unordered and disjoint-vs-overlapping, compute binomial coefficients via formula or Pascal's recurrence, expand binomial powers, and correct over-counts with inclusion-exclusion. The next section turns these counts into PROBABILITIES, ratios of favourable outcomes to total outcomes, and lays out the axioms that make those ratios behave consistently across compound events.

Mark section complete →

References

Garrity, T. (2002). All the Mathematics You Missed: But Need to Know for Graduate School. Cambridge University Press, ch. 15.

Ross, S. M. (2014). A First Course in Probability (9th ed.). Pearson, ch. 1.

Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. 1 (3rd ed.). Wiley, ch. 2.

Graham, R. L., Knuth, D. E., Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley, ch. 5.

Stanley, R. P. (2011). Enumerative Combinatorics, Vol. 1 (2nd ed.). Cambridge University Press, ch. 1.

This page is prerendered for SEO and accessibility. The interactive widgets above hydrate on JavaScript load.