Page 171: Letters ABCDE, forming strings of length 3

 

34.    With repetitions: 5^3
Five choices for first letter, five choices for second letter, five choices for third letter

35.    Without repetitions: 5*4*3
Five choices for first letter, four choices for second letter, three choices for third letter

36.    Beginning with A, with repetitions: 5^2
1 choice (A) for first letter, five choices for second letter, five choices for third letter

37.    Beginning with A, without repetitions: 4*3
1 choice (A) for first letter, four choices for second letter, three choices for third letter

38.    Without A, with repetitions: 4^3
Selecting from {B, C, D, E}: Four choices for first letter, four choices for second letter, four choices for third letter

39.    Without A, without repetitions: 4*3*2
Selecting from {B, C, D, E}: Four choices for first letter, three choices for second letter, two choices for third letter

40.    With A, with repetitions: 5^3-4^3
All possibilities, minus the ones not containing A
Consider why this is wrong: Pick a position for A (3 ways); for the remaining two positions, pick any of the 5 letters (5^2)
Hint: there is some double-counting – why?

41.    With A, without repetitions: 5*4*3 – 4*3*2 = 3*4*3
All possibilities, minus the ones not containing A
Alternate: Pick a position for A (3 ways); pick any of the remaining letters for the first available position (4 ways); pick any of the remaining letters for the final position (3 ways)

 

Page 172: Five computer science books, three math books, and two art books

 

54.    All orderings: 10!

55.    All orderings, putting CS books on left, math books in center, and art books on right: 5!*3!*2!
There are 5! ways to order the CS books
There are 3! ways to order the math books
There are 2! ways to order the art books

56.    All orderings, putting CS books on left: 5!*5!
There are 5! ways to order the CS books
There are 5! ways to order the remaining books

57.    3!*5!*3!*2!

a.       Arrange the subjects (3!)

b.      Arrange the cs books (5!)

c.       Arrange the math books (3!)

d.      Arrange the art books (2!)

58.    8!*C(9,2)*2!

a.       Arrange the cs and math books (8!)

b.      Pick which two of the 9 positions between (and outside) the previously arranged books to use for art books C(9,2)

c.       Pick which art book goes in each position (2!)

 

 

59.     

60.    Functions from X to Y, with |X| = n and |Y| = m: mn
Suppose that X = {x1, …, xn}.  We need to pick a y value for x1 (there are m ways to do it), a y value for x2 (there are m ways to do it), etc., repeated n times. 

 

 

Page 182: Number of strings formed by ordering the letters ABCDE:
(Note that “ordering” implies “no repetitions”)

10.    Containing ACE: 3!
Permutations of { ACE, B, D}

11.    Containing A, C, and E together in any order:

a.       Order A, C, E: 3!

b.      Order p(ACE) with B and D: 3!

c.       Multiplication: 3!*3!

12.    Containing DB and AE: 3!

13.    Either AE or EA: 4!*2

14.    A appears before D: C(5,2)*3! = 5!/(3!*2!)*3! = ½*5!

15.    Neither AB nor CD:

a.       Contains AB: 4!

b.      Contains CD: 4!

c.       Contains both AB and CD: 3!

d.      Contains either AB or CD: 2*4! – 3!

e.       Contains neither: 5! – (2*4! – 3!)

16.    Containing neither AB nor BE:

a.       Contains AB: 4!

b.      Contains BE: 4!

c.       Contains both: 3!

d.      Contains either AB or BE: 2*4! – 3!

e.       Doesn’t contain either 5! – (2*4! – 3!)

17.    A before C and C before E: C(5,3)*2!

18.    Either DB or BE (or both):

a.       DB: 4!

b.      BE: 4!

c.       Both: 3!

d.      Either: 2*4! – 3!

===================================================

Page 183: Club of six men and six women:

31.    Committee of five: C(12,5)

32.    Three men, four women: C(6,3)*C(6,4)

33.    Four persons with at least one woman:

a.       Four men: C(6,4)

b.      Four persons: C(12,4)

c.       Subtract: C(12,4) – C(6,4)

34.    Four persons with at most one man:

a.       Four women: C(6,4)

b.      Three women and a man: C(6,3)*C(6,1)

c.       Addition: C(6,4)+C(6,3)*C(6,1)

35.    Four persons with at least one of each sex: C(12,4) – 2*C(6,4)

36.    Four persons, not containing both Mabel and Ralph

a.       Four persons, containing both: C(10,2)

b.      Subtract: C(12,4)-C(10,2)

 

 

37.    4/10 GOP, 3/12 Dem., 2/4 Ind: C(10,4)*C(12,3)*C(4,2)

38.    C(8,3)

39.    Three zeros in a row in an 8-bit string: 6

40.     

 

Poker hands

41.    Four aces: 48

42.    Four of a kind: 13*48

43.    All spades: C(13,5)

44.    Cards of exactly two suits: C(4,2)*C(26,5)

45.    Cards of all suits: Not restricted to any three suits

a.       Cards of no suits: 0

b.      Cards of 1 suit: C(4,1)*C(13,5)

c.       Cards of two suits: C(4,2)*C(26,5)

d.      Cards of three suits: C(4,3)*C(39,5)

e.       None of the above: C(52,5) – C(4,3)*C(39,5) – C(4,2)*C(26,5) – C(4,1)*C(13,5)

46.    A2345 in one suit: 4

47.    Consecutive and of the same suit: 9*4 (A low)

48.    9*4^4

49.    13*C(4,2)*12*C(4,2)*11 ?*C(3,2)

 

Bridge hands

50.     

 

Page 209: Number of strings by re-ordering letters

  1. GUIDE: one of each, so it’s straight permutions 5!
  2. SCHOOL: two O’s – generalized permutations – 6!/2!
  3. SALESPERSONS: four S’s, 2 E’s – generalized permutations – 12!/(4!*2!)
  4. SALESPERSONS if the four S’s are consecutive: 9!/2!
  5. SALESPERSONS if no two S’s are consecutive: (8!/2!)*C(9,4)
  6. SCHOOL using some or all of the letters (pick the i letters to use, for i
    1. 0 letters: 1
    2. 1 letter: C(5,1)*1!
    3. 2 letters: C(4,0)*2!/2! + C(5,2)*2! - “OO” and two letter combinations of {S, C, H, O, L} – C(5,2)*2!+1
    4. 3 letters: C(4,1)*3!/2! + C(5,3)*3!
    5. 4 letters:  C(4,2)*4!/2! + C(5,4)*4!
    6. 5 letters: C(4,3)*5!/2! + C(5,5)*5!
    7. 6 letters: C(4,4)*6!/2!

Comics are Action, Superman, Captain Marvel, Archie, X-man, Nancy

  1. How many ways to pick 6? 
    6 categories, so 11 positions, to be filled by 6 x’s and 5 |’s is C(11,5)
  2. How many ways to select 10?
    15 positions to be filled by 10 x’s and 5 |’s is C(15,5)
  3. How many ways to select 10, if we choose at least one of each?
    15 positions; 6 already have x’s; C(9,5)


Categories

  1. How many routes in x,y,z coordinates from (0,0,0) to (i,j,k) where i,j,k are positive integers and we are limited to one-unit steps in each positive direction?
    Denote each step by a letter x, y, or z, depending on the direction.  We must have I of the x’s, j of the y’s, and k of the z’s.  This is (i+j+k)!/(i!*j!*k!)
  2. An exam has 12 problems.  How many ways can (integer) points be assigned to the problems if the total is 100 and each problem worth 5 points?
    [Suppose the total is 100 and no restriction on the number of points.  Then we have 100 things being put in 12 categories, which is 111!/100!.  But we need to start with 5 in each category, so now we have just 40 points to distribute among the 12 categories.  This is 51!/40!]

 

Bicycles

  1. 100 distinct bikes in 4 distinct warehouses:  Each bike must go in a warehouse.  Step n.  Pick one of the 4 warehouses, n = 1 to100.  That’s 4^100.
  2. 100 indistinguishable bikes in 4 distinct warehouses.  Putting 100 things into 1 of 4 categories.  C(103,3)

 

Books

  1. 10 distinct books, divided among 3 students.  The first gets 5 books, the second gets 3 books, the third gets 2 books.  Line up the books; put a label on each book (the student’s name).  5 have the first name, 3 have the second name, 2 have the third name.  Strings 10 characters long.  C(10,5)*C(5,3)*C(2,2) = 10!/(5!*3!*2!)

 

Red, blue, and green balls

  1. Select 10 balls: 3 piles, 10 balls: C(12,2)
  2. Select 10 balls, including 1 red ball – 9 balls into 3 piles, C(11,2)
  3. Select 10 balls, including 1 red, 2 blue, 3 green: 4 balls into 3 piles: C(6,2)
  4. Select 10 balls, including exactly 1 red: select 1 red, then 9 balls into 2 piles: C(10,1)
  5. Select 10 balls, including exactly 1 red and at least one blue:
    1. Select a red
    2. Select a blue
    3. Select green or blue (8 balls) C(9,1)
  6. Select 10 balls, including at most 1 red:
    1. One red ball: 9 things into 2 piles C(10,1)
    2. No red balls: 10 things into 2 piles C(11,1)
  7. Select 10 balls, including twice as many red as green:
    1. 0 red, 0 green: 1
    2. 2 red, 1 green: 1
    3. 4 red, 2 green: 1
    4. 6 red, 3 green: 1

 

x1+x2+x3=15

  1. Each xi is greater than or equal to 0: 15 things into 3 piles = C(17,15)
  2. Each xi is greater than or equal to 1: 12 things into 3 piles = C(14,12)
  3. x1=1, x2 and x3 greater than or equal to 0: 14 things into 2 piles: C(15,14)
  4. x1>=0, x2>0, x3=1: 13 things into 2 piles: C(14,1) = 14
  5.  
  6. 0<=x1<6, 1<=x2<=8, x3>=0:  6*8 = 48
    There are 6 ways to choose x1 and 8 ways to choose x2.  Once you have chosen x1 and x2, you know the value of x3
  7.  
  8.  
  9. Number of solutions of x1 + … + xn <=M
    Same as the number of solutions for x1+…+xn+xn+1 = M, which is putting M things into n+1 piles: C(M+n, n)