Lecture 31 — Probability, Binomial Coefficients
Probability as a ratio of two counts when the outcomes are equally likely, and the identities that binomial coefficients satisfy: the symmetry \(\binom{n}{r} = \binom{n}{n-r}\), Pascal’s formula, the Binomial Theorem, and the sum of a row of Pascal’s triangle. Pre-work: Video 039 (Introduction to Probability) and Video 040 (Binomial Coefficients). Sample spaces, events, the formula \(P(E) = \frac{|E|}{|S|}\) and the complement are collected in probability. The identities, their combinatorial proofs, Pascal’s triangle and the method for picking a coefficient out of an expansion are in binomial-coefficients. The note starts by finishing the BARBARA question from 2026-10-13-counting-selections.
Goals
- Learn how to calculate probabilities by counting when there are equally likely outcomes.
- Gain a better understanding of the combinatorial proofs of Pascal’s formula and the Binomial Theorem.
- Learn how to evaluate coefficients in binomial expansions.
- Gain confidence with solving counting problems.
Three questions to keep in mind:
- To find a coefficient in an expansion, how do you work out what \(k\) should be? Finding \(k\): set the power of \(x\) in the general term equal to the power wanted.
- Why is Pascal’s formula true? Its combinatorial proof, which splits subsets by whether they contain one particular element.
- Why is the Binomial Theorem true? Its combinatorial proof, which counts \(a,b\)-sequences by their number of \(b\)’s.
Finishing BARBARA
How many distinct arrangements of the letters in the word BARBARA are there?
The full working is in 2026-10-13-counting-selections. In short: tag the copies so every letter is different, \(\mathrm{B}_1\mathrm{B}_2\), \(\mathrm{A}_1\mathrm{A}_2\mathrm{A}_3\), \(\mathrm{R}_1\mathrm{R}_2\), and there are \(7!\) arrangements of the 7 tagged letters. Removing the tags merges arrangements that differ only in how the copies of each letter are ordered among themselves: \(2!\) orders for the B’s, \(3! = 6\) for the A’s (\(\mathrm{A}_1\mathrm{A}_2\mathrm{A}_3\), \(\mathrm{A}_1\mathrm{A}_3\mathrm{A}_2\), \(\mathrm{A}_2\mathrm{A}_1\mathrm{A}_3\), \(\mathrm{A}_2\mathrm{A}_3\mathrm{A}_1\), \(\mathrm{A}_3\mathrm{A}_1\mathrm{A}_2\), \(\mathrm{A}_3\mathrm{A}_2\mathrm{A}_1\), all giving the same word) and \(2!\) for the R’s. So
\[\#(\text{arrangements}) = \frac{7!}{2!\,3!\,2!} = \frac{\text{(total number of letters)}!}{(\#\text{B's})!\,(\#\text{A's})!\,(\#\text{R's})!} = \frac{5040}{24} = 210.\]
Worked: a committee with at least one mathematician
If a committee of 5 is chosen at random from a group of 25 mathematicians and 25 physicists, what is the probability that at least one mathematician will be chosen?
Answer: \(\frac{1283}{1316} \approx 97.5\%\).
A committee is an unordered selection of 5 from the 50 people, and every committee is equally likely. Let
- \(T\) = the total number of ways to choose 5 people \(= \binom{50}{5} = 2\,118\,760\),
- \(N\) = the number of choices with no mathematicians \(= \binom{25}{5} = 53\,130\), all five chosen from the 25 physicists.
“At least one mathematician” is five cases (1 to 5 mathematicians), but its complement, “no mathematicians”, is one. So count the complement and subtract:
\[\begin{aligned} P(\text{at least one mathematician}) &= \frac{\#(\text{choices with} \ge 1 \text{ mathematician})}{\text{total number of choices}} = \frac{T - N}{T} = 1 - \frac{N}{T} \\ &= 1 - \frac{\binom{25}{5}}{\binom{50}{5}} = 1 - \frac{53\,130}{2\,118\,760} = 1 - \frac{33}{1316} = \frac{1283}{1316} \approx 97.5\% \text{ (to 1 dp)}. \end{aligned}\]
The fraction \(\frac{N}{T} \approx 2.5\%\) is the probability of no mathematicians; it is the quantity being subtracted, not the answer. The sample space split into the two events is drawn in probability.
Figure 1: All committees of 5, sorted by how many mathematicians they contain. With \(k\) mathematicians there are \(\binom{25}{k}\) ways to pick them and \(\binom{25}{5-k}\) ways to pick the \(5-k\) physicists. The event wanted, at least one mathematician, is the five rows \(k = 1, \dots, 5\); its complement is the single row \(k = 0\). The six rows together are every committee, so the five-row sum is the total minus the one row: \(2,118,760 - 53,130 = 2,065,630\).
Worked: 5 not next to 6
What is the probability that a randomly chosen permutation of \(\{1, 2, \dots, 9\}\) has 5 not next to 6?
Answer: \(\frac79 \approx 77.8\%\).
A permutation is ordered with no repeats. Let
- \(T\) = the total number of permutations \(= 9!\),
- \(A\) = the number of permutations containing “56” \(= 8!\).
To count \(A\), glue 5 and 6 into a single tile “56”. Then there are 8 objects to arrange, the tile and the other 7 numbers, so \(8!\) arrangements. Equivalently, the tile can start in any of 8 positions (1 to 8), and the other seven numbers fill the remaining positions in \(7!\) ways: \(8 \cdot 7! = 8!\). By the same argument there are \(8!\) permutations containing “65”. “5 next to 6” means “56” or “65”, which cannot both happen, so \(2A = 2 \cdot 8!\) permutations have 5 next to 6. Then
\[P(\text{5 not next to 6}) = \frac{T - 2A}{T} = \frac{9! - 2 \cdot 8!}{9!} = \frac{9 \cdot 8! - 2 \cdot 8!}{9 \cdot 8!} = \frac{9 - 2}{9} = \frac79 = 0.\dot{7} \approx 77.8\% \text{ (to 1 dp)}.\]
The tile is drawn, and the answer checked a second way, in probability. The factor of 2 is the easy thing to lose: without the “65” permutations the answer would come out as \(\frac89\).
Figure 2: Counting the permutations of \(1, \dots, 9\) that contain 56 by where the pair sits. The tile 56 covers two neighbouring places out of nine, and its left end can be at any of places 1 to 8, so there are 8 positions for it. Whichever is used, the other seven numbers fill the seven empty places in \(7!\) orders. That gives \(8 \cdot 7! = 8!\) permutations with 5 immediately before 6, and another \(8!\) with 6 immediately before 5.
Worked: dividing 400 students into two groups
How many ways are there to divide 400 students into a group of 150 and a group of 250?
Answer: \(\dbinom{400}{150} = \dbinom{400}{250} = \dfrac{400!}{150!\,250!}\), about \(3.47 \times 10^{113}\).
Choose which 150 students go in the first group: \(\binom{400}{150}\) ways. The 250 left over are the second group, with no further choice, so that is the whole count. Choosing the group of 250 first instead gives \(\binom{400}{250}\) ways, and it must be the same number, since it counts the same divisions. Both equal \(\frac{400!}{150!\,250!}\).
Because the groups have different sizes, a division is fixed by saying who is in the group of 150. There is nothing to multiply by for the second group, and nothing to divide by either.
The general fact. For \(0 \le r \le n\),
\[\binom{n}{r} = \binom{n}{n-r},\]
because the number of ways of choosing an \(r\)-element subset of an \(n\)-element set equals the number of ways of choosing the \(n - r\) elements that are not in the subset. Each subset is paired with its complement. For \(n = 5\), \(r = 2\) the pairing is
\[\begin{aligned} &\{1,2\} \leftrightarrow \{3,4,5\}, \quad \{1,3\} \leftrightarrow \{2,4,5\}, \quad \{1,4\} \leftrightarrow \{2,3,5\}, \quad \{1,5\} \leftrightarrow \{2,3,4\}, \quad \{2,3\} \leftrightarrow \{1,4,5\}, \\ &\{2,4\} \leftrightarrow \{1,3,5\}, \quad \{2,5\} \leftrightarrow \{1,3,4\}, \quad \{3,4\} \leftrightarrow \{1,2,5\}, \quad \{3,5\} \leftrightarrow \{1,2,4\}, \quad \{4,5\} \leftrightarrow \{1,2,3\}, \end{aligned}\]
so \(\binom52 = \binom53 = 10\). See binomial-coefficients.
Pascal’s formula
Pascal’s formula. For integers \(1 \le r \le n\), \[\binom{n+1}{r} = \binom{n}{r-1} + \binom{n}{r}.\]
With \(n = 8\) and \(r = 3\) it says \(\binom93 = \binom82 + \binom83\), that is, \(84 = 28 + 56\).
Why it is true. \(\binom93\) is the number of 3-element subsets of \(\{1, 2, \dots, 9\}\). Pick out one element, 9, and sort the subsets by whether they contain it.
- The subsets that contain 9, like \(\{1, 7, 9\}\). With 9 already in, the subset is decided by its other two elements, which can be any two of \(1, \dots, 8\). So these subsets are \(\{9\}\) joined to a 2-element subset of \(\{1, \dots, 8\}\), and there are \(\binom82 = 28\) of them.
- The subsets that do not contain 9, like \(\{1, 7, 8\}\). All three elements come from \(\{1, \dots, 8\}\), so these are just the 3-element subsets of \(\{1, \dots, 8\}\), and there are \(\binom83 = 56\).
Every 3-element subset of \(\{1, \dots, 9\}\) is in exactly one of the two groups, so \(\binom93 = \binom82 + \binom83\). Nothing here depended on the numbers 8 and 3. In general, sort the \(r\)-element subsets of \(\{1, \dots, n+1\}\) by whether they contain \(n + 1\). Those that do are \(\{n+1\}\) joined to an \((r-1)\)-element subset of \(\{1, \dots, n\}\), \(\binom{n}{r-1}\) of them, and those that don’t are \(r\)-element subsets of \(\{1, \dots, n\}\), \(\binom{n}{r}\) of them. That is the whole proof: one side counts a collection directly, the other counts it in two disjoint pieces. It is drawn, with the general proof written out, in binomial-coefficients.
Pascal’s triangle. Writing \(\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}\) as row \(n\) and centring the rows gives
\[\begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1 \\ 1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1 \\ 1 \quad 7 \quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad 1 \\ 1 \quad 8 \quad 28 \quad 56 \quad 70 \quad 56 \quad 28 \quad 8 \quad 1 \end{array}\]
The top row is \(\binom00\), the next is \(\binom10, \binom11\), and so on down to row 8. Pascal’s formula is the rule that builds it: each entry inside the triangle is the sum of the two above it. For example \(4 + 6 = 10\) is \(\binom41 + \binom42 = \binom52\). Each row also reads the same in both directions, which is the symmetry \(\binom{n}{r} = \binom{n}{n-r}\). The triangle is drawn with these additions picked out in binomial-coefficients.
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.\]
\(a,b\)-sequences. A sequence of \(n\) terms, each either \(a\) or \(b\), is an \(a,b\)-sequence of length \(n\); \(aabab\) is one of length 5. Expanding
\[(a+b)^n = \underbrace{(a+b)(a+b)\cdots(a+b)}_{n \text{ factors}}\]
without collecting terms means choosing \(a\) or \(b\) from each factor in turn and writing the choices down in order. So the expansion of \((a+b)^n\) is the sum of every \(a,b\)-sequence of length \(n\):
\[\begin{aligned} (a+b)^2 &= (a+b)(a+b) = aa + ab + ba + bb, \\ (a+b)^3 &= (a+b)(a+b)(a+b) = (aa + ab + ba + bb)(a+b) \\ &= aaa + aba + baa + bba + aab + abb + bab + bbb. \end{aligned}\]
Why it is true. Collect the sequences by their number of \(b\)’s.
- Each sequence is a monomial. An \(a,b\)-sequence of length \(n\) with \(k\) occurrences of \(b\) has \(n - k\) occurrences of \(a\), so it equals \(a^{n-k}b^k\). For example \(aabab = a^3b^2\), and in \((a+b)^3\) the three sequences \(aba\), \(baa\), \(aab\) each equal \(a^2b\), which gives the term \(3a^2b\).
- Counting them. A sequence of length \(n\) with \(k\) \(b\)’s is decided by which \(k\) of the \(n\) positions hold the \(b\)’s. There are \(\binom{n}{k}\) choices of where to put the \(b\)’s, so \(\binom{n}{k}\) such sequences.
- Adding up. The term \(a^{n-k}b^k\) therefore appears \(\binom{n}{k}\) times, for each \(k\) from 0 to \(n\), which is the theorem. At the ends, \(a^n\) (no \(b\)’s) has coefficient \(\binom{n}{0} = 1\) and \(b^n\) (all \(b\)’s) has coefficient \(\binom{n}{n} = 1\).
For example, the terms of \((a+b)^5\) with three \(a\)’s and two \(b\)’s are the ten sequences
\[aaabb + aabab + aabba + abaab + ababa + abbaa + baaab + baaba + babaa + bbaaa = 10a^3b^2,\]
and \(10 = \binom52\), the number of ways to choose where the two \(b\)’s go among the five positions. Choosing where the three \(a\)’s go, as in \(\boxed{a}\,\boxed{a}\,\boxed{\phantom{a}}\,\boxed{a}\,\boxed{\phantom{a}}\), gives \(\binom53\), and \(\binom53 = \binom52 = 10\), so it doesn’t matter which letter’s positions are chosen.
Figure 3: Where the coefficient of \(a^3b^2\) in \((a+b)^5\) comes from. Expanding the product means picking one letter from each of the five factors, and the result is the \(a,b\)-sequence of the picks. Picking \(b\) from factors 3 and 5 and \(a\) from the rest gives \(aabab\); picking \(b\) from factors 1 and 4 gives \(baaba\). Both equal \(a^3b^2\). Every way of choosing which 2 of the 5 factors supply a \(b\) gives one more copy of \(a^3b^2\), so the coefficient is \(\binom52 = 10\).
The full proof, with the \(a,b\)-sequences of length 3 drawn as a tree and all ten of these length-5 sequences drawn as choices of positions for the \(b\)’s, is in binomial-coefficients.
Worked: coefficients in binomial expansions
- What is the coefficient of \(x^3\) in the expansion of \((x + 9)^7\)?
- What is the coefficient of \(x^8\) in the expansion of \((3 - x)^{12}\)?
- What is the coefficient of \(x^2\) in the expansion of \((3x - 2)^5\)?
Answers: (1) \(229\,635\), (2) \(40\,095\), (3) \(-720\).
Each uses the Binomial Theorem, \((a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\), and only one of its terms.
Finding \(k\)
Match the expression to \((a + b)^n\), taking each constant and each minus sign along with the letter it belongs to. Then the general term is \(\binom{n}{k} a^{n-k} b^k\), and \(k\) is whatever value makes the power of \(x\) in that term equal to the power asked for. Where \(x\) sits decides the equation:
- if \(x\) is in \(a\), it is raised to the power \(n - k\), so solve $n - k = $ (the power wanted);
- if \(x\) is in \(b\), it is raised to the power \(k\), so \(k\) is the power wanted.
Figure 4: Finding \(k\) by lining each expansion up against the general term \(\binom{n}{k}a^{n-k}b^k\). Whatever stands in the place of \(a\) is raised to the power \(n - k\), and whatever stands in the place of \(b\) to the power \(k\). The power of \(x\) comes from whichever of the two contains \(x\), outlined in red: in (1) and (3) \(x\) is part of \(a\), so its power is \(n - k\); in (2) it is part of \(b\), so its power is \(k\). Setting that power equal to the one wanted gives \(k\).
Which of the two terms is called \(a\) doesn’t affect the answer. Swapping them turns \(k\) into \(n - k\), and \(\binom{n}{k} = \binom{n}{n-k}\). In (1), \(k = 4\) with \(x\) as \(a\), or \(k = 3\) with \(x\) as \(b\), and \(\binom74 = \binom73 = 35\) either way. What does matter is that the power \(n - k\) goes on whatever was called \(a\) and the power \(k\) on whatever was called \(b\).
(1) \(x^3\) in \((x + 9)^7\)
Here \(a = x\), \(b = 9\), \(n = 7\). The power of \(x\) is \(n - k = 7 - k\), so \(7 - k = 3\) and \(k = 4\). The term is
\[\binom74 x^3 \cdot 9^4,\]
so the coefficient of \(x^3\) is \(\binom74 \cdot 9^4 = 35 \cdot 6561 = 229\,635\).
(2) \(x^8\) in \((3 - x)^{12}\)
Here \(a = 3\), \(b = -x\), \(n = 12\). The power of \(x\) is \(k\), so \(k = 8\) and \(n - k = 4\). The term is
\[\binom{12}{8} \cdot 3^4 \cdot (-x)^8 = \binom{12}{8} \cdot 3^4 \cdot x^8,\]
since an even power of \(-x\) is positive. So the coefficient of \(x^8\) is \(\binom{12}{8} \cdot 3^4 = \binom{12}{4} \cdot 81 = 495 \cdot 81 = 40\,095\).
(3) \(x^2\) in \((3x - 2)^5\)
Here \(a = 3x\), \(b = -2\), \(n = 5\). The power of \(x\) is \(n - k = 5 - k\), so \(5 - k = 2\) and \(k = 3\). The term is
\[\binom53 \cdot (3x)^2 \cdot (-2)^3 = -\binom53 \cdot 2^3 \cdot 9 \cdot x^2,\]
since \((3x)^2 = 9x^2\) and \((-2)^3 = -8\). So the coefficient of \(x^2\) is \(-\binom53 \cdot 2^3 \cdot 9 = -10 \cdot 8 \cdot 9 = -720\).
The traps are the 3 and the sign: writing \(3x^2\) for \((3x)^2\) gives \(-240\), and dropping the minus gives \(720\). More on both, and a case where \(x\) is in both terms, in binomial-coefficients.
Worked: the sum of a row of Pascal’s triangle
Find a combinatorial proof that \(\displaystyle\sum_{r=0}^{n} \binom{n}{r} = 2^n\).
The idea is to find one collection that has \(2^n\) elements and can also be counted as a sum of binomial coefficients. The subsets of an \(n\)-element set are such a collection.
01-sequences. Let \(N = \{1, 2, \dots, n\}\). Represent each subset of \(N\) by a 01-sequence of length \(n\): a 1 in position \(i\) if \(i\) is in the subset, a 0 if not. For \(n = 6\),
\[\{2, 3, 6\} \subseteq \{1, 2, 3, 4, 5, 6\} \quad\longleftrightarrow\quad 0\,1\,1\,0\,0\,1.\]
Each subset gives exactly one 01-sequence and each 01-sequence gives exactly one subset.
Proof. Count the subsets of \(N\) in two ways.
- All at once. The number of subsets of \(N\) is \(|\mathcal{P}(N)| = 2^{|N|} = 2^n\) (sets-and-set-notation): each of the \(n\) positions of the 01-sequence is a 0 or a 1, independently.
- By cardinality. Every subset has some cardinality \(k\) with \(0 \le k \le n\), so
\[\begin{aligned} \#(\text{subsets of } N) &= \sum_{k=0}^{n} \#(\text{subsets of cardinality } k) \\ &= \sum_{k=0}^{n} \#(\text{01-sequences with exactly } k \text{ ones}) \\ &= \sum_{k=0}^{n} \binom{n}{k}, \end{aligned}\]
since a 01-sequence with exactly \(k\) ones is fixed by choosing which \(k\) of the \(n\) positions hold the ones.
Both expressions count the subsets of \(N\), so
\[2^n = \sum_{r=0}^{n} \binom{n}{r}. \qquad \square\]
For \(n = 6\): \(1 + 6 + 15 + 20 + 15 + 6 + 1 = 64 = 2^6\), the sum of row 6 of Pascal’s triangle. The case \(n = 3\), with all eight subsets of \(\{1, 2, 3\}\) grouped by size, is drawn in binomial-coefficients.
Figure 5: Both counts of the subsets of \({1, \dots, 6}\). Top: a subset is recorded as a 01-sequence, one digit per element, 1 for in and 0 for out, so \({2, 3, 6}\) is \(011001\). Six digits, each 0 or 1, give \(2^6 = 64\) sequences. Bottom: the same 64 sorted by their number of ones, which is the size of the subset. A sequence with \(k\) ones is a choice of \(k\) of the 6 positions, so each group has \(\binom6k\) members, one example shown for each. The group sizes are row 6 of Pascal’s triangle, and they add up to 64.
See also
- probability — sample spaces, events, equally likely outcomes, and the complement
- binomial-coefficients — symmetry, Pascal’s formula and triangle, the Binomial Theorem, finding coefficients, and the row sum
- counting-selections — \(n\) choose \(r\), gluing, and arrangements of words with repeated letters
- 2026-10-13-counting-selections — Lecture 30 · 2026-10-20-inclusion-exclusion — Lecture 32
- practice-problems — §39, with full worked solutions
- practice-problems — §40, with full worked solutions