Permutations and Combinations: Mixed Practice, Worked Solutions

Ques­tion 1: Four-digit even num­bers#

The prob­lem#

How many $4$-digit even num­bers can be formed from $1, 2, 3, 4, 5, 6, 7$ with­out rep­e­ti­tion?

Under­stand­ing the prob­lem#

You have seven dig­its and must build a $4$-digit num­ber. No digit may be used twice. The num­ber must be even, which means its last (units) digit must be even. Among the given dig­its, the even ones are $2, 4, 6$.

The idea#

The restric­tion is on the units place, so fill that place first. Then arrange any $3$ of the remain­ing $6$ dig­its in the other three places, where order mat­ters. Mul­ti­ply by the fun­da­men­tal prin­ci­ple of count­ing.

Step-by-step solu­tion#

Step 1. Fill the units place. It must be $2$, $4$ or $6$: $3$ choices.

Step 2. After that, $6$ dig­its remain. The thou­sands, hun­dreds and tens places are filled by arrang­ing $3$ of these $6$ in order.

$${}^6P_3 = 6 \times 5 \times 4 = 120.$$

Step 3. Mul­ti­ply.

$$3 \times 120 = 360.$$

Check­ing the answer#

There are ${}^7P_4 = 840$ four-digit num­bers in all. By sym­me­try, the frac­tion with an even last digit is $\displaystyle \frac37$, and $\displaystyle \frac37 \times 840 = 360$. Cor­rect.

Answer#

$360$ even num­bers.

Com­mon mis­take to avoid#

If you fill the thou­sands place first, the num­ber of choices for the units place depends on what you used ear­lier. Always fill the restricted place first.

Ques­tion 2: Two peo­ple who must not sit together#

The prob­lem#

In how many ways can $7$ peo­ple sit in a row if two par­tic­u­lar peo­ple must not sit together?

Under­stand­ing the prob­lem#

Seven peo­ple, one row of seven seats. Two spe­cific peo­ple, call them A and B, must not be in adja­cent seats. Count the seat­ings.

The idea#

Count­ing "not together" directly is awk­ward. Instead use the com­ple­ment:

$$\text{(not together)} = \text{(all arrangements)} - \text{(together)}.$$

To count "together", tie A and B into one block.

Step-by-step solu­tion#

Step 1. All arrange­ments of $7$ peo­ple in a row.

$$7! = 5040.$$

Step 2. Arrange­ments with A and B together. Treat the pair as one unit. Then there are $6$ units, which can be arranged in $6!$ ways. Inside the block, A and B can be in order AB or BA: $2$ ways.

$$2 \times 6! = 2 \times 720 = 1440.$$

Step 3. Sub­tract.

$$5040 - 1440 = 3600.$$

Check­ing the answer#

Another way: arrange the other $5$ peo­ple ($5! = 120$ ways). This makes $6$ gaps (includ­ing the two ends). Put A and B in two dif­fer­ent gaps in order: ${}^6P_2 = 30$. Total $120 \times 30 = 3600$. Same answer.

Answer#

$3600$ ways.

Ques­tion 3: Arrange­ments of ENGI­NEER­ING#

The prob­lem#

How many arrange­ments of ENGI­NEER­ING are there? How many start and end with E?

Under­stand­ing the prob­lem#

The word has $11$ let­ters, sev­eral of them repeated. Swap­ping two iden­ti­cal let­ters does not give a new arrange­ment, so you must divide out those repeats.

The idea#

For $n$ objects with $p$ alike of one kind, $q$ alike of another, and so on, the num­ber of arrange­ments is

$$\displaystyle \frac{n!}{p!\,q!\,\cdots}.$$

Step-by-step solu­tion#

Step 1. Count each let­ter in E N G I N E E R I N G.

$$\text{E: }3,\quad \text{N: }3,\quad \text{G: }2,\quad \text{I: }2,\quad \text{R: }1 \qquad (3 + 3 + 2 + 2 + 1 = 11).$$

Step 2. All arrange­ments.

$$\displaystyle \frac{11!}{3!\,3!\,2!\,2!} = \frac{39\,916\,800}{6 \times 6 \times 2 \times 2} = \frac{39\,916\,800}{144} = 277\,200.$$

Step 3. Now fix an E in the first place and an E in the last place. One E is left, so the mid­dle $9$ places hold E1, N3, G2, I2, R1.

$$\displaystyle \frac{9!}{3!\,2!\,2!} = \frac{362\,880}{6 \times 2 \times 2} = \frac{362\,880}{24} = 15\,120.$$

Check­ing the answer#

The chance that a ran­dom arrange­ment starts and ends with E is $\displaystyle \frac{3}{11} \times \frac{2}{10} = \frac{6}{110}$, and $\displaystyle \frac{6}{110} \times 277\,200 = 15\,120$. Cor­rect.

Answer#

$277\,200$ arrange­ments in all; $15\,120$ start and end with E.

Com­mon mis­take to avoid#

In the sec­ond part, only one E remains in the mid­dle, so you divide by $1!$ for E, not $3!$.

Ques­tion 4: Solv­ing an equa­tion in ${}^nP_r$#

The prob­lem#

Find $r$ if $5 \times {}^4P_r = 6 \times {}^5P_{r-1}$.

Under­stand­ing the prob­lem#

$r$ is a whole num­ber. For ${}^4P_r$ to make sense, $r \le 4$; for ${}^5P_{r-1}$, $r - 1 \ge 0$. So $1 \le r \le 4$.

The idea#

Use $\displaystyle {}^nP_r = \frac{n!}{(n - r)!}$, sim­plify the fac­to­ri­als, and solve the result­ing equa­tion.

Step-by-step solu­tion#

Step 1. Write both sides with fac­to­ri­als.

$$\displaystyle 5 \cdot \frac{4!}{(4 - r)!} = 6 \cdot \frac{5!}{(5 - (r - 1))!} = 6 \cdot \frac{5!}{(6 - r)!}.$$

Step 2. Put in $4! = 24$ and $5! = 120$.

$$\displaystyle \frac{120}{(4 - r)!} = \frac{720}{(6 - r)!}.$$

Step 3. Cross-mul­ti­ply and divide by $120$.

$$\displaystyle \frac{(6 - r)!}{(4 - r)!} = 6.$$

Step 4. Expand $(6 - r)! = (6 - r)(5 - r)(4 - r)!$ and can­cel.

$$(6 - r)(5 - r) = 6.$$

Step 5. Expand and solve.

$$\begin{aligned} 30 - 11r + r^2 &= 6 \\ r^2 - 11r + 24 &= 0 \\ (r - 3)(r - 8) &= 0. \end{aligned}$$

So $r = 3$ or $r = 8$.

Step 6. $r = 8$ is impos­si­ble because $r \le 4$. So $r = 3$.

Check­ing the answer#

${}^4P_3 = 24$, so the left side is $120$. ${}^5P_2 = 20$, so the right side is $120$. Equal.

Answer#

$r = 3$.

Ques­tion 5: Three-let­ter words from COM­PUTER#

The prob­lem#

How many $3$-let­ter words (with or with­out mean­ing) can be made from COM­PUTER with­out rep­e­ti­tion? How many con­tain the let­ter M?

Under­stand­ing the prob­lem#

COM­PUTER has $8$ dif­fer­ent let­ters. A "word" is any ordered string, so order mat­ters.

The idea#

The first part is ${}^8P_3$. For the sec­ond part, first choose the posi­tion of M, then fill the other two posi­tions from the remain­ing $7$ let­ters.

Step-by-step solu­tion#

Step 1. All $3$-let­ter words.

$${}^8P_3 = 8 \times 7 \times 6 = 336.$$

Step 2. Words that con­tain M. M can be in posi­tion $1$, $2$ or $3$: $3$ choices.

Step 3. The other two posi­tions are filled, in order, from the remain­ing $7$ let­ters.

$${}^7P_2 = 7 \times 6 = 42.$$

Step 4. Mul­ti­ply.

$$3 \times 42 = 126.$$

Check­ing the answer#

Words with­out M: ${}^7P_3 = 210$. Then $336 - 210 = 126$. Same answer.

Answer#

$336$ words; $126$ of them con­tain M.

Ques­tion 6: Dis­trib­ut­ing three prizes#

The prob­lem#

How many ways can $3$ prizes be given to $10$ stu­dents if a stu­dent may win more than one prize? If not?

Under­stand­ing the prob­lem#

The prizes are dif­fer­ent (first, sec­ond, third), so it mat­ters which stu­dent gets which prize. In the first case rep­e­ti­tion is allowed; in the sec­ond it is not.

The idea#

Give the prizes one at a time and count the choices of stu­dent for each.

Step-by-step solu­tion#

Part (a): a stu­dent may win more than one prize

Step 1. Each of the $3$ prizes can go to any of the $10$ stu­dents.

$$10 \times 10 \times 10 = 10^3 = 1000.$$

Part (b): no stu­dent wins twice

Step 1. The first prize has $10$ pos­si­ble win­ners, the sec­ond $9$, the third $8$.

$$10 \times 9 \times 8 = {}^{10}P_3 = 720.$$

Check­ing the answer#

The dif­fer­ence $1000 - 720 = 280$ should be the num­ber of ways in which some stu­dent wins at least two prizes. Count it: all three to one stu­dent, $10$ ways; exactly two to one stu­dent, $10 \times 9 \times 3 = 270$ ways. $10 + 270 = 280$. Cor­rect.

Answer#

$1000$ ways if repeats are allowed; $720$ ways if not.

Ques­tion 7: Choos­ing a cricket team#

The prob­lem#

A cricket team of $11$ is cho­sen from $6$ bats­men, $5$ bowlers and $3$ all-rounders, with exactly $5$ bats­men, $4$ bowlers and $2$ all-rounders. How many ways?

Under­stand­ing the prob­lem#

You are select­ing, not arrang­ing, so order does not mat­ter. The three groups are cho­sen inde­pen­dently, and $5 + 4 + 2 = 11$.

The idea#

Use ${}^nC_r$ for each group and mul­ti­ply.

Step-by-step solu­tion#

Step 1. Bats­men: $5$ from $6$.

$${}^6C_5 = {}^6C_1 = 6.$$

Step 2. Bowlers: $4$ from $5$.

$${}^5C_4 = {}^5C_1 = 5.$$

Step 3. All-rounders: $2$ from $3$.

$${}^3C_2 = {}^3C_1 = 3.$$

Step 4. Mul­ti­ply.

$$6 \times 5 \times 3 = 90.$$

Check­ing the answer#

Choos­ing $5$ of $6$ is the same as choos­ing the one bats­man left out, which explains $6$. The same idea gives $5$ and $3$.

Answer#

$90$ ways.

Ques­tion 8: Lines and tri­an­gles with collinear points#

The prob­lem#

$12$ points lie in a plane; $5$ of them are collinear and no other three are. How many lines? How many tri­an­gles?

Under­stand­ing the prob­lem#

Any two points give a line, and any three non-collinear points give a tri­an­gle. The $5$ collinear points spoil the sim­ple count: all pairs among them give the same line, and triples among them give no tri­an­gle.

The idea#

Count as if no three were collinear, then cor­rect for the $5$ collinear points.

Step-by-step solu­tion#

Lines

Step 1. If no three were collinear, the num­ber of lines would be

$$\displaystyle {}^{12}C_2 = \frac{12 \times 11}{2} = 66.$$

Step 2. Pairs cho­sen from the $5$ collinear points were counted as ${}^5C_2 = 10$ sep­a­rate lines, but they are all one line. Remove them and add that one line back.

$$66 - 10 + 1 = 57.$$

Tri­an­gles

Step 1. Triples from all $12$ points.

$$\displaystyle {}^{12}C_3 = \frac{12 \times 11 \times 10}{6} = 220.$$

Step 2. Triples cho­sen entirely from the $5$ collinear points lie on one line and form no tri­an­gle.

$${}^5C_3 = 10.$$

Step 3. Sub­tract.

$$220 - 10 = 210.$$

Check­ing the answer#

Count lines another way: $1$ line through the five; lines join­ing one of the five to one of the other seven: $5 \times 7 = 35$; lines among the seven: ${}^7C_2 = 21$. Total $1 + 35 + 21 = 57$. Cor­rect.

Answer#

$57$ lines and $210$ tri­an­gles.

Ques­tion 9: Five-card hands with exactly three hearts#

The prob­lem#

How many $5$-card hands have exactly $3$ hearts?

Under­stand­ing the prob­lem#

A stan­dard pack has $52$ cards: $13$ hearts and $39$ non-hearts. A hand is a selec­tion, so order does not mat­ter. "Exactly $3$ hearts" means the other $2$ cards are not hearts.

The idea#

Choose the hearts and the non-hearts sep­a­rately, then mul­ti­ply.

Step-by-step solu­tion#

Step 1. Choose $3$ hearts from $13$.

$$\displaystyle {}^{13}C_3 = \frac{13 \times 12 \times 11}{6} = 286.$$

Step 2. Choose $2$ non-hearts from $39$.

$$\displaystyle {}^{39}C_2 = \frac{39 \times 38}{2} = 741.$$

Step 3. Mul­ti­ply.

$$286 \times 741 = 211\,926.$$

Check­ing the answer#

$286 \times 741 = 286 \times 700 + 286 \times 41 = 200\,200 + 11\,726 = 211\,926$.

Answer#

$211\,926$ hands.

Com­mon mis­take to avoid#

Choos­ing the remain­ing $2$ cards from $49$ would allow more hearts, giv­ing "at least $3$", not "exactly $3$".

Ques­tion 10: Answer­ing seven ques­tions from two sec­tions#

The prob­lem#

A ques­tion paper has two sec­tions of $6$ ques­tions each; a stu­dent answers $7$ ques­tions with at least $3$ from each sec­tion. How many ways?

Under­stand­ing the prob­lem#

The stu­dent picks $7$ ques­tions (order does not mat­ter). Let $a$ be the num­ber from Sec­tion A and $b$ from Sec­tion B, with $a + b = 7$, $a \ge 3$, $b \ge 3$.

The idea#

List the pos­si­ble splits $(a, b)$, count each with com­bi­na­tions, and add (the cases do not over­lap).

Step-by-step solu­tion#

Step 1. Pos­si­ble splits: $a = 3, b = 4$ or $a = 4, b = 3$. (If $a = 2$, then $b = 5$, but $a \ge 3$ fails.)

Step 2. Case $(3, 4)$.

$${}^6C_3 \times {}^6C_4 = 20 \times 15 = 300.$$

Step 3. Case $(4, 3)$.

$${}^6C_4 \times {}^6C_3 = 15 \times 20 = 300.$$

Step 4. Add.

$$300 + 300 = 600.$$

Check­ing the answer#

With­out the con­di­tion there are ${}^{12}C_7 = 792$ choices. The excluded splits are $(1,6), (2,5), (5,2), (6,1)$: $6 + 90 + 90 + 6 = 192$. And $792 - 192 = 600$. Cor­rect.

Answer#

$600$ ways.

Ques­tion 11: MATH­E­MAT­ICS with the vow­els together#

The prob­lem#

How many words can be formed from all let­ters of MATH­E­MAT­ICS with the vow­els together?

Under­stand­ing the prob­lem#

MATH­E­MAT­ICS has $11$ let­ters: M2, A2, T2, H1, E1, I1, C1, S1. The vow­els are A, E, A, I ($4$ vow­els, with A repeated). "Together" means the four vow­els sit next to each other in some order.

The idea#

Glue the vow­els into one block. Arrange the block with the con­so­nants, then arrange the vow­els inside the block. Divide by fac­to­ri­als for repeated let­ters at each stage.

Step-by-step solu­tion#

Step 1. Arrange­ments inside the vowel block: A, A, E, I.

$$\displaystyle \frac{4!}{2!} = \frac{24}{2} = 12.$$

Step 2. The con­so­nants are M, M, T, T, H, C, S ($7$ let­ters). With the vowel block, there are $8$ units, where M and T each appear twice.

$$\displaystyle \frac{8!}{2!\,2!} = \frac{40\,320}{4} = 10\,080.$$

Step 3. Mul­ti­ply.

$$10\,080 \times 12 = 120\,960.$$

Check­ing the answer#

Let­ter count: $4$ vow­els $+ 7$ con­so­nants $= 11$. Cor­rect. With­out the con­di­tion the total is $\displaystyle \frac{11!}{2!\,2!\,2!} = 4\,989\,600$, much larger, as expected.

Answer#

$120\,960$ words.

Ques­tion 12: Relat­ing ${}^nP_r$ and ${}^nC_r$#

The prob­lem#

Show that ${}^nP_r = r \cdot {}^{n}C_r \cdot (r - 1)!$ and hence that ${}^nP_r \ge {}^nC_r$.

Under­stand­ing the prob­lem#

Here $1 \le r \le n$. You must prove an iden­tity and then deduce an inequal­ity from it.

The idea#

Use the lesson's link ${}^nP_r = r!\,{}^nC_r$: to arrange $r$ objects, first choose them (${}^nC_r$ ways) and then order them ($r!$ ways). Then write $r! = r \cdot (r - 1)!$.

Step-by-step solu­tion#

Step 1. Start from the for­mu­las.

$$\displaystyle {}^nC_r = \frac{n!}{r!\,(n - r)!}, \qquad {}^nP_r = \frac{n!}{(n - r)!}.$$

Step 2. So

$$\displaystyle {}^nP_r = r! \cdot \frac{n!}{r!\,(n - r)!} = r! \cdot {}^nC_r.$$

Step 3. Write $r! = r \cdot (r - 1)!$.

$${}^nP_r = r \cdot {}^nC_r \cdot (r - 1)!.$$

This proves the iden­tity.

Step 4. For the inequal­ity: since $r \ge 1$, we have $r! \ge 1$. Also ${}^nC_r > 0$. Mul­ti­ply­ing,

$${}^nP_r = r!\,{}^nC_r \ge 1 \cdot {}^nC_r = {}^nC_r. \qquad \blacksquare$$

Check­ing the answer#

$n = 5, r = 3$: ${}^5P_3 = 60$, and $3 \times {}^5C_3 \times 2! = 3 \times 10 \times 2 = 60$. Also $60 \ge 10$. Equal­ity holds only when $r! = 1$, that is $r = 1$ (for exam­ple ${}^5P_1 = {}^5C_1 = 5$).

Answer#

${}^nP_r = r!\,{}^nC_r = r \cdot {}^nC_r \cdot (r - 1)!$, and since $r! \ge 1$, ${}^nP_r \ge {}^nC_r$.