106 TECHNIQUES OF COUNTING [CHAP. 5
Answers to Supplementary Problems
5.31. (a) 3 628 800; 39 916 800; 479 001 600;
(b) log( 60 !)= 81 .92, so 60!= 6. 59 × 1081.
5.32. (a) 240; (b) 2 184; (c) 1/90; (d) 1/1716.
5.33. (a)n+1; (b)n(n− 1 ); (c) 1/[n(n+ 1 )(n+ 2 );
(d)(n−r)(n−r+ 1 ).
5.34. (a) 10; (b) 35; (c) 91; (d) 15; (e) 1140; (f) 816.
5.35. Hints: (a) Expand( 1 + 1 )n; (b) Expand( 1 − 1 )n.
5.36. (a) 1, 9 , 36 , 84 , 126 , 126 , 84 , 36 , 9 ,1;
(b) 1, 10 , 45 , 120 , 210 , 252 , 210 , 120 , 45 , 10 ,1.
5.37. (a) 60; (b) 210; (c) 504; (d) not defined.
5.38. (a) 15; (b) 105.
5.39. (a)18; (b) 80; (c) 306.
5.40. (a) 26^2 · 103 ; (b) 26· 25 · 103 ; (b); (c) 26· 103.
5.41. (a) 26· 25 · 10 · 9 · 8 =468 000; (b) 26· 25 · 9 · 9 · 8 =
421 200.
5.42. m= 18 · 17 · 16 =4896.
5.43. (a) 12!; (b) 3! 5! 4! 3 !=103 680.
5.44. (a) 6!=720; (b) 2· 3 !· 3 !· =72; (c) 4· 3 !· 3 !=144.
5.45. (a) 120; (b) 48.
5.46. (a) 24; (b) 12.
5.47. (a) 3· 9 ·8; (b) 9· 8 ·5; (c) 9· 8 · 7 /2; (d) 9· 8 · 7 /5.
5.48. (a)P( 6 , 3 )=120; (b) 2· 5 · 4 =40; (c) 2· 5 · 4 =40.
5.49. m=360.
5.50. (a)9;(b) 5.
5.51. (a) 30; (b) 9!/[ 2! 2! 2 !] =45 360; (c) 11!/[ 2! 3! 2 !] =
1 663 200; (d) 8!/[ 2! 2! 2 !] =5040.
5.52. m= 9 !/[ 4! 2! 3 !] =1260.
5.53. (a) 12^3 =1 728; (b)P( 12 , 3 )=1320.
5.54. (a) 10^4 =10 000; (b)P( 10 , 4 )=5040.
5.55. (a) 6; (b) 15; (c) 20.
5.56. (a)C( 12 , 4 ); (b)C( 9 , 2 )·C( 3 , 2 )=108;
(c)C( 9 , 3 )· 3 =252; (d) 9+ 108 + 252 =369 or
C( 12 , 4 )−C( 9 , 4 )=369.
5.57. (a)C( 11 , 5 )=462; (b) 126+ 84 =210;
(c)C( 9 , 5 )+ 2 C( 9 , 4 )=378.
5.58. m=C( 12 , 4 )+ 2 C( 12 , 3 )=935.
5.59. (a)C( 10 , 2 )=45;(b)^6 ·^4 =24; (c)C(^6 ,^2 )+
C( 4 , 2 )=21 or 45− 24 =21.
5.60. (a) 165; (b) 110; (c) 80; (d) 276.
5.61. (a) 46; (b) 22; (c) 14.
5.62. (a) 4; (b) 20; (c) 56.
5.63. (a) 55; (b) 52.5.64. (a) 4; (b) 6; (c) 5.
5.65. (a) 100+ 60 + 42 − 20 − 14 − 8 + 2 =162;
(b) 20− 2 =18; (c) 60− 20 − 8 + 2 =34;
(d) 300− 162 =138.
5.66. (a) 37; (b) 9; (c) 28; (d) 4; (e) 13.
5.67. m= 175
5.68. (a) 22; (b) 37.
5.69. (a) 53; (b) 63.
5.70. Each player will win anywhere from 1 up ton− 1
games (pigeonholes). There arenplayers (pigeons).
5.71. Draw three lines between the midpoints of the sides
ofT. This partitionsTinto 4 equilateral triangles
(pigeonholes) where each side has length 1. Two of
the 5 points (pigeons) must lie in one of the triangles.
5.72. Letribe the remainder whenxiis divisible by 10.
Consider the six pigeonholes: H 1 ={xi|ri= 0 },
H 2 ={xi|ri = 5 }, H 3 ={xi|ri = 1or9},
H 4 ={xi|ri =2or8},H 5 ={xi|ri =3or7},
H 6 ={xi|ri=4or6}. Then somexandybelong
to someHk.
5.73. m=C( 10 , 4 )·C( 6 , 3 )= 420
5.74. (a)n= 33 =27 (Each element can be placed in any
of the three cells.) (b)The number of elements in three
cells can be distributed as follows:[ 3 , 0 , 0 ], [2,1,0],
or [1,1,1]. Thusn= 1 + 3 + 1 =5.
5.75. (a) n= 34 =81 (Each element can be placed
in any of the three cells.) (b) The number of el-
ements in three cells can be distributed as follows:
[ 4 , 0 , 0 ],[ 3 , 1 , 0 ],[ 2 , 2 , 0 ],or[ 2 , 1 , 1 ]. Thus
n= 1 + 4 + 3 + 6 =14.
5.76. (a)C( 21 , 3 )·C( 5 , 2 )· 5 !; (b)C( 20 , 2 )·C( 5 , 2 )· 5 !;
(c) 19·C( 5 , 2 )· 5 !; (d) 19·C( 5 , 2 )· 4 !.
5.77. Draw tree diagramTas in Fig. 5-4. NoteTbeginsat
A, the winner of the first game, and there is only one
choice in the fourth game, the winner of the second
game.
(a)n=15 as listed below; (b) 6; (c) 8:
AAAA,AABAA,AABABA,AABABBA,
AABABBB,ABABAA,ABABABA,ABABABB,
ABABBAA,ABABBAB,ABABBB,ABBBAAA,
ABBBAAB,ABBBAB, ABBBB.
5.78. (a) 4,HTHTHT,HTTHTH,HTHTTH,THTHTH;
(b)n+1.
5.79. 18.
5.80. n!C(n, 2 ).Fig. 5-4