Counting Principle and Permutations, Worked Solutions

Ques­tion 1: Three-digit num­bers with and with­out rep­e­ti­tion#

The prob­lem#

How many $3$-digit num­bers can be formed from $1, 2, 3, 4, 5, 6$ (a) with rep­e­ti­tion; (b) with­out rep­e­ti­tion?

Under­stand­ing the prob­lem#

A 3-digit num­ber has three places: hun­dreds, tens and units. You may use only the six dig­its $1$ to $6$. In (a) a digit may be used again; in (b) each digit may be used at most once. Since $0$ is not avail­able, there is no worry about a lead­ing zero.

The idea#

Fill the three places one after another and use the fun­da­men­tal prin­ci­ple of count­ing: if the first place can be filled in $p$ ways, then the sec­ond in $q$ ways, then the third in $r$ ways, the total is $p \times q \times r$.

Step-by-step solu­tion#

Part (a): with rep­e­ti­tion

Step 1. Each place can take any of the 6 dig­its, because rep­e­ti­tion is allowed.

Step 2. Mul­ti­ply.

$$6 \times 6 \times 6 = 216$$

Part (b): with­out rep­e­ti­tion

Step 1. The hun­dreds place has 6 choices. Once one digit is used, the tens place has 5 choices left, and the units place 4.

Step 2. Mul­ti­ply.

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

Check­ing the answer#

With­out rep­e­ti­tion you must get fewer num­bers than with rep­e­ti­tion: $120 < 216$. ✓

Answer#

(a) $216$; (b) $120$.

Ques­tion 2: Four-let­ter codes#

The prob­lem#

How many $4$-let­ter codes from the first $10$ let­ters of the alpha­bet, no let­ter repeated?

Under­stand­ing the prob­lem#

A code is an ordered string: ABCD and DCBA are dif­fer­ent codes. You choose 4 let­ters from A to J, all dif­fer­ent.

The idea#

Order mat­ters and there is no rep­e­ti­tion, so this is the num­ber of per­mu­ta­tions of 10 things taken 4 at a time, $^{10}P_4$.

Step-by-step solu­tion#

Step 1. The first let­ter has 10 choices, the sec­ond 9, the third 8, the fourth 7.

Step 2. Mul­ti­ply.

$$^{10}P_4 = 10 \times 9 \times 8 \times 7 = 5040$$

Check­ing the answer#

Using the for­mula: $\displaystyle ^{10}P_4 = \frac{10!}{6!} = \frac{3628800}{720} = 5040$. ✓

Answer#

$5040$ codes.

Ques­tion 3: Work­ing with fac­to­ri­als#

The prob­lem#

Eval­u­ate $\displaystyle \frac{10!}{8!\,2!}$ and find $x$ if $\displaystyle \frac{1}{7!} + \frac{1}{8!} = \frac{x}{9!}$.

Under­stand­ing the prob­lem#

Fac­to­ri­als grow very fast, so never mul­ti­ply them out fully. Instead write the larger fac­to­r­ial in terms of the smaller one, for exam­ple $10! = 10 \times 9 \times 8!$.

The idea#

Use $n! = n \times (n - 1)!$ to can­cel com­mon fac­tors. For the equa­tion, write every term over the com­mon denom­i­na­tor $9!$.

Step-by-step solu­tion#

Part (a)

Step 1. Write $10! = 10 \times 9 \times 8!$ and can­cel $8!$.

$$\displaystyle \frac{10!}{8!\,2!} = \frac{10 \times 9 \times 8!}{8! \times 2} = \frac{90}{2} = 45$$

Part (b)

Step 1. Mul­ti­ply both sides by $9!$ to clear the denom­i­na­tors.

$$\displaystyle \frac{9!}{7!} + \frac{9!}{8!} = x$$

Step 2. Sim­plify each frac­tion: $9! = 9 \times 8 \times 7!$ and $9! = 9 \times 8!$.

$$\displaystyle \frac{9!}{7!} = 9 \times 8 = 72, \qquad \frac{9!}{8!} = 9$$

Step 3. Add.

$$x = 72 + 9 = 81$$

Check­ing the answer#

$\displaystyle \frac{1}{5040} + \frac{1}{40320} = \frac{8 + 1}{40320} = \frac{9}{40320}$, and $\displaystyle \frac{81}{362880} = \frac{9}{40320}$. ✓

Answer#

$\displaystyle \frac{10!}{8!\,2!} = 45$; $x = 81$.

Ques­tion 4: Solv­ing equa­tions in nPr#

The prob­lem#

Find $n$: (a) $^nP_5 = 42 \times {}^nP_3$; (b) $^{2n}P_3 = 100 \times {}^nP_2$.

Under­stand­ing the prob­lem#

$^nP_r = n(n - 1)(n - 2)\cdots$ ($r$ fac­tors). You need the pos­i­tive inte­ger $n$ that makes each equa­tion true. Remem­ber $n$ must be at least as large as $r$ for $^nP_r$ to make sense.

The idea#

Write each $^nP_r$ as a prod­uct, can­cel the com­mon fac­tors, and solve the result­ing sim­ple equa­tion.

Step-by-step solu­tion#

Part (a)

Step 1. Expand both sides.

$$n(n - 1)(n - 2)(n - 3)(n - 4) = 42\, n(n - 1)(n - 2)$$

Step 2. Since $n \ge 5$, the fac­tor $n(n - 1)(n - 2)$ is not zero, so divide by it.

$$(n - 3)(n - 4) = 42$$

Step 3. Notice $42 = 7 \times 6$, two con­sec­u­tive inte­gers, so $n - 3 = 7$. Or expand:

$$n^2 - 7n + 12 = 42 \;\Rightarrow\; n^2 - 7n - 30 = 0 \;\Rightarrow\; (n - 10)(n + 3) = 0$$

Step 4. $n$ must be pos­i­tive, so $n = 10$.

Part (b)

Step 1. Expand both sides.

$$2n(2n - 1)(2n - 2) = 100\, n(n - 1)$$

Step 2. Write $2n - 2 = 2(n - 1)$.

$$2n(2n - 1) \cdot 2(n - 1) = 100\, n(n - 1)$$

Step 3. Divide both sides by $n(n - 1)$, which is not zero since $n \ge 2$.

$$4(2n - 1) = 100$$

Step 4. Solve.

$$2n - 1 = 25 \;\Rightarrow\; n = 13$$

Check­ing the answer#

(a) $^{10}P_5 = 30240$ and $42 \times {}^{10}P_3 = 42 \times 720 = 30240$. ✓
(b) $^{26}P_3 = 26 \times 25 \times 24 = 15600$ and $100 \times {}^{13}P_2 = 100 \times 156 = 15600$. ✓

Answer#

(a) $n = 10$; (b) $n = 13$.

Com­mon mis­take to avoid#

In (a), do not keep $n = -3$: the num­ber of objects can­not be neg­a­tive.

Ques­tion 5: Two books always together#

The prob­lem#

In how many ways can $6$ books be arranged on a shelf so that two par­tic­u­lar books are always together?

Under­stand­ing the prob­lem#

All 6 books are dif­fer­ent. Two cho­sen books, call them A and B, must sit side by side. Within that pair, AB and BA are dif­fer­ent arrange­ments.

The idea#

Tie the two books together and treat them as one unit. Arrange the units, then arrange the books inside the unit.

Step-by-step solu­tion#

Step 1. With A and B tied together, there are $4 + 1 = 5$ units to arrange.

$$5! = 120$$

Step 2. Inside the unit, A and B can be arranged in $2! = 2$ ways.

Step 3. Mul­ti­ply.

$$2 \times 120 = 240$$

Check­ing the answer#

Total arrange­ments are $6! = 720$. The chance that two par­tic­u­lar books are adja­cent is $\displaystyle \tfrac{2}{6} = \tfrac13$, and $\displaystyle \tfrac13 \times 720 = 240$. ✓

Answer#

$240$ ways.

Ques­tion 6: Arrange­ments of MIS­SIS­SIPPI#

The prob­lem#

How many arrange­ments of MIS­SIS­SIPPI? How many begin with P?

Under­stand­ing the prob­lem#

MIS­SIS­SIPPI has 11 let­ters, but they are not all dif­fer­ent: M appears once, I four times, S four times and P twice. Swap­ping two iden­ti­cal let­ters does not cre­ate a new arrange­ment.

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#

Part (a): all arrange­ments

Step 1. Count the let­ters: $n = 11$, with I: 4, S: 4, P: 2, M: 1.

Step 2. Apply the for­mula.

$$\displaystyle \frac{11!}{4!\,4!\,2!} = \frac{39916800}{24 \times 24 \times 2} = \frac{39916800}{1152} = 34650$$

Part (b): begin­ning with P

Step 1. Fix one P in the first place. The remain­ing 10 let­ters are M, I, I, I, I, S, S, S, S, P, now only one P.

Step 2. Arrange these 10 let­ters.

$$\displaystyle \frac{10!}{4!\,4!} = \frac{3628800}{576} = 6300$$

Check­ing the answer#

The frac­tion of arrange­ments start­ing with P should equal the frac­tion of let­ters that are P, $\displaystyle \tfrac{2}{11}$: $\displaystyle \tfrac{2}{11} \times 34650 = 6300$. ✓

Answer#

$34650$ arrange­ments; $6300$ begin with P.

Ques­tion 7: Five-digit num­bers greater than 50,000#

The prob­lem#

How many $5$-digit num­bers greater than $50{,}000$ can be formed from $0, 3, 5, 7, 9$ with­out rep­e­ti­tion?

Under­stand­ing the prob­lem#

All five dig­its are used exactly once. A num­ber is greater than $50{,}000$ when its first digit is $5$ or more. Since dig­its can­not repeat, $50000$ itself can­not be formed, so every num­ber start­ing with $5$ is already larger than $50{,}000$.

The idea#

Fill the first place with an allowed digit, then arrange the remain­ing four dig­its freely.

Step-by-step solu­tion#

Step 1. The first digit must be $5$, $7$ or $9$: 3 choices.

Step 2. The remain­ing 4 dig­its (includ­ing $0$, which is fine in later places) fill the other 4 places in $4! = 24$ ways.

Step 3. Mul­ti­ply.

$$3 \times 24 = 72$$

Check­ing the answer#

The small­est such num­ber is $50379 > 50000$, and the first digit $3$ (giv­ing num­bers in the thirty-thou­sands) is cor­rectly excluded.

Answer#

$72$ num­bers.

Ques­tion 8: ORANGES with vow­els in odd places#

The prob­lem#

How many arrange­ments of ORANGES keep the vow­els in the odd places?

Under­stand­ing the prob­lem#

ORANGES has 7 dif­fer­ent let­ters. The vow­els are O, A, E (3 of them); the con­so­nants are R, N, G, S (4). The odd places are posi­tions 1, 3, 5, 7, four places for three vow­els, so one odd place will hold a con­so­nant.

The idea#

Place the vow­els first, in the odd posi­tions, then fill every remain­ing posi­tion with the con­so­nants. Mul­ti­ply the two counts.

Step-by-step solu­tion#

Step 1. Arrange 3 vow­els in 4 odd places (order mat­ters).

$$^4P_3 = 4 \times 3 \times 2 = 24$$

Step 2. Four places remain (the three even places and one odd place). Arrange the 4 con­so­nants in them.

$$4! = 24$$

Step 3. Mul­ti­ply.

$$24 \times 24 = 576$$

Check­ing the answer#

Total arrange­ments are $7! = 5040$; the ones we want are a small frac­tion ($\displaystyle \tfrac{576}{5040} \approx 0.11$), which is sen­si­ble for a restric­tive con­di­tion.

Answer#

$576$ arrange­ments.

Com­mon mis­take to avoid#

Do not write $3!$ for the vow­els: there are 4 odd places, not 3, so it is $^4P_3$.

Ques­tion 9: No two girls together#

The prob­lem#

In how many ways can $4$ boys and $3$ girls stand in a line so that no two girls are together?

Under­stand­ing the prob­lem#

All 7 peo­ple are dif­fer­ent. The con­di­tion "no two girls together" means between any two girls there must be at least one boy.

The idea#

Use the gap method: arrange the boys first, then put each girl in a sep­a­rate gap between or beside the boys.

Step-by-step solu­tion#

Step 1. Arrange the 4 boys.

$$4! = 24$$

Step 2. Four boys in a row cre­ate 5 gaps (marked $\_$): $\_\,B\,\_\,B\,\_\,B\,\_\,B\,\_$.

Step 3. Place the 3 girls in 3 dif­fer­ent gaps, order mat­ter­ing.

$$^5P_3 = 5 \times 4 \times 3 = 60$$

Step 4. Mul­ti­ply.

$$24 \times 60 = 1440$$

Check­ing the answer#

Total arrange­ments are $7! = 5040$, and $1440 < 5040$. Also, each girl in a dif­fer­ent gap guar­an­tees a boy between any two girls. ✓

Answer#

$1440$ ways.

Ques­tion 10: Tele­phone num­bers start­ing with 67#

The prob­lem#

How many $6$-digit tele­phone num­bers can be made with dig­its $0$–$9$, start­ing with $67$, no digit repeated?

Under­stand­ing the prob­lem#

The first two places are fixed as $6$ and $7$. Four places remain, and no digit may repeat, so $6$ and $7$ can­not appear again.

The idea#

Count the dig­its still avail­able and arrange them in the four remain­ing places: a per­mu­ta­tion.

Step-by-step solu­tion#

Step 1. Dig­its avail­able: $10 - 2 = 8$.

Step 2. Fill 4 places from 8 dig­its, order mat­ter­ing.

$$^8P_4 = 8 \times 7 \times 6 \times 5 = 1680$$

Check­ing the answer#

$\displaystyle ^8P_4 = \frac{8!}{4!} = \frac{40320}{24} = 1680$. ✓

Answer#

$1680$ tele­phone num­bers.