Combinations and Selection Problems, Worked Solutions

Ques­tion 1: Eval­u­at­ing two com­bi­na­tions#

The prob­lem#

Eval­u­ate $^{12}C_4$ and $^{12}C_8$. Why are they equal?

Under­stand­ing the prob­lem#

$^{12}C_4$ is the num­ber of ways to choose $4$ objects from $12$ dis­tinct objects when order does not mat­ter; $^{12}C_8$ is the num­ber of ways to choose $8$ from the same $12$. You must com­pute both and explain why the num­bers come out the same.

The idea#

Use $\displaystyle ^nC_r = \frac{n!}{r!\,(n - r)!}$. In prac­tice, can­cel $(n - r)!$ first so that you only mul­ti­ply $r$ fac­tors on top: $\displaystyle ^nC_r = \frac{n(n - 1)\cdots(n - r + 1)}{r!}$. For the rea­son, use the iden­tity $^nC_r = {}^nC_{n-r}$.

Step-by-step solu­tion#

Step 1. Write $^{12}C_4$ with the fac­to­ri­als can­celled: $\displaystyle \tfrac{12!}{4!\,8!}$ leaves the four fac­tors $12 \times 11 \times 10 \times 9$ on top.

$$\displaystyle ^{12}C_4 = \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1}$$

Step 2. Can­cel before mul­ti­ply­ing to keep the num­bers small: $4 \times 3 = 12$ can­cels the $12$, and $2$ divides $10$ to give $5$.

$$^{12}C_4 = 11 \times 5 \times 9 = 495$$

Step 3. Now $\displaystyle ^{12}C_8 = \tfrac{12!}{8!\,4!}$. This is exactly the same frac­tion as $\displaystyle \tfrac{12!}{4!\,8!}$, only with the two fac­to­ri­als in the denom­i­na­tor writ­ten in the other order.

$$\displaystyle ^{12}C_8 = \frac{12!}{8!\,4!} = \frac{12!}{4!\,8!} = {}^{12}C_4 = 495$$

Step 4. Explain in words. Every time you choose $4$ of the $12$ objects to include, you have auto­mat­i­cally cho­sen the other $8$ to leave out. So each selec­tion of $4$ matches exactly one selec­tion of $8$, and the two counts must be equal. This is the iden­tity $^nC_r = {}^nC_{n-r}$.

Check­ing the answer#

$495$ is a whole num­ber, as a count must be. Also $^{12}C_4 \times 4! = 495 \times 24 = 11880 = 12 \times 11 \times 10 \times 9 = {}^{12}P_4$, match­ing $^nC_r \cdot r! = {}^nP_r$.

Answer#

$^{12}C_4 = {}^{12}C_8 = 495$; they are equal because choos­ing $4$ to include is the same as choos­ing $8$ to leave out, i.e. $^nC_r = {}^nC_{n-r}$.

Ques­tion 2: Find­ing n from a com­bi­na­tion equa­tion#

The prob­lem#

Find $n$: (a) $^nC_2 = 66$; (b) $^{2n}C_3 : {}^nC_3 = 12 : 1$.

Under­stand­ing the prob­lem#

In each part $n$ is unknown. You must turn the com­bi­na­tion state­ment into an ordi­nary alge­braic equa­tion and solve it. Remem­ber that $n$ must be a pos­i­tive whole num­ber, and large enough that the com­bi­na­tions make sense ($n \ge 2$ in (a), $n \ge 3$ in (b)).

The idea#

Expand each com­bi­na­tion using $\displaystyle ^nC_r = \frac{n(n - 1)\cdots(n - r + 1)}{r!}$, then solve. In (b), writ­ing the ratio as a frac­tion lets com­mon fac­tors can­cel.

Step-by-step solu­tion#

Part (a): $^nC_2 = 66$

Step 1. Expand $^nC_2$.

$$\displaystyle ^nC_2 = \frac{n(n - 1)}{2} = 66$$

Step 2. Mul­ti­ply both sides by $2$.

$$n(n - 1) = 132$$

Step 3. Look for two con­sec­u­tive whole num­bers whose prod­uct is $132$. Since $12 \times 11 = 132$, $n = 12$. (Solv­ing $n^2 - n - 132 = 0$ as a qua­dratic gives $(n - 12)(n + 11) = 0$, so $n = 12$ or $n = -11$.)

Step 4. Reject $n = -11$, because $n$ counts objects and can­not be neg­a­tive.

$$n = 12$$

Part (b): $^{2n}C_3 : {}^nC_3 = 12 : 1$

Step 1. Write the ratio as a frac­tion and expand both com­bi­na­tions. Each has $3!$ in its denom­i­na­tor.

$$\displaystyle \frac{^{2n}C_3}{^nC_3} = \frac{\dfrac{2n(2n - 1)(2n - 2)}{3!}}{\dfrac{n(n - 1)(n - 2)}{3!}} = \frac{2n(2n - 1)(2n - 2)}{n(n - 1)(n - 2)}$$

Step 2. Sim­plify. Write $2n - 2 = 2(n - 1)$; then $n$ and $(n - 1)$ can­cel from top and bot­tom.

$$\displaystyle \frac{2n(2n - 1) \cdot 2(n - 1)}{n(n - 1)(n - 2)} = \frac{4(2n - 1)}{n - 2}$$

Step 3. Set this equal to $12$ and cross-mul­ti­ply.

$$\displaystyle \begin{aligned} \frac{4(2n - 1)}{n - 2} &= 12 \\ 4(2n - 1) &= 12(n - 2) \\ 8n - 4 &= 12n - 24 \\ 20 &= 4n \\ n &= 5 \end{aligned}$$

Check­ing the answer#

(a) $\displaystyle ^{12}C_2 = \tfrac{12 \times 11}{2} = 66$. Cor­rect. (b) $^{10}C_3 = 120$ and $^5C_3 = 10$, and $120 : 10 = 12 : 1$. Cor­rect.

Answer#

(a) $n = 12$; (b) $n = 5$.

Com­mon mis­take to avoid#

In (b), do not can­cel $2n$ against $n$ care­lessly and lose the fac­tor $2$. Writ­ing $2n - 2 = 2(n - 1)$ first makes the can­celling safe.

Ques­tion 3: Chords and tri­an­gles from points on a cir­cle#

The prob­lem#

How many chords can be drawn through $15$ points on a cir­cle? How many tri­an­gles with ver­tices among them?

Under­stand­ing the prob­lem#

You have $15$ points on a cir­cle. A chord is a seg­ment join­ing two of the points. A tri­an­gle needs three points as ver­tices. You must count both.

The idea#

A chord is fixed by choos­ing $2$ points, and the order does not mat­ter (the chord $AB$ is the chord $BA$), so the num­ber of chords is $^{15}C_2$. A tri­an­gle is fixed by choos­ing $3$ points, so the count is $^{15}C_3$, pro­vided no three of the points are in a straight line. Three points on a cir­cle are never collinear (a line meets a cir­cle in at most two points), so every choice of $3$ gives a gen­uine tri­an­gle. This is Exam­ple 6 of the les­son.

Step-by-step solu­tion#

Step 1. Count the chords.

$$\displaystyle ^{15}C_2 = \frac{15 \times 14}{2 \times 1} = \frac{210}{2} = 105$$

Step 2. Con­firm that every triple of points forms a tri­an­gle: a straight line cuts a cir­cle in at most $2$ points, so no $3$ of the points are collinear.

Step 3. Count the tri­an­gles.

$$\displaystyle ^{15}C_3 = \frac{15 \times 14 \times 13}{3 \times 2 \times 1} = \frac{2730}{6} = 455$$

Check­ing the answer#

$\displaystyle ^{15}C_3 = {}^{15}C_2 \times \tfrac{13}{3} = 105 \times \tfrac{13}{3} = 455$, which agrees with the for­mula $\displaystyle ^nC_r = {}^nC_{r-1} \cdot \tfrac{n - r + 1}{r}$.

Answer#

$105$ chords and $455$ tri­an­gles.

Ques­tion 4: A team with a player forced in or kept out#

The prob­lem#

In how many ways can a team of $11$ be cho­sen from $16$ play­ers (a) if $2$ par­tic­u­lar play­ers must be included? (b) if a par­tic­u­lar player is excluded?

Under­stand­ing the prob­lem#

A team is a selec­tion, so order does not mat­ter. In (a), two named play­ers are guar­an­teed places; in (b), one named player is not allowed.

The idea#

Deal with the con­di­tion first, then choose freely from who­ever is left. If play­ers are forced in, they fill places and leave the pool. If a player is excluded, he leaves the pool but fills no place.

Step-by-step solu­tion#

Part (a): two par­tic­u­lar play­ers included

Step 1. Put the $2$ play­ers in the team. That leaves $11 - 2 = 9$ places to fill.

Step 2. Those $9$ must come from the play­ers not yet used: $16 - 2 = 14$ play­ers.

Step 3. Count, using $^{14}C_9 = {}^{14}C_5$ to keep the work­ing short.

$$\displaystyle ^{14}C_9 = {}^{14}C_5 = \frac{14 \times 13 \times 12 \times 11 \times 10}{5 \times 4 \times 3 \times 2 \times 1} = \frac{240240}{120} = 2002$$

Part (b): one par­tic­u­lar player excluded

Step 1. Remove the excluded player from the pool: $16 - 1 = 15$ play­ers remain.

Step 2. All $11$ places are still open, so choose $11$ from $15$.

$$\displaystyle ^{15}C_{11} = {}^{15}C_4 = \frac{15 \times 14 \times 13 \times 12}{4 \times 3 \times 2 \times 1} = \frac{32760}{24} = 1365$$

Check­ing the answer#

For (b), the total num­ber of teams is $^{16}C_{11} = 4368$. Teams that do con­tain the par­tic­u­lar player num­ber $^{15}C_{10} = 3003$. Then $4368 - 3003 = 1365$, the same as our answer.

Answer#

(a) $2002$; (b) $1365$.

Ques­tion 5: Draw­ing balls of two colours#

The prob­lem#

A bag holds $5$ red and $6$ white balls. In how many ways can $4$ balls be drawn (a) with $2$ of each colour? (b) with at least one red?

Under­stand­ing the prob­lem#

The balls are treated as dis­tinct objects (so choos­ing dif­fer­ent red balls gives dif­fer­ent selec­tions). You draw $4$ balls; order of draw­ing does not mat­ter. Part (a) fixes exactly how many of each colour; part (b) only requires that red appears at least once.

The idea#

For (a), choose the reds and the whites sep­a­rately and mul­ti­ply (the mul­ti­pli­ca­tion prin­ci­ple). For (b), "at least one" is eas­i­est by the com­ple­ment: count all selec­tions, then sub­tract those with no red at all.

Step-by-step solu­tion#

Part (a): two red and two white

Step 1. Choose $2$ of the $5$ red balls.

$$\displaystyle ^5C_2 = \frac{5 \times 4}{2} = 10$$

Step 2. Choose $2$ of the $6$ white balls.

$$\displaystyle ^6C_2 = \frac{6 \times 5}{2} = 15$$

Step 3. Each choice of reds can be paired with each choice of whites, so mul­ti­ply.

$$10 \times 15 = 150$$

Part (b): at least one red

Step 1. Count every pos­si­ble selec­tion of $4$ from all $11$ balls.

$$\displaystyle ^{11}C_4 = \frac{11 \times 10 \times 9 \times 8}{24} = 330$$

Step 2. Count the selec­tions with no red, i.e. all $4$ white.

$$^6C_4 = {}^6C_2 = 15$$

Step 3. Every selec­tion has either no red or at least one red, so sub­tract.

$$330 - 15 = 315$$

Check­ing the answer#

Add the cases directly for (b): $1$ red: $^5C_1\,{}^6C_3 = 5 \times 20 = 100$; $2$ red: $150$; $3$ red: $^5C_3\,{}^6C_1 = 60$; $4$ red: $^5C_4 = 5$. Total $100 + 150 + 60 + 5 = 315$. It matches.

Answer#

(a) $150$; (b) $315$.

Com­mon mis­take to avoid#

Do not add $^5C_2 + {}^6C_2$ in (a). You need a red pair and a white pair, so the counts mul­ti­ply.

Ques­tion 6: Diag­o­nals of a decagon#

The prob­lem#

How many diag­o­nals has a decagon?

Under­stand­ing the prob­lem#

A decagon has $10$ ver­tices. A diag­o­nal joins two ver­tices that are not next to each other. Seg­ments join­ing neigh­bour­ing ver­tices are sides, not diag­o­nals.

The idea#

Any $2$ ver­tices deter­mine a seg­ment, giv­ing $^{10}C_2$ seg­ments. Of these, exactly $10$ are sides. So the num­ber of diag­o­nals is $^nC_2 - n$ with $n = 10$, as in Exam­ple 6.

Step-by-step solu­tion#

Step 1. Count all seg­ments join­ing two of the $10$ ver­tices.

$$\displaystyle ^{10}C_2 = \frac{10 \times 9}{2} = 45$$

Step 2. A decagon has $10$ sides, and each side is one of those seg­ments. Remove them.

$$45 - 10 = 35$$

Check­ing the answer#

Another way: from each ver­tex you can draw a diag­o­nal to every ver­tex except itself and its two neigh­bours, i.e. $10 - 3 = 7$ diag­o­nals. Over $10$ ver­tices that gives $70$, but each diag­o­nal has been counted from both ends, so divide by $2$: $35$. It agrees.

Answer#

A decagon has $35$ diag­o­nals.

Ques­tion 7: A com­mit­tee with at least three girls#

The prob­lem#

A com­mit­tee of $7$ is cho­sen from $9$ boys and $5$ girls with at least $3$ girls. How many ways?

Under­stand­ing the prob­lem#

A com­mit­tee is a selec­tion. It has $7$ mem­bers, and the num­ber of girls must be $3$ or more. There are only $5$ girls, so the num­ber of girls can be $3$, $4$ or $5$; the rest of the $7$ places go to boys.

The idea#

Split into sep­a­rate cases by the exact num­ber of girls. In each case choose the girls and the boys sep­a­rately and mul­ti­ply; then add the cases, because they can­not hap­pen together. This is the method of Exam­ple 3.

Step-by-step solu­tion#

Step 1. List the pos­si­ble cases (girls + boys $= 7$):

• $3$ girls and $4$ boys
• $4$ girls and $3$ boys
• $5$ girls and $2$ boys

Step 2. Case of $3$ girls and $4$ boys.

$$^5C_3 \times {}^9C_4 = 10 \times 126 = 1260$$

Step 3. Case of $4$ girls and $3$ boys.

$$^5C_4 \times {}^9C_3 = 5 \times 84 = 420$$

Step 4. Case of $5$ girls and $2$ boys.

$$^5C_5 \times {}^9C_2 = 1 \times 36 = 36$$

Step 5. Add the three cases.

$$1260 + 420 + 36 = 1716$$

Check­ing the answer#

Count by com­ple­ment: all com­mit­tees $^{14}C_7 = 3432$. Com­mit­tees with fewer than $3$ girls: $0$ girls $^9C_7 = 36$; $1$ girl $5 \times {}^9C_6 = 420$; $2$ girls $10 \times {}^9C_5 = 1260$; total $1716$. So those with at least $3$ girls are $3432 - 1716 = 1716$. It agrees.

Answer#

$1716$ ways.

Com­mon mis­take to avoid#

Do not choose $3$ girls first and then "any $4$ of the remain­ing $11$". That counts com­mit­tees with $4$ or $5$ girls more than once. Always split into exact cases.

Ques­tion 8: Words from EQUA­TION#

The prob­lem#

From the let­ters of EQUA­TION, how many $5$-let­ter words use $3$ vow­els and $2$ con­so­nants?

Under­stand­ing the prob­lem#

A "word" here is any arrange­ment of let­ters, whether or not it has a mean­ing. Each let­ter of EQUA­TION may be used at most once. The word has $5$ let­ters: exactly $3$ vow­els and $2$ con­so­nants. Unlike a com­mit­tee, a word's let­ters are in order, so arrange­ment mat­ters.

The idea#

This is "choose, then arrange" (Exam­ple 7). First choose which vow­els and which con­so­nants to use (com­bi­na­tions), then arrange the $5$ cho­sen let­ters in order ($5!$ ways).

Step-by-step solu­tion#

Step 1. Sort the let­ters. EQUA­TION has $8$ let­ters, all dif­fer­ent:

• vow­els: E, U, A, I, O ($5$ vow­els)
• con­so­nants: Q, T, N ($3$ con­so­nants)

Step 2. Choose $3$ of the $5$ vow­els.

$$^5C_3 = 10$$

Step 3. Choose $2$ of the $3$ con­so­nants.

$$^3C_2 = 3$$

Step 4. The $5$ cho­sen let­ters are all dif­fer­ent, so they can be arranged in $5!$ ways.

$$5! = 120$$

Step 5. Mul­ti­ply the three stages.

$$10 \times 3 \times 120 = 3600$$

Check­ing the answer#

The answer is the same as Exam­ple 7 (DAUGH­TER), and that is no coin­ci­dence: the cal­cu­la­tion there was $^3C_2 \times {}^5C_3 \times 5!$, and here it is $^5C_3 \times {}^3C_2 \times 5!$, which is the same prod­uct.

Answer#

$3600$ words.

Ques­tion 9: Two friends who will not come together#

The prob­lem#

A per­son has $8$ friends and invites $5$ to din­ner. In how many ways, if two of the friends refuse to come together?

Under­stand­ing the prob­lem#

The guest list is a selec­tion of $5$ from $8$. Call the two awk­ward friends $A$ and $B$. A list is allowed as long as it does not con­tain both $A$ and $B$; it may con­tain one of them or nei­ther.

The idea#

Use the com­ple­ment: count all guest lists, then sub­tract the for­bid­den ones (those con­tain­ing both $A$ and $B$).

Step-by-step solu­tion#

Step 1. Count all selec­tions of $5$ from $8$.

$$\displaystyle ^8C_5 = {}^8C_3 = \frac{8 \times 7 \times 6}{6} = 56$$

Step 2. Count the for­bid­den lists. If both $A$ and $B$ are invited, $3$ more guests are needed from the other $6$ friends.

$$\displaystyle ^6C_3 = \frac{6 \times 5 \times 4}{6} = 20$$

Step 3. Sub­tract.

$$56 - 20 = 36$$

Check­ing the answer#

Count the allowed cases directly. Nei­ther $A$ nor $B$: choose $5$ from the other $6$: $^6C_5 = 6$. Exactly one of them ($2$ ways to pick which), plus $4$ from the other $6$: $2 \times {}^6C_4 = 2 \times 15 = 30$. Total $6 + 30 = 36$. It agrees.

Answer#

$36$ ways.

Ques­tion 10: Prov­ing Pas­cal's rule#

The prob­lem#

Prove $^nC_r + {}^nC_{r-1} = {}^{n+1}C_r$ alge­braically.

Under­stand­ing the prob­lem#

You must show that the left side, writ­ten with fac­to­ri­als, sim­pli­fies to exactly the right side. Here $1 \le r \le n$, so that every fac­to­r­ial is defined.

The idea#

Write both terms on the left using $\displaystyle ^nC_r = \frac{n!}{r!\,(n - r)!}$, bring them to a com­mon denom­i­na­tor, add, and recog­nise the result. The key facts are

$$r! = r \cdot (r - 1)!, \qquad (n - r + 1)! = (n - r + 1) \cdot (n - r)!.$$

Step-by-step solu­tion#

Step 1. Write both terms with fac­to­ri­als. For the sec­ond, replace $r$ by $r - 1$: then $n - (r - 1) = n - r + 1$.

$$\displaystyle ^nC_r + {}^nC_{r-1} = \frac{n!}{r!\,(n - r)!} + \frac{n!}{(r - 1)!\,(n - r + 1)!}$$

Step 2. Choose the com­mon denom­i­na­tor $r!\,(n - r + 1)!$. The first frac­tion is miss­ing a fac­tor $(n - r + 1)$, since $(n - r + 1)! = (n - r + 1)(n - r)!$; mul­ti­ply its top and bot­tom by $(n - r + 1)$.

$$\displaystyle \frac{n!}{r!\,(n - r)!} = \frac{n!\,(n - r + 1)}{r!\,(n - r + 1)!}$$

Step 3. The sec­ond frac­tion is miss­ing a fac­tor $r$, since $r! = r\,(r - 1)!$; mul­ti­ply its top and bot­tom by $r$.

$$\displaystyle \frac{n!}{(r - 1)!\,(n - r + 1)!} = \frac{n!\,r}{r!\,(n - r + 1)!}$$

Step 4. Add the numer­a­tors and take out the com­mon fac­tor $n!$.

$$\displaystyle \frac{n!\,(n - r + 1) + n!\,r}{r!\,(n - r + 1)!} = \frac{n!\,(n - r + 1 + r)}{r!\,(n - r + 1)!} = \frac{n!\,(n + 1)}{r!\,(n - r + 1)!}$$

Step 5. Use $(n + 1) \cdot n! = (n + 1)!$ and write $n - r + 1$ as $(n + 1) - r$.

$$\displaystyle \frac{(n + 1)!}{r!\,\big((n + 1) - r\big)!} = {}^{n+1}C_r$$

This is the right side, so the iden­tity is proved.

Check­ing the answer#

Test a small case: $n = 4$, $r = 2$. Left: $^4C_2 + {}^4C_1 = 6 + 4 = 10$. Right: $^5C_2 = 10$. They agree.

Answer#

$\displaystyle ^nC_r + {}^nC_{r-1} = \frac{(n + 1)!}{r!\,(n + 1 - r)!} = {}^{n+1}C_r$, as required.