Unit 2, lesson 11

Combinations and Binomial Coefficients

How combinations count unordered selections by removing the overcount of ordered ones, giving the binomial coefficient, its symmetry, Pascal's identity and triangle, and the binomial theorem.

  • Video 11
  • Ordered and Unordered Selections

A three-person review committee is to be chosen from eight volunteers, and the committee has no internal roles. Choosing A, then B, then C produces the same committee as choosing C, then A, then B, so the ordered count 8⋅7⋅6=3368 \cdot 7 \cdot 6 = 336 counts every committee several times. How many different committees are there, and if every committee is equally likely, what is the chance that a particular volunteer is on it? This lesson removes the overcount to obtain the binomial coefficient, explains its symmetry and Pascal’s identity, and shows why the same numbers are the coefficients in the expansion of (a+b)n(a + b)^n.

Key terms

Combination

Definition A combination of rr objects from nn distinct objects is an unordered selection without replacement, that is, a subset with rr elements. Two combinations are the same exactly when they contain the same objects, in whatever order those objects were chosen. The number of such combinations is the binomial coefficient (nr)\binom{n}{r} defined below.

In plain words A combination records who is in the group, not who was picked first. It is the right outcome to count when the selected objects play no roles that can be told apart.

Example A committee of three from eight volunteers is a combination, and there are (83)=56\binom{8}{3} = 56 committees. Suppose the selection makes all 56 committees equally likely, as happens when three names are drawn one at a time, each uniformly from the names not yet drawn. Volunteer A belongs to (72)=21\binom{7}{2} = 21 committees, since the other two members come from the remaining seven volunteers, so

P(A is chosen)=(72)(83)=2156=38.\begin{aligned} P(\text{A is chosen}) &= \frac{\binom{7}{2}}{\binom{8}{3}} \\[0.4em] &= \frac{21}{56} = \frac{3}{8}. \end{aligned}

The equal likelihood is an assumption about the mechanism. If the selection favored some volunteers, there would still be 56 committees, but the ratio of the two counts would no longer be guaranteed to equal the probability.

Overcounting

Definition A counting method overcounts when it counts some target outcomes more than once. If the method counts nothing but target outcomes and counts every target outcome exactly mm times, with the same mm for every outcome, then the number of target outcomes is the method’s count divided by mm. If the number of repetitions varies from outcome to outcome, a single division is no longer justified.

In plain words Count something easier, such as ordered lists, and then divide out the repetition, but only after checking that every outcome is repeated the same number of times.

Example The ordered count 8⋅7⋅6=3368 \cdot 7 \cdot 6 = 336 lists each committee once for each of its 3!=63! = 6 orders. The committee of A, B and C, for instance, appears as ABC, ACB, BAC, BCA, CAB and CBA. Every committee has exactly 6 orders, so there are 336/6=56336/6 = 56 committees. Compare a flawed count of the committees that contain A or B, which picks A or B in 2 ways and then any 2 of the other 7 volunteers in (72)=21\binom{7}{2} = 21 ways, for 2⋅21=422 \cdot 21 = 42. The 30 committees with exactly one of A and B are counted once each, but the 6 committees with both are counted twice, so no single division repairs the count. The correct number is 30+6=3630 + 6 = 36, which also equals 56−(63)=56−2056 - \binom{6}{3} = 56 - 20.

Binomial coefficient

Definition For integers 0≤r≤n0 \le r \le n, the binomial coefficient, read ”nn choose rr”, is

(nr)=n!r! (n−r)!.\binom{n}{r} = \frac{n!}{r!\,(n - r)!}.

It counts the subsets with rr elements of a set with nn elements. The formula follows from overcounting, since the n!/(n−r)!n!/(n - r)! ordered selections of rr objects list each subset exactly r!r! times. In particular (n0)=(nn)=1\binom{n}{0} = \binom{n}{n} = 1, because there is one empty subset and one subset containing everything. The coefficients are symmetric,

(nr)=(nn−r),\binom{n}{r} = \binom{n}{n - r},

because pairing each subset with its complement, the objects left out, matches the subsets of size rr one to one with the subsets of size n−rn - r.

In plain words Divide the ordered count by the number of orders of each group. Choosing who is in and choosing who is left out are the same decision, so the two counts agree.

Example By symmetry (85)=(83)=56\binom{8}{5} = \binom{8}{3} = 56, since every three-person committee from eight people leaves out a group of five. Likewise, choosing 9 objects from 11 means choosing the 2 that are left out, so

(119)=(112)=11⋅102=55.\begin{aligned} \binom{11}{9} &= \binom{11}{2} \\[0.4em] &= \frac{11 \cdot 10}{2} = 55. \end{aligned}

Pascal’s identity and Pascal’s triangle

Definition Pascal’s identity states that for integers nn and rr with 1≤r≤n−11 \le r \le n - 1,

(nr)=(n−1r−1)+(n−1r).\binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r}.

To see this, fix one of the nn objects. A subset of size rr either contains it, and then its other r−1r - 1 members come from the remaining n−1n - 1 objects, or leaves it out, and then all rr members come from the remaining n−1n - 1 objects. The two cases are disjoint and cover every subset, so the sum rule gives the identity. Pascal’s triangle arranges the coefficients in rows. Row nn lists (n0),(n1),…,(nn)\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}, starting with row 0 at the top. Each row begins and ends with 1, and by Pascal’s identity every entry in between is the sum of the two entries just above it. Rows 0 to 5 are

11112113311464115101051\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 \end{array}

In plain words Sort the groups by whether one particular member is in them. The triangle is a table of combination counts that can be built by additions alone.

Example For three-person committees from eight volunteers, splitting on whether volunteer A is included gives

(83)=(72)+(73),\binom{8}{3} = \binom{7}{2} + \binom{7}{3},

which is 56=21+3556 = 21 + 35. In the triangle above, each 10 in row 5 is the sum 4+64 + 6 of the two entries above it in row 4.

Binomial theorem

Definition For real numbers aa and bb and every integer n≥0n \ge 0,

(a+b)n=∑r=0n(nr)an−rbr,(a + b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n - r} b^{r},

where a power with exponent 0 is read as 1, even when its base is 0. The reason is a counting argument. Expanding the product of nn copies of a+ba + b means choosing aa or bb from each copy and adding all the resulting products. The product an−rbra^{n-r}b^{r} arises once for each way of choosing which rr of the nn copies supply bb, and there are (nr)\binom{n}{r} such choices. No probability is involved in the identity.

In plain words The coefficients in the expansion of (a+b)n(a + b)^n are the entries of row nn of Pascal’s triangle, because each coefficient counts the ways to pick which brackets supply bb.

Example In (a+b)3(a + b)^3, a product with two factors bb and one factor aa comes from choosing which 2 of the 3 brackets supply bb, which can be done in (32)=3\binom{3}{2} = 3 ways. So

(a+b)3=a3+3a2b+3ab2+b3.\begin{aligned} (a + b)^3 &= a^3 + 3a^2b \\[0.4em] &\quad + 3ab^2 + b^3 . \end{aligned}

Setting a=b=1a = b = 1 in the theorem gives ∑r=0n(nr)=2n\sum_{r=0}^{n} \binom{n}{r} = 2^n, the number of all subsets of a set with nn elements, since each element is either in a subset or not. For row 6 this reads 1+6+15+20+15+6+1=64=261 + 6 + 15 + 20 + 15 + 6 + 1 = 64 = 2^6.

Check yourself

  1. A club has 10 members. In how many ways can it choose a two-person team, and in how many ways can it choose a president and a vice president who are different people? Why do the answers differ by a factor of 2?
Show the answer

A team is unordered, so there are (102)=45\binom{10}{2} = 45 teams. The two offices are different roles, so there are 10⋅9=9010 \cdot 9 = 90 ordered choices. Each team can fill the two offices in exactly 2!=22! = 2 ways, so the ordered count is twice the unordered count.

  1. A group has three experienced and four new volunteers. A committee of three is chosen so that all three-person subsets are equally likely. Find the probability that exactly two members are experienced and the probability that at least two are experienced.
Show the answer

There are (73)=35\binom{7}{3} = 35 committees. A committee with exactly two experienced members combines a choice of 2 of the 3 experienced volunteers with a choice of 1 of the 4 new ones, which gives 3⋅4=123 \cdot 4 = 12 committees, so

P(exactly two)=(32)(41)(73)=1235.\begin{aligned} P(\text{exactly two}) &= \frac{\binom{3}{2}\binom{4}{1}}{\binom{7}{3}} \\[0.4em] &= \frac{12}{35}. \end{aligned}

At least two means exactly two or exactly three. Only (33)=1\binom{3}{3} = 1 committee has three experienced members, and the two cases are disjoint, so the probability of at least two is (12+1)/35=13/35(12 + 1)/35 = 13/35. The answers differ by the all-experienced committee, which “exactly two” leaves out and “at least two” includes.

  1. Find the coefficient of x2y3x^2y^3 in the expansion of (x−2y)5(x - 2y)^5.
Show the answer

Apply the binomial theorem with a=xa = x, b=−2yb = -2y and n=5n = 5. The power y3y^3 requires r=3r = 3, and that term is

(53)x2(−2y)3=10⋅(−8) x2y3=−80 x2y3.\begin{aligned} &\binom{5}{3} x^{2} (-2y)^{3} \\[0.4em] &\quad = 10 \cdot (-8)\, x^2y^3 \\[0.4em] &\quad = -80\, x^2y^3 . \end{aligned}

The coefficient is −80-80. A common slip is to stop at (53)=10\binom{5}{3} = 10 and forget that the factor −2-2 is also raised to the third power.

How this lesson connects

Builds on