Permutations, combinations and Pascal’s triangle

Two rules everything is built on

The product rule. If a task is done in two stages, with $m$ ways to do the first and, for each of them, $n$ ways to do the second, there are $m \times n$ ways overall. A shirt (5 choices) and trousers (3 choices) make $15$ outfits.

The sum rule. If a task can be done in one of two ways that don’t overlap, with $m$ options for the first and $n$ for the second, there are $m + n$ options. If the ways do overlap, subtract the overlap: $|A \cup B| = |A| + |B| - |A \cap B|$. That correction, extended to more sets, is the inclusion–exclusion principle.

The four basic counts

Choose $k$ items from $n$ distinct ones.

Order matters, no repetition: permutations

For the first position there are $n$ choices, then $n - 1$, down to $n - k + 1$. By the product rule that is $n(n-1)\cdots(n-k+1) = n!/(n-k)!$. Arranging all $n$ items is the special case $k = n$: $n!$ orderings. Gold, silver and bronze among 8 finalists: $8 \cdot 7 \cdot 6$ = 336 podiums.

Order doesn’t matter, no repetition: combinations

Each unordered selection of $k$ items can be put in order in $k!$ ways, so every combination is counted $k!$ times among the permutations. Divide it out: $\binom{n}{k} = P(n,k)/k!$. A committee of 3 from 10 people: $720 / 6$ = 120. A five-card poker hand from a 52-card deck: $\binom{52}{5}$ = 2,598,960.

Order matters, repetition allowed: sequences

Each of the $k$ positions independently takes any of $n$ values: $n^k$. Eight-letter lowercase passwords: $26^8$ = 208,827,064,576. Binary strings of length $k$: $2^k$.

Order doesn’t matter, repetition allowed: multisets

Four scoops of ice cream from 3 flavours, where only how many of each flavour counts. The trick, called stars and bars, is to write a selection as $k$ stars (the scoops) separated by $n - 1$ bars (the boundaries between flavours): ★★|★|★ means two of the first flavour, one of the second, one of the third. Every arrangement of $k$ stars and $n - 1$ bars is one selection, so the count is $\binom{k + n - 1}{k}$. For the ice cream, $\binom{6}{4}$ = 15.

Pascal’s triangle

Write the binomial coefficients in rows, row $n$ holding $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$. Each entry is the sum of the two above it:

There is a one-line counting proof. Fix one particular item. A $k$-element selection either includes it, and then the other $k-1$ come from the remaining $n - 1$ items, or it doesn’t, and then all $k$ come from the remaining $n - 1$. The two cases don’t overlap, so the sum rule gives the identity. Click any entry below to see it applied.

A few patterns to look for in the triangle:

• Row sums are powers of 2. $\sum_k \binom{n}{k} = 2^n$, because both sides count the subsets of an $n$-element set.
• Symmetry. $\binom{n}{k} = \binom{n}{n-k}$: choosing which $k$ to take is the same as choosing which $n - k$ to leave.
• The binomial theorem. Row $n$ holds the coefficients of $(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k}$. Row 4 is 1, 4, 6, 4, 1, and $(x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$.
• Odd entries form a fractal. Turn on “Colour the odd numbers” and add rows: the pattern is Sierpiński’s triangle.

Counting in computer science

Counting is how you size a search space before deciding how to search it. There are $2^n$ subsets of $n$ items, $n!$ orderings, and $\binom{n}{2} = n(n-1)/2$ pairs, which is exactly the number of comparisons a naive “compare every pair” loop makes. The $n!$ orderings also give the $\Omega(n \log n)$ lower bound for comparison sorting explained on the sorting page. And because $\binom{n}{k}$ appears in probability, “how likely is this hash collision?” and “how many test cases cover every pair of options?” are counting questions too.

References

1. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. Chapter 5 is about binomial coefficients.
2. K. H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019. Chapter 6.
3. “Stars and bars (combinatorics)”, Wikipedia.