Binomial Coefficients

definitions
discrete-math
counting

The numbers \(\binom{n}{r}\) count subsets, and they are also the coefficients that appear when \((a + b)^n\) is multiplied out, which is where the name binomial coefficient comes from. This note collects the identities they satisfy and the way each is proved by counting: the symmetry \(\binom{n}{r} = \binom{n}{n-r}\), Pascal’s formula and the triangle it builds, the Binomial Theorem, how to pick a single coefficient out of an expansion such as \((3x - 2)^5\), and why every row of Pascal’s triangle adds up to a power of 2. The definition and the formula \(\frac{n!}{r!\,(n-r)!}\) are in counting-selections. Using these counts to work out probabilities is in probability. First met in 2026-10-19-probability-binomial-coefficients.

\(n\) choose \(r\)

\(\binom{n}{r}\), read “\(n\) choose \(r\)”, is the number of \(r\)-element subsets of a set with \(n\) elements:

\[\binom{n}{r} = \frac{n!}{r!\,(n-r)!} = \frac{n(n-1)\cdots(n-r+1)}{r(r-1)\cdots 1}, \qquad 0 \le r \le n.\]

Why it divides by \(r!\), and how to calculate it without large factorials, is in counting-selections. Two values come up constantly: \(\binom{n}{0} = \binom{n}{n} = 1\) (one way to take nothing, one way to take everything) and \(\binom{n}{1} = n\).

Everything below rests on reading \(\binom{n}{r}\) as a count, not as a formula. Most identities about binomial coefficients can be proved by grinding through factorials, but each one is also the statement that two ways of counting the same collection agree, and that version explains why it is true.

Combinatorial proofs

A combinatorial proof of an identity \(\text{LHS} = \text{RHS}\) finds one collection of objects and counts it twice: once in a way that gives the left side, once in a way that gives the right side. Both counts are counts of the same thing, so they are equal. No algebra is needed. The work is in choosing the collection, and in checking that each count really counts every object exactly once.

There are two common shapes.

  • A pairing. Match the objects counted by the left side one-to-one with the objects counted by the right side. That is how the symmetry is proved: each subset is paired with its complement.
  • Splitting into cases. Count a collection directly for one side, and split it into disjoint cases, added up, for the other. That is how Pascal’s formula and the row sum are proved.

Symmetry: \(\binom{n}{r} = \binom{n}{n-r}\)

For \(0 \le r \le n\), \[\binom{n}{r} = \binom{n}{n-r}.\]

Why. Choosing which \(r\) elements of an \(n\)-element set go into a subset is the same act as choosing which \(n - r\) elements are left out. Every \(r\)-element subset \(A\) has a complement, the \(n - r\) elements not in \(A\), and every \((n - r)\)-element subset is the complement of exactly one \(r\)-element subset. So the subsets of the two sizes pair off exactly, and there are the same number of each.

Figure 1: The ten 2-element subsets of \({1, 2, 3, 4, 5}\), each joined to its complement, the three elements it leaves out. Every 2-element subset has exactly one complement, and every 3-element subset is the complement of exactly one 2-element subset, so the two lists pair off with nothing left over. That pairing is the proof that \(\binom52 = \binom53 = 10\), and the same pairing of each \(r\)-element subset with its complement proves \(\binom{n}{r} = \binom{n}{n-r}\).

Using it. Calculate whichever of the two has the smaller bottom number:

\[\binom{12}{8} = \binom{12}{4} = \frac{12 \cdot 11 \cdot 10 \cdot 9}{4 \cdot 3 \cdot 2 \cdot 1} = 495, \qquad \binom{7}{4} = \binom{7}{3} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35.\]

Dividing into two groups. The number of ways to split 400 students into a group of 150 and a group of 250 is \(\binom{400}{150}\): choose who goes in the group of 150, and the other 250 make up the second group. Choosing the group of 250 first gives \(\binom{400}{250}\), and the symmetry says these are the same number,

\[\binom{400}{150} = \binom{400}{250} = \frac{400!}{150!\,250!}.\]

It is about \(3.47 \times 10^{113}\), a 114-digit number, so the factorial form is the answer. Choosing one group settles the other, so there is a single binomial coefficient, not a product of two.

Pascal’s formula

Pascal’s formula. For integers \(n\) and \(r\) with \(1 \le r \le n\), \[\binom{n+1}{r} = \binom{n}{r-1} + \binom{n}{r}.\]

A case first. Take \(n = 8\) and \(r = 3\). The formula says

\[\binom93 = \binom82 + \binom83, \qquad 84 = 28 + 56.\]

The left side counts the 3-element subsets of \(\{1, 2, \dots, 9\}\). Split them according to whether they contain the largest element, 9.

  • Subsets that contain 9, such as \(\{1, 7, 9\}\). The 9 is already in, so the subset is decided by its other two elements, which are any two of \(1, \dots, 8\). Each such subset is \(\{9\}\) joined to a 2-element subset of \(\{1, \dots, 8\}\), and there are \(\binom82 = 28\) of them.
  • Subsets that do not contain 9, such as \(\{1, 7, 8\}\). All three elements come from \(1, \dots, 8\), so these are exactly the 3-element subsets of \(\{1, \dots, 8\}\): \(\binom83 = 56\) of them.

Every 3-element subset of \(\{1, \dots, 9\}\) is in exactly one of the two cases, so by the addition rule (counting-principles) \(\binom93 = \binom82 + \binom83\).

Figure 2: The combinatorial proof of Pascal’s formula with \(n = 8\) and \(r = 3\). The 3-element subsets of \({1, \dots, 9}\) either contain 9 or they don’t, never both. One that contains 9, like \({1, 7, 9}\), is decided by its other two elements, a 2-element subset of \({1, \dots, 8}\). One that doesn’t, like \({1, 7, 8}\), is a 3-element subset of \({1, \dots, 8}\). Counting the two cases and adding gives \(\binom93 = \binom82 + \binom83\).

The proof in general. Let \(1 \le r \le n\). The left side \(\binom{n+1}{r}\) counts the \(r\)-element subsets of \(\{1, 2, \dots, n+1\}\). Split them by whether they contain \(n + 1\).

  1. Those that contain \(n + 1\). Removing \(n + 1\) leaves an \((r-1)\)-element subset of \(\{1, \dots, n\}\), and adding \(n + 1\) to any \((r-1)\)-element subset of \(\{1, \dots, n\}\) gives one of these back. So there are \(\binom{n}{r-1}\) of them.
  2. Those that do not contain \(n + 1\). These are exactly the \(r\)-element subsets of \(\{1, \dots, n\}\), and there are \(\binom{n}{r}\) of them.

Every \(r\)-element subset of \(\{1, \dots, n+1\}\) falls in exactly one case, so \(\binom{n+1}{r} = \binom{n}{r-1} + \binom{n}{r}\). \(\square\)

The one idea to remember is fix one element and ask whether it is in or out. “In” uses up one of the \(r\) places, which is where the \(r - 1\) comes from. “Out” uses up none of the places but removes the element from the pool, which is where the \(n\) in place of \(n + 1\) comes from.

Algebraic check. The same identity follows from the factorial formula, by putting both terms over the common denominator \(r!\,(n-r+1)!\):

\[\binom{n}{r-1} + \binom{n}{r} = \frac{n!\, r}{r!\,(n-r+1)!} + \frac{n!\,(n-r+1)}{r!\,(n-r+1)!} = \frac{n!\,(n+1)}{r!\,(n+1-r)!} = \binom{n+1}{r}.\]

It is correct but says nothing about why the identity holds.

Pascal’s triangle

Write the binomial coefficients in rows, row \(n\) holding \(\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}\), centred under one another. The result is Pascal’s triangle. Each row starts and ends with 1, since \(\binom{n}{0} = \binom{n}{n} = 1\), and Pascal’s formula says that every other entry is the sum of the two entries diagonally above it. So the triangle can be built row by row with nothing but addition.

Figure 3: Pascal’s triangle, rows 0 to 9. The entry in row \(n\), position \(k\) (counting from 0 at the left) is \(\binom{n}{k}\). Each entry inside the triangle is the sum of the two above it, which is Pascal’s formula. Two additions are picked out: \(4 + 6 = 10\) is \(\binom41 + \binom42 = \binom52\), and \(28 + 56 = 84\) is \(\binom82 + \binom83 = \binom93\). Each row reads the same backwards as forwards, because \(\binom{n}{k} = \binom{n}{n-k}\), and the entries of row \(n\) add up to \(2^n\).

What to read off the triangle:

  • Row \(n\) is the list of coefficients of \((a + b)^n\) (below). Row 3 is \(1, 3, 3, 1\) and \((a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3\).
  • Each row is a palindrome: that is the symmetry.
  • Each row adds up to a power of 2: \(1 + 4 + 6 + 4 + 1 = 16 = 2^4\). That is the row sum.

Row 8, for reference, is \(1, 8, 28, 56, 70, 56, 28, 8, 1\).

\(a,b\)-sequences

A sequence of \(n\) terms, each of which is either \(a\) or \(b\), is an \(a,b\)-sequence of length \(n\). For example, \(aabab\) is an \(a,b\)-sequence of length 5.

There are \(2^n\) of them, since each of the \(n\) terms is one of 2 letters.

Why they matter. Multiply out \((a + b)^n = (a+b)(a+b)\cdots(a+b)\), \(n\) factors, without collecting like terms and without reordering the letters in each product. Each term of the result is made by picking one letter from each factor, in order, so each term is an \(a,b\)-sequence of length \(n\), and every \(a,b\)-sequence appears exactly once. So

\[(a + b)^n = \sum \bigl(\text{every } a,b\text{-sequence of length } n\bigr).\]

For \(n = 2\) and \(n = 3\):

\[\begin{aligned} (a+b)^2 &= (a+b)(a+b) = aa + ab + ba + bb, \\ (a+b)^3 &= (aa + ab + ba + bb)(a + b) \\ &= aaa + aba + baa + bba + aab + abb + bab + bbb. \end{aligned}\]

Since the letters are numbers, they commute, and a sequence is the same as the product of its letters: \(aba = baa = aab = a^2b\), and \(aabab = a^3b^2\). In general, an \(a,b\)-sequence of length \(n\) with \(k\) copies of \(b\) equals \(a^{n-k}b^k\). Collecting like terms is then counting sequences by how many \(b\)’s they have.

Figure 4: Multiplying out \((a+b)^3\) one factor at a time. Each factor contributes either \(a\) or \(b\), so every path from the left to a leaf is one \(a,b\)-sequence of length 3, and the eight leaves are all eight of them. The colour of a leaf is its number of \(b\)’s, and a sequence with \(k\) \(b\)’s equals \(a^{3-k}b^k\). There is 1 sequence with no \(b\), 3 with one, 3 with two and 1 with three, which are the numbers of ways to choose where the \(b\)’s go: \(\binom30, \binom31, \binom32, \binom33\). Collecting them gives \((a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3\).

The Binomial Theorem

The Binomial Theorem. For any \(a, b \in \mathbb{R}\) and any nonnegative integer \(n\), \[(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k = a^n + \binom{n}{1} a^{n-1}b^1 + \cdots + \binom{n}{n-1} a^1 b^{n-1} + b^n.\]

The statement is printed on the exam formula-sheet; the proof is not.

Combinatorial proof. \((a+b)^n\) is the sum of all the \(a,b\)-sequences of length \(n\) (above). Group them by their number of \(b\)’s.

  1. A sequence with exactly \(k\) \(b\)’s has \(n - k\) \(a\)’s, so it equals \(a^{n-k}b^k\).
  2. How many sequences of length \(n\) have exactly \(k\) \(b\)’s? Such a sequence is fixed by choosing which \(k\) of its \(n\) positions hold a \(b\); the rest hold \(a\). So there are \(\binom{n}{k}\) of them.
  3. So the term \(a^{n-k}b^k\) appears \(\binom{n}{k}\) times, and \(k\) can be anything from 0 to \(n\). Adding up gives \((a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k}b^k\). \(\square\)

The end terms fit the pattern: \(a^n\) is the single sequence with no \(b\)’s, coefficient \(\binom{n}{0} = 1\), and \(b^n\) is the single sequence of all \(b\)’s, coefficient \(\binom{n}{n} = 1\).

An example to hold onto: \((a+b)^5\) and \(a^3b^2\). The sequences of length 5 with three \(a\)’s and two \(b\)’s are

\[aaabb,\ aabab,\ aabba,\ abaab,\ ababa,\ abbaa,\ baaab,\ baaba,\ babaa,\ bbaaa,\]

ten of them, so the expansion of \((a+b)^5\) contains \(10a^3b^2\). Ten is \(\binom52\), the number of ways to choose the 2 positions for the \(b\)’s out of 5. Choosing the 3 positions for the \(a\)’s instead gives \(\binom53\), which is also 10: placing the \(a\)’s settles where the \(b\)’s go, and that is the symmetry again. The full expansion is

\[(a+b)^5 = a^5 + 5a^4b + 10a^3b^2 + 10a^2b^3 + 5ab^4 + b^5,\]

with row 5 of Pascal’s triangle as its coefficients.

Figure 5: The ten \(a,b\)-sequences of length 5 with two \(b\)’s, each drawn as five positions with the two \(b\)’s shaded. A sequence is decided by which two positions hold its \(b\)’s, and every pair of positions from \({1, \dots, 5}\) appears exactly once, so there are \(\binom52 = 10\) sequences, each equal to \(a^3b^2\), and \((a+b)^5\) contains \(10a^3b^2\). The pairs are the ten 2-element subsets of \({1, 2, 3, 4, 5}\), and the \(a\)’s sit in the complementary 3 positions, so choosing the \(a\)-positions instead counts the same ten sequences as \(\binom53\).

Another way to see step 2. Multiplying out the product means choosing, from each of the \(n\) factors \((a + b)\), either its \(a\) or its \(b\). A term equal to \(a^{n-k}b^k\) comes from choosing \(b\) from some \(k\) of the factors and \(a\) from the rest, and there are \(\binom{n}{k}\) ways to choose which \(k\) factors. The positions in the sequence and the factors in the product are the same thing.

Finding a coefficient in an expansion

To find the coefficient of one power of \(x\) in something like \((3x - 2)^5\), don’t expand the whole thing. Find the one term of the Binomial Theorem that contains that power.

  1. Match to \((a + b)^n\), signs and constants included. In \((3x - 2)^5\), \(a = 3x\), \(b = -2\) and \(n = 5\). The minus sign belongs to \(b\), and the 3 belongs to \(a\).
  2. Write the general term \(\binom{n}{k} a^{n-k} b^k\) with these substituted: \(\binom5k (3x)^{5-k}(-2)^k\).
  3. Find \(k\). Work out the power of \(x\) in the general term as a function of \(k\), set it equal to the power wanted, and solve. Here \(x\) is inside \(a\), so it is raised to \(5 - k\). For \(x^2\), \(5 - k = 2\), so \(k = 3\).
  4. Substitute \(k\) and simplify, keeping the constants and the sign. \(\binom53 (3x)^2 (-2)^3 = 10 \cdot 9x^2 \cdot (-8) = -720x^2\). The coefficient is \(-720\).

The question “what should \(k\) be?” always has the same answer: whatever makes the power of \(x\) come out right. Where \(x\) sits decides the equation.

  • \(x\) in the first term, \(a\). Its power is \(n - k\). So for \(x^3\) in \((x + 9)^7\), \(7 - k = 3\) and \(k = 4\).
  • \(x\) in the second term, \(b\). Its power is \(k\). So for \(x^8\) in \((3 - x)^{12}\), \(a = 3\), \(b = -x\) and \(k = 8\) directly.
  • \(x\) in both terms. Collect the powers. In \(\left(x^2 + \frac{1}{x}\right)^5\) the general term is \(\binom5k (x^2)^{5-k} (x^{-1})^k = \binom5k x^{10 - 3k}\). For \(x^4\), \(10 - 3k = 4\) gives \(k = 2\), and the coefficient is \(\binom52 = 10\). For \(x^5\), \(10 - 3k = 5\) has no whole-number solution, so there is no \(x^5\) term and its coefficient is 0.

Which letter is called \(a\) and which \(b\) is a free choice. Swapping them changes \(k\) to \(n - k\), and \(\binom{n}{k} = \binom{n}{n-k}\), so the answer is the same either way. What must stay consistent is that the power \(n - k\) goes on whatever was called \(a\) and the power \(k\) on whatever was called \(b\).

Expansion \(a\) \(b\) Power of \(x\) in the general term Wanted \(k\) Term Coefficient
\((x + 9)^7\) \(x\) \(9\) \(7 - k\) \(x^3\) 4 \(\binom74 x^3 9^4\) \(35 \cdot 6561 = 229\,635\)
\((3 - x)^{12}\) \(3\) \(-x\) \(k\) \(x^8\) 8 \(\binom{12}{8} 3^4 (-x)^8\) \(495 \cdot 81 = 40\,095\)
\((3x - 2)^5\) \(3x\) \(-2\) \(5 - k\) \(x^2\) 3 \(\binom53 (3x)^2 (-2)^3\) \(10 \cdot 9 \cdot (-8) = -720\)

These three are worked in full in 2026-10-19-probability-binomial-coefficients.

Signs. With \(b = -c\), the general term carries \((-1)^k\). It is positive when \(k\) is even and negative when \(k\) is odd. In \((3 - x)^{12}\), \((-x)^8 = x^8\), so the \(x^8\) coefficient is positive. In \((3x - 2)^5\), \((-2)^3 = -8\), so the \(x^2\) coefficient is negative.

Scaled terms. \((3x)^2 = 9x^2\), not \(3x^2\). The constant inside the bracket is raised to the power too.

The sum of a row: \(\sum_{r=0}^{n} \binom{n}{r} = 2^n\)

For every nonnegative integer \(n\), \[\sum_{r=0}^{n} \binom{n}{r} = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n.\]

Combinatorial proof. Count the subsets of \(N = \{1, 2, \dots, n\}\) in two ways.

  • All at once. The number of subsets of \(N\) is the size of its power set, \(|\mathcal{P}(N)| = 2^{|N|} = 2^n\) (sets-and-set-notation). To see why, write each subset as a 01-sequence of length \(n\): put a 1 in position \(i\) if \(i\) is in the subset and a 0 if it isn’t. For \(N = \{1, \dots, 6\}\), the sequence \(011001\) is the subset \(\{2, 3, 6\}\). Every subset gives one 01-sequence and every 01-sequence gives one subset, and there are \(2^n\) 01-sequences of length \(n\), since each position is 0 or 1.
  • By size. Every subset has some cardinality \(k\) between 0 and \(n\), and the subsets of cardinality \(k\) are the 01-sequences with exactly \(k\) ones. Such a sequence is fixed by choosing which \(k\) positions hold the ones, so there are \(\binom{n}{k}\) of them. Adding over all sizes, the number of subsets is \(\sum_{k=0}^{n} \binom{n}{k}\).

Both count the subsets of \(N\), so \(2^n = \sum_{r=0}^{n} \binom{n}{r}\). \(\square\)

Figure 6: The eight subsets of \({1, 2, 3}\), each written as a 01-sequence, where a 1 in position \(i\) means \(i\) is in the subset. Grouped by size there are \(\binom30 = 1\) with no elements, \(\binom31 = 3\) with one, \(\binom32 = 3\) with two and \(\binom33 = 1\) with three: a subset of size \(k\) is a choice of \(k\) positions for the 1s. Counted all at once there are \(2^3 = 8\), two choices for each position. So row 3 of Pascal’s triangle adds up to \(2^3\).

A check from the Binomial Theorem. Put \(a = b = 1\): \((1 + 1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k\), which is the same identity. With \(a = 1\) and \(b = -1\) instead, \(0 = (1 - 1)^n = \sum_{k=0}^{n} (-1)^k \binom{n}{k}\) for \(n \ge 1\): the alternating sum of a row is 0, as in \(1 - 4 + 6 - 4 + 1 = 0\). That alternating sum is what makes inclusion-exclusion count every element exactly once.

Common mistakes

  • Leaving the constant behind. In \((3x - 2)^5\) the term is \(\binom53 (3x)^2(-2)^3\), and \((3x)^2 = 9x^2\). Writing \(3x^2\) gives \(-240\) in place of \(-720\).
  • Dropping the sign. The \(-\) belongs to \(b\), so it is raised to the power \(k\): \((-2)^3 = -8\) but \((-x)^8 = +x^8\). Forgetting it gives \(+720\) for the \(x^2\) coefficient of \((3x - 2)^5\).
  • Putting \(k\) on the wrong letter. When \(x\) is in \(a\), its power is \(n - k\), not \(k\). In \((x + 9)^7\), solving \(k = 3\) and then writing \(\binom73 x^4 9^3\) finds the \(x^4\) coefficient, not the \(x^3\) one. The binomial \(\binom73 = \binom74\) is the same either way; the powers on \(a\) and \(b\) are what go wrong.
  • Expecting every power to appear. In \(\left(x^2 + \frac1x\right)^5\) the powers are \(x^{10 - 3k}\), so \(x^5\) never appears and its coefficient is 0. A \(k\) that is not a whole number between 0 and \(n\) means the term isn’t there.
  • Pascal’s formula with the wrong indices. It is \(\binom{n+1}{r} = \binom{n}{r-1} + \binom{n}{r}\): the two entries diagonally above, both from row \(n\). Not \(\binom{n}{r} + \binom{n}{r+1}\) in row \(n+1\), and not two entries from different rows.
  • Treating two groups as a product. Splitting 400 people into groups of 150 and 250 is \(\binom{400}{150}\), not \(\binom{400}{150}\binom{400}{250}\): once the 150 are chosen the other group is already decided. (If it were written as stages, the second stage would be \(\binom{250}{250} = 1\).)
  • A combinatorial proof that only computes. Showing \(84 = 28 + 56\) checks one case. The proof has to say what is being counted and why each side counts it.

See also