Binomial Coefficients

nk counts k-subsets — symmetry, Pascal's recursion, row sums = 2^n.

The idea

Definition (Binomial coefficient).

For integers $n \ge 0$ and $k$, the binomial coefficient $\binom{n}{k}$, read $n$ choose $k$, is the number of $k$-element subsets of an $n$-element set — the number of ways to choose $k$ objects from $n$ when order is ignored. For $0 \le k \le n$ it has the closed form $\binom{n}{k} = \frac{n!}{k!\,(n-k)!},$ and it is $0$ when $k$ is negative or larger than $n$, since there are no such subsets.

The coefficient answers questions where a selection matters but its arrangement does not: a committee of three chosen from ten people is the same committee in any order.

The name comes from the binomial theorem. Multiply out $(a+b)^{n}$: each term arises by picking $a$ or $b$ from each of the $n$ factors, so the term $a^{k}b^{n-k}$ appears once for each choice of which $k$ factors contribute an $a$. Its coefficient is therefore $\binom{n}{k}$.

Arranged in rows by $n$, the coefficients form Pascal's triangle: each entry is the sum of the two entries above it, and each row reads the same left to right as right to left.

Ways to work on it

• Walkthrough. What nk counts, plus symmetry, Pascal's recursion, and _k nk = 2^n.
• Proof. Derive the closed form nk = n!/(k! (n-k)!) by counting twice.
• Practice. Compute nk for small n, k.
• Hardest. Evaluate a count or a sum by choosing the right binomial-coefficient identity.

Not sure where to start? Take the ten-question placement test.