Previous: Homework assignment 08Homework assignment 08 Up: Homework assignmentsHomework assignments Next: Homework assignment 11Homework assignment 11
Document also available in PDF, Postscript, DVI, pure text and LaTeX.

Homework assignment 10



3.4. Permutations and Combinations

Exercise 1  [2 p. 215]   How many batting orders are possible for a nine-man baseball team?
Proof: [Correction] Since we have nine players and nine possible positions (and since order matters), we merely have P(9,9)=362880.

Exercise 2  [6 p. 215]   In how many ways can six people be seated in a circle of six chairs? Only relative positions in the circle can be distinguished. (Hint: Think of taking any circle arrangement, cutting it open, and straightening it out to form a line.)
Proof: [Correction] Since only relative position matters, (that is, it is rotationally invariant) we can measure or relate all permutations with respect to one fixed person. Thus, the solution is (n-1)!=(6-1)!=120.

Exercise 3  [13 p. 251]   In how many different ways can you seat 11 men and 8 women around a circular table if no 2 women are to sit together? (Only relative positions in the circle can be distinguished.)
Proof: [Correction] A good training for this exercise is to first solve it with simpler hypothesis (typically on a straight table).

The hypothesis ``no 2 women sit together'' can be rewritten as ``between two men, there is at most 1 woman''. To break the symmetry due to the round table, we can pickup once for all one of the 11 men, and decide to list the other guests starting from this man. So we have 10 other men remaining, and 11 positions between them to put the 8 women. There are C(11,8) ways of choosing which positions are to be filled. It remains to choose in which order the 10 men and 8 women will be placed. There are respectively 10! and 8! ways of doing this. Conclusion: the solution of the full problem is C(11,8)8!10!=24141680640000 ways.

Exercise 4  [77 p. 221]   In a 5-card hand drawn from a standard 52-card deck, what is the probability of getting the following?
  1. a flush
  2. a full house
  3. a straight
  4. a straight flush
Proof: [Correction] The total number of hands is C(52,5) (choose 5 cards out of 52).
  1. Probability for a flush (choose a colors, and choose 5 cards with this color): 4× C(13,5)/C(52,5)
  2. Probability for a full house (choose a number; choose 3 cards with this number; choose a different number; choose 2 cars with this number): 13× C(4,3)×12 C(4,2)/C(52,5)
  3. Probability for a straight (choose the lowest number of the flush, and choose the color of each card): 10×55/C(52,5)
  4. Probability for a straight flush (choose the lowest number of the flush, and choose the color) 10×4/C(52,5)

3.5. Binomial Theorem

Exercise 5  [1h p. 225]   Expand the expression ( 3x + 1/2)5 using the binomial theorem.
Proof: [Correction] 15/16x + 45/4 x2 + 135/2 x3 + 405/2x4 + 243 x5 + 1/32

Exercise 6  [14 p. 226]   Prove the following formula (Hint: Use Pascal's formula).
C(n+2,r) = C(n,r) + 2C(n,r-1)+C(n,r-2) for 2<= r <= n
Proof: [Correction]
C(n+2,r) =C(n+1,r)+C(n+1,r-1)
  =[C(n,r)+C(n,r-1)]+[C(n,r-1)+C(n,r-2)]
  = C(n,r) + 2C(n,r-1)+C(n,r-2)

Exercise 7  [18 p. 226]  
  1. Use the binomial theorem to prove that
    C(n,n)+2C(n,n-1)+22C(n,n-2)+...+2n-1C(n,1)+2nC(n,0) = 3n
  2. Prove this result directly from
    C(n,0)+2C(n,1)+22C(n,2)+...+2nC(n,n) = 3n.
Proof: [Correction]
  1. We just transorm 3 into 2+1 to apply the binomial theorem:
    3n = (2+1)n = C(n,0)2n10+C(n,1)2n-111+...+C(n,n)201n
      = C(n,n)+2C(n,n-1)+22C(n,n-2)+...+2n-1C(n,1)+2nC(n,0)
  2. We know that C(n,k)=C(n,n-k). By applying this formula to all the binomial coefficients in
    C(n,0)+2C(n,1)+22C(n,2)+...+2nC(n,n) = 3n
    We get precisely the formula we wanted to prove:
    C(n,n)+2C(n,n-1)+22C(n,n-2)+...+2n-1C(n,1)+2nC(n,0) = 3n
Previous: Homework assignment 08Homework assignment 08 Up: Homework assignmentsHomework assignments Next: Homework assignment 11Homework assignment 11
Homework assignment 10 / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Tue Dec 2 13:40:29 2003