Count­ing with­out list­ing

How many 44-let­ter codes can be made from 1010 let­ters? In how many ways can 55 peo­ple sit in a row? List­ing them all is hope­less. The trick is to count by mul­ti­ply­ing instead. We start with the fun­da­men­tal prin­ci­ple of count­ing. Then come fac­to­r­ial nota­tion and the for­mu­las for arrange­ments (per­mu­ta­tions): with rep­e­ti­tion, with­out it, and when some objects are iden­ti­cal.

Fun­da­men­tal prin­ci­ple of count­ing

If one event can hap­pen in mm ways and, after it, a sec­ond can hap­pen in nn ways, then the two together can hap­pen in m×nm \times n ways. The same goes for three or more events: keep mul­ti­ply­ing.

Exam­ple 1. With 33 shirts and 44 trousers you can make 1212 out­fits, as the tree shows. A num­ber plate with 22 let­ters fol­lowed by 33 dig­its, rep­e­ti­tion allowed, can be made in 262×103=676,00026^2 \times 10^3 = 676{,}000 ways.

Tree diagram: three branches for shirts S1, S2, S3, each splitting into four branches for trousers T1 to T4, giving twelve outfits from S1 T1 to S3 T4; 3 times 4 = 12.
Exam­ple 1: every shirt pairs with every pair of trousers

Exam­ple 2. How many 33-digit num­bers can be made from 1,2,5,7,91, 2, 5, 7, 9 with­out repeat­ing a digit? The answer is 5×4×3=605 \times 4 \times 3 = 60. How many of them are even? An even one must end in 22. Tip: fill the restricted place first. That gives 4×3×1=124 \times 3 \times 1 = 12.

Fac­to­ri­als

Prod­ucts like these come up so often that they get their own sym­bol: n!=1×2×⋯×nn! = 1 \times 2 \times \cdots \times n, read "n fac­to­r­ial", with 0!=10! = 1 by agree­ment. A handy fact is n!=n×(n−1)!n! = n \times (n - 1)!. For exam­ple, 6!=7206! = 720. When divid­ing fac­to­ri­als, can­cel rather than mul­ti­ply out: 9!7!=9×8=72\displaystyle \tfrac{9!}{7!} = 9 \times 8 = 72.

Per­mu­ta­tions

An ordered arrange­ment of rr objects cho­sen from nn dis­tinct objects is called a per­mu­ta­tion. Think of fill­ing places one after another. The first place can be filled in nn ways, the sec­ond in n−1n - 1, and so on, down to the rrth in n−r+1n - r + 1:

nPr=n(n−1)⋯(n−r+1)=n!(n−r)!,nPn=n!.\displaystyle ^nP_r = n(n - 1)\cdots(n - r + 1) = \frac{n!}{(n - r)!}, \qquad ^nP_n = n!.

If rep­e­ti­tion is allowed, every place has all the choices again, and the count is nrn^r.

Exam­ple 3. Gold, sil­ver and bronze can be shared among 88 run­ners in 8P3=336^8P_3 = 336 ways.

Three boxes for the gold, silver and bronze places holding 8, 7 and 6, the number of runners available for each, multiplied together to give 336.
Exam­ple 3: fill­ing three medal places from eight run­ners

Exam­ple 4. The let­ters of TRI­AN­GLE can be arranged in 8!=40,3208! = 40{,}320 ways. If the word must begin with T and end with E, those two are fixed, and only the mid­dle let­ters move: 6!=7206! = 720.

Exam­ple 5. Find nn if nP4=20×nP2^nP_4 = 20 \times {}^nP_2. Can­celling the com­mon fac­tors leaves (n−2)(n−3)=20(n - 2)(n - 3) = 20, so n=7n = 7.

Objects that are alike

Swap­ping two iden­ti­cal let­ters gives the same word, so the plain fac­to­r­ial over­counts. We divide out the repeats. If among nn objects pp are alike of one kind, qq of another and rr of a third, with the rest all dif­fer­ent, the num­ber of dis­tinct arrange­ments is

n!p! q! r!.\displaystyle \frac{n!}{p!\,q!\,r!}.

Exam­ple 6. BANANA has 66 let­ters, with A three times and N twice, giv­ing 6!3! 2!=60\displaystyle \tfrac{6!}{3!\,2!} = 60 arrange­ments.

Exam­ple 7. STA­TIS­TICS has 1010 let­ters, with S 33 times, T 33 times and I twice. So there are 10!3! 3! 2!=50,400\displaystyle \tfrac{10!}{3!\,3!\,2!} = 50{,}400 arrange­ments.

Exam­ple 8. PER­MU­TA­TION has 1111 let­ters, with T twice. How many arrange­ments keep the vow­els together? Tie E, U, A, I, O into one block. That leaves 77 units with T twice, and the vow­els can then be shuf­fled inside their block: 7!2!×5!=2520×120=302,400\displaystyle \tfrac{7!}{2!} \times 5! = 2520 \times 120 = 302{,}400.

Prac­tice ques­tions

  1. How many 33-digit num­bers can be formed from 1,2,3,4,5,61, 2, 3, 4, 5, 6 (a) with rep­e­ti­tion; (b) with­out rep­e­ti­tion?
  2. How many 44-let­ter codes from the first 1010 let­ters of the alpha­bet, no let­ter repeated?
  3. Eval­u­ate 10!8! 2!\displaystyle \tfrac{10!}{8!\,2!} and find xx if 17!+18!=x9!\displaystyle \tfrac{1}{7!} + \tfrac{1}{8!} = \tfrac{x}{9!}.
  4. Find nn: nP5=42×nP3^nP_5 = 42 \times {}^nP_3; 2nP3=100×nP2^{2n}P_3 = 100 \times {}^nP_2.
  5. In how many ways can 66 books be arranged on a shelf so that two par­tic­u­lar books are always together?
  6. How many arrange­ments of MIS­SIS­SIPPI? How many begin with P?
  7. How many 55-digit num­bers greater than 50,00050{,}000 can be formed from 0,3,5,7,90, 3, 5, 7, 9 with­out rep­e­ti­tion?
  8. How many arrange­ments of ORANGES keep the vow­els in the odd places?
  9. In how many ways can 44 boys and 33 girls stand in a line so that no two girls are together?
  10. How many 66-digit tele­phone num­bers can be made with dig­its 00–99, start­ing with 6767, no digit repeated?

Answers

Show answers
  1. 216216; 120120.
  2. 50405040.
  3. 4545; x=9×8+9=81x = 9 \times 8 + 9 = 81.
  4. (n−3)(n−4)=42(n - 3)(n - 4) = 42, n=10n = 10; 2n(2n−1)(2n−2)=100n(n−1)2n(2n - 1)(2n - 2) = 100n(n - 1) gives 4(2n−1)=1004(2n - 1) = 100, n=13n = 13.
  5. 2×5!=2402 \times 5! = 240.
  6. 11!4! 4! 2!=34,650\displaystyle \tfrac{11!}{4!\,4!\,2!} = 34{,}650; start­ing with P: 10!4! 4!=6,300\displaystyle \tfrac{10!}{4!\,4!} = 6{,}300.
  7. First digit 55, 77 or 99: 3×4!=723 \times 4! = 72.
  8. Put the vow­els O, A, E in the 44 odd places: 4P3=24^4P_3 = 24. The con­so­nants R, N, G, S fill the rest: 4!=244! = 24. Total 576576.
  9. Line up the boys first: 4!4!. The girls then go into the 55 gaps: 5P3=60^5P_3 = 60. Total 14401440.
  10. 8P4=1680^8P_4 = 1680.