Counting & the Binomial Theorem

Counting: the multiplication principle

Before we get to $(a+b)^n$, we need to count. The fundamental tool:

Multiplication Principle. If a task has $m$ steps, step $i$ can be done in $n_i$ ways (independently), then the total number of ways is $n_1 \cdot n_2 \cdots n_m$.

Example: create a 3-character code using 26 letters for each character. Total codes: $26 \times 26 \times 26 = 26^3 = 17576$. This is the whole principle. It sounds almost embarrassingly simple because it is — the power comes from applying it systematically, not from the principle itself being mysterious.

Permutations

A permutation is an ordered selection. The number of ways to arrange $k$ objects chosen from $n$ distinct objects (order matters):

$P(n,k) = \frac{n!}{(n-k)!} = n(n-1)(n-2)\cdots(n-k+1).$

Why? First choice: $n$ options. Second choice: $n-1$ (one used). $\ldots$ $k$th choice: $n-k+1$. Multiply: $n(n-1)\cdots(n-k+1) = n!/(n-k)!$.

Recall $0! = 1$ (the empty product convention, consistent with $P(n,0) = 1$: there's exactly one way to select nothing).

Combinations: order-blind counting

A combination is an unordered selection. The number of ways to choose $k$ objects from $n$ distinct objects (order does NOT matter):

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

Why? Every combination of $k$ objects can be arranged in $k!$ different orders. So: $\underbrace{P(n,k)}_{\text{ordered}} = \underbrace{\binom{n}{k}}_{\text{unordered}} \times \underbrace{k!}_{\text{rearrangements}}.$ Solve: $\binom{n}{k} = P(n,k)/k! = n!/[k!(n-k)!]$.

This is "n choose k" — the number of $k$-element subsets of an $n$-element set. You computed this in the Sets stratum when counting power sets; you just didn't have a name for it. You've been doing combinatorics this whole time. Surprise.

Pascal's triangle and the key identity

Arrange the combinations: $\binom{0}{0}$ $\binom{1}{0} \quad \binom{1}{1}$ $\binom{2}{0} \quad \binom{2}{1} \quad \binom{2}{2}$ $\binom{3}{0} \quad \binom{3}{1} \quad \binom{3}{2} \quad \binom{3}{3}$

which evaluates to: $1$ $1 \quad 1$ $1 \quad 2 \quad 1$ $1 \quad 3 \quad 3 \quad 1$

This is Pascal's triangle. The key identity that generates it:

$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}.$

Proof via committee argument. The right side counts $(k+1)$-element subsets of $\{1, 2, \ldots, n+1\}$. Split into two types based on whether element $n+1$ is included:

• Subsets INCLUDING $n+1$: choose the remaining $k$ elements from $\{1,\ldots,n\}$ — that's $\binom{n}{k}$ ways.
• Subsets EXCLUDING $n+1$: choose all $k+1$ elements from $\{1,\ldots,n\}$ — that's $\binom{n}{k+1}$ ways.

These two cases are mutually exclusive and exhaustive, so their sum equals the total: $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}. \quad \square$

This is the purely combinatorial proof, with no algebra at all.

The Binomial Theorem: where it comes from

Theorem. For any $n \ge 0$: $\boxed{(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k.}$

Why the coefficients are binomial. When you expand $(a+b)^n = (a+b)(a+b)\cdots(a+b)$ ($n$ factors), you get a sum of $2^n$ terms (each factor contributes either $a$ or $b$). Each term is a product of exactly $n$ letters — some $a$'s and some $b$'s. A term that has exactly $k$ $b$'s (and hence $n-k$ $a$'s) contributes $a^{n-k}b^k$.

How many such terms are there? Exactly the number of ways to choose WHICH $k$ of the $n$ factors contributed a $b$ — which is $\binom{n}{k}$.

So the coefficient of $a^{n-k}b^k$ is exactly $\binom{n}{k}$. Not a coincidence, not a pattern someone scribbled in a triangle four hundred years ago: it counts choices. Every coefficient in the expansion is literally a count of subsets. That's the binomial theorem — and now you will never again be confused about where those coefficients come from, because you know the argument. You magnificent idiot, you've got it.

Small cases to ground it.

$n = 2$: $(a+b)^2 = \binom{2}{0}a^2 + \binom{2}{1}ab + \binom{2}{2}b^2 = a^2 + 2ab + b^2$. You knew this.

$n = 3$: $(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$. Row 3 of Pascal's triangle: $1, 3, 3, 1$.

Connection: row sums and power sets

Set $a = b = 1$ in the binomial theorem: $2^n = (1+1)^n = \sum_{k=0}^{n}\binom{n}{k}.$

The sum of row $n$ of Pascal's triangle is $2^n$.

But wait — this is the same result from the Sets stratum: a set with $n$ elements has $2^n$ subsets, because $\binom{n}{k}$ is the number of $k$-element subsets and all subsets have size $0, 1, \ldots, n$. The binomial theorem is the Sets result in algebraic clothing.

The Sets stratum built the room; the Binomial Theorem is what's written on the wall. When you see this kind of convergence — two apparently different arguments arriving at the same fact — that is not an accident. That is mathematics doing exactly what it's supposed to do, and it should give you a feeling somewhere between vertigo and genuine joy.