2D  Step Methods


We have studied the multiplication and addition principles of combinatorics, as well as ways of counting permutations and combinations. Now it is time to put everything together and tackle problems requiring more than one of these tools at once. Often a seemingly complicated problem can be easily solved by breaking it down into a series of small steps, each of which requires just a simple application of one of our basic methods. The examples will illustrate the technique.


example 1

The PTA of Haleiwa School has 20 active members. How many ways can the association choose a president, a secretary, and 3 members of the planning committee? (Assume no person holds more than one position.)

We divide the problem into a series of steps which, when performed in order, will accomplish the designated task of choosing the officers:


PTA meeting

Step 1 - select a President : 20 ways

Step 2 - select a Secretary : 19 ways

Step 3 - select a planning committee : C(18,3) = 816 ways


(By now you should know how to calculate expressions like C(18,3) and P(8,5) - so we will skip such details from here on.)

Remember that before doing calculations for a step, we assume the preceding steps have already been completed. Thus in step 2 we assume the president has been chosen, so there are only 19 candidates for secretary; likewise in step 3 there are only 18 candidates because a president and secretary have been chosen. By the multiplication principle the number of ways of completing all three steps is


20 · 19 · 816 = 310,080  .




example 2

chickens

Elmo, a generous person, has 9 chickens. For Christmas he will give 3 chickens to his parents, 2 to his Auntie, and 1 to his brother. How many ways can Elmo distribute the chickens?

There are three steps that Elmo may follow:


Step 1 - give 3 chickens to parents : C(9,3) = 84 ways

Step 2 - give 2 chickens to Auntie : C(6,2) = 15 ways

Step 3 - give 1 chicken to brother : C(4,1) = 4 ways


Note that in step 2 there are only 6 chickens to choose from, since 3 have already been given away, and then in step 3 there are only 4 chickens remaining. The number of Elmo's possibilities is the product


18 · 15 · 4 = 5,040  .




example 3

humuhumunukunukuapuaa

humuhumunukunukuapuaa

How many ways can you arrange the letters in the word

 

(a)  

EAT

 

(b)  

EGG

 

(c)  

KALALAU

 

(d)  

KAMEHAMEHA

 

(e)  

HUMUHUMUNUKUNUKUAPUAA


In (a) we are counting the number of permutations of 3 distinct letters, so the number of ways is 3! = 6. In fact, we can quickly list the 6 possibilities:


EAT    ETA    AET    ATE    TEA    TAE  .


In (b) there are fewer arrangements because the letters are not distinct - if we interchange the two G's we get the same arrangement! Experimentation reveals only three different arrangements:


EGG       GEG       GGE  .


We can solve this problem systematically by breaking it into steps; we think of the letters as fitting into three slots:






Step 1 is to locate a slot for the letter E - there are 3 possible ways. Step 2 then is to locate 2 slots for the two G's - since there are only two slots left there is only one way. By the multiplication principle, the number of possible arrangements is 3 · 1 = 3.


For the word KALALAU we require 7 slots, and 4 steps because there are 4 different letters:


Step 1 - choose 1 slot for the K : C(7,1) = 7 ways


 

 

K

 

 

 

 









Step 2 - choose 3 slots for the A's : C(6,3) = 20 ways


 

A

K

 

A

 

A










Step 3 - choose 2 slots for the L's : C(3,2) = 3 ways


L

A

K

L

A

 

A









Step 4 - choose 1 slot for the U : C(1,1) = 1 way


L

A

K

L

A

U

A









Note that in each step the number of available slots goes down as more slots are filled. The number of possible arrangements is the product


C(7,1) · C(6,3) · C(3,2) · C(1,1) = 7 · 20 · 3 · 1 = 420  .


For KAMEHAMEHA there are 10 slots, and the letter K appears once, A appears 3 times, and M, E, and H all appear twice. The calculations are


C(10,1) · C(9,3) · C(6,2) · C(4,2) · C(2,2) = 10 · 84 · 15 · 6 · 1 = 75,600  .


You can check that the calculations for HUMUHUMUNUKUNUKUAPUAA are


C(21,2) · C(19,9) · C(10,2) · C(8,2) · C(6,2) · C(4,3) · C(1,1) = 1,466,593,128,000  .


(About one and a half trillion - don't try to write them all down!)




example 4

commission

Five Democrats, 4 Republicans, and 3 Independents have been nominated for the Land Use Commission. The governor intends to select 2 Democrats, 2 Republicans, and 1 Independent. How many ways can she make her choices?

The steps are


Step 1 - select 2 Democrats : C(5,2) = 10 ways

Step 2 - select 2 Republicans : C(4,2) = 6 ways

Step 3 - select 1 Independent : C(3,1) = 3 ways  .


Thus the governor's options number 10 · 6 · 3 = 180.




example 5

poker hand

From a standard deck of 52 cards, how many ways can you get a poker hand (5 cards) consisting of

(a)  3 kings and 2 queens?

(b)  4 aces and one other card?

(c)  2 queens, 1 jack, and 2 numerical cards?

(d)  5 cards of the same suit?


In (a) there are C(4,3) = 4 ways of getting 3 kings, then C(4,2) = 6 ways of getting 2 queens; the product is 4 · 6 = 24.


In (b) there is C(4,4) = 1 way of getting 4 aces, then C(48,1) = 48 ways of getting the fifth card; the product is 1 · 48 = 48.


In (c) there are C(4,2) = 6 ways of getting 2 queens, then C(4,1) = 4 ways of getting a jack, and finally C(40,2) = 780 ways of getting 2 numerical cards; the product is 6 · 4 · 780 = 18,720.


Part (d) is a little different from the preceding questions. In order to get 5 cards of the same suit, you must perform one of four tasks - namely,


Task 1 - get 5 spades : C(13,5) = 1,287 ways

Task 2 - get 5 hearts : C(13,5) = 1,287 ways

Task 3 - get 5 diamonds : C(13,5) = 1,287 ways

Task 4 - get 5 clubs : C(13,5) = 1,287 ways  .


But since you will be performing only one of these tasks, the addition principle applies; the number of possibilities is the sum


1,287 + 1,287 + 1,287 + 1,287 = 5,148  .




example 6

Four women and three men are to be seated in a row of seven chairs.


7 people sitting

How many possible seating arrangements are there if

(a)  there are no restrictions?

(b)  women and men are to alternate?

(c)  the tallest woman and the tallest man are to sit on the end chairs?

(d)  the women are to sit together and the men are to sit together?

(e)  the women are to sit together, but there is no restriction on the men?


In (a) the answer is 7! = 5040, the number of permutations of 7 objects.


In (b) we must seat the women in the four alternating chairs beginning with an outside chair; there are 4! = 24 ways. Then we must seat the men in the 3 remaining chairs, in one of 3! = 6 ways. The number of arrangements therefore is 24 · 6 = 144.


In (c) we do the seating in 3 steps:


Step 1 - seat the tallest woman on an end chair : 2 ways

Step 2 - seat the tallest man on the other end : 1 way

Step 3 - seat the remaining 5 people in the 5 middle chairs : 5! = 120 ways


The product is 2 · 1 · 120 = 240 ways.


In (d) first we seat the women. They can sit in either the four chairs on the left or the four chairs on the right; then the men must sit in the three remaining chairs. The steps are


Step 1 - choose 4 chairs for the women : 2 ways

Step 2 - seat the 4 women in their 4 chosen chairs : 4! = 24 ways

Step 3 - choose 3 chairs for the men : 1 way

Step 4 - seat the 3 men in these 3 chairs : 3! = 6 ways


The number of possible arrangements is 2 · 24 · 1 · 6 = 288.


In (e) again we seat the women first. Since the men do not have to sit together there are now more places to sit for the women. They can sit in the four leftmost chairs, or the second through fifth chairs, or the third through sixth chairs, or the four rightmost chairs. The steps are


Step 1 - choose 4 chairs for the women : 4 ways

Step 2 - seat the 4 women in their 4 chosen chairs : 4! = 24 ways

Step 3 - seat the 3 men in the 3 remaining chairs : 3! = 6 ways


The product in this scenario is 4 · 24 · 6 = 576.




example 7

dance couple

From a dance class of 5 males and 4 females, how many ways can the teacher form 3 couples to dance the two-step?

This question is different from our previous couple-forming problems, because now not all females will be chosen and likewise not all males will be chosen. We divide the problem into three steps:


Step 1 - select 3 males : C(5,3) = 10 ways

Step 2 - select 3 females : C(4,3) = 4 ways

Step 3 - match these chosen males and females : 3! = 6 ways .


The number of ways of forming 3 couples is 10 · 4 · 6 = 240.




example 8

girl on horse

Farmer Brown has 8 horses, 4 sons, and 2 daughters. He intends to choose 2 sons and 1 daughter, set each upon a horse, and line them up for a picture. How many possible pictures are there?

Here are the steps:


Step 1 - choose 2 sons : C(4,2) = 6 ways

Step 2 - choose 1 daughter : C(2,1) = 2 ways

Step 3 - choose 3 horses : C(8,3) = 56 ways

Step 4 - set these 3 kids upon these 3 horses : 3! = 6 ways

Step 5 - line them up for a picture : 3! = 6 ways


The number of possible pictures is the product


6 · 2 · 56 · 6 · 6 = 24,192 .





EXERCISES 2D


basketball game
  1. From a basketball team of 8 players, how many ways can the coach select two guards, two forwards, and one center to start the game?

  2. A class has 9 students. How many ways can the teacher assign
    1. 7 grades of "pass" and 2 of "not pass"?
    2. 1 A, 2 B's, 3 C's, 2 D's, and 1 F?

  1. lunch
    The Kaimuki Diner has a really good lunch special. For $4.95 you can choose 1 meat from a choice of beef, pork, or chicken, then 2 vegetables from a choice of 6, and soup or salad from a choice of 3 soups and 5 salads.
    1. How many ways can you order lunch?
    2. What would be the answer if you could order soup and salad?

card game
  1. In a poker hand of 5 cards, how many different hands are there containing
    1. 2 aces and 3 face cards?
    2. 2 clubs, 2 hearts, and 1 diamond?
    3. 3 black cards and 2 red cards?
    4. 1 king, 1 queen, 1 jack, and 2 aces?
    5. 2 even numbers and 3 red face cards?

  1. A play requires 2 women to play Lucy and Ethel, and 2 men to play Desi and Fred. If 5 women and 4 men audition, how many ways can the roles be cast?


  2. 9 young women
    How many ways can 9 young women be lined up for a picture, if Alice insists on standing in the middle and Betty insists on standing on an end?


  3. Nine women will travel to the North Shore in a Ford, a Honda, and a Toyota. If 3 women ride in each car, how many ways can the 9 women be distributed in the 3 cars?

  4. How many ways can you arrange the letters in the word
    1. ALOHA
    2. KAKAAKO
    3. MENEHUNE
    4. MISSISSIPPI ?

pig show
  1. This weekend is the 4-H fair pig show. The judge will award 1 champion purple ribbon, 2 blue ribbons, 2 red ribbons, and 1 white ribbon. How many ways can the 6 ribbons be awarded to the pigs if
    1. only 6 pigs are entered?
    2. 7 pigs are entered?

  2. There are 11 French courses that Beth has not yet taken. How many ways can she choose 2 French courses to take the fall semester and 3 to take the spring semester?

  1. yellow car
    A family of 2 parents and 3 children will go for a ride in a car with 2 seats in front and 3 in the back. How many ways can the family be seated in the car if
    1. the parents sit in the front and the children in the back?
    2. the parents sit in the front, the children in the back, and the mother drives?
    3. the mother drives and the father sits in the back?
    4. one parent drives and the other parent sits in the back?

newly married couple
  1. A town has 8 single young men and 5 single young women.

    1. If next Sunday each of the young women marries an eligible young man from the town, in how many ways can that be accomplished?
    2. If only 4 of the young women marry an eligible young man next Sunday, in how many ways can that be accomplished?
    3. If 2 young men marry an eligible young woman next Sunday, in how many ways can that be accomplished?
    4. If only one couple gets married next Sunday, in how many ways can that be accomplished?

  1. newly married couple
    How many ways can 4 cookbooks and 2 sewing books be lined up on a shelf, if

    1. there are no restrictions?
    2. the sewing books are to be in the middle?
    3. the cookbooks are to be together and the sewing books together?
    4. the sewing books are to be together?
handshake
  1. Three Republicans and 4 Democrats attend a legislative meeting. How many handshakes are there if
    1. everyone shakes hands with everyone?
    2. each Republican shakes hands with each Democrat?
    3. each Republican shakes hands with each Republican, and each Democrat shakes hand with each Democrat?

    rabbits
  1. A pet shop has 3 white rabbits, 4 black rabbits, 5 gray rabbits, and 6 brown rabbits. How many ways can the owner choose

    1. one rabbit of each color for his window display?
    2. two rabbits of each color for his window display?
    3. two rabbits of the same color to sell to Mrs. Cho?
    4. two gray rabbits, 3 brown rabbits, and 1 white rabbit to sell to Mr. Park?


  2. Ann, Bessie, Cathy, Debbie, Elvis, and Frank will sit in a row of six chairs.

    chairs

    How many ways can they select seats if
    1. a female is to sit at the extreme left?
    2. the two males are to sit on the ends?
    3. the males are to sit together and the females together?
    4. the males are to sit together?
    5. Ann and Bessie are to sit together on an end?
    6. Frank is to sit between two females?


  3. In a family of 2 parents, 3 girl children, and 2 boy children, how many ways can the mother select

    1. 3 children to clean the yard?
    2. 1 boy and 2 girls to clean the yard?
    3. 1 family member to wash dishes and 2 to dry dishes?
    4. 1 parent to wash dishes, and a boy and a girl to dry dishes?
    5. 1 parent to wash dishes, and a parent and a child to dry dishes?
    6. 1 parent or 2 girls to clean the rug?
    dishwasher
    dishdryer
    1. 2 girls or 2 boys to wash the car?
    2. 1 parent, or 2 boys, or 2 girls, to set the table?
    3. a parent, or a boy and a girl, to wash the car?
    4. 2 girls and 1 boy and 1 parent to go shopping?
    5. 1 parent to wash dishes, 2 girls to dry dishes, and another parent or a boy to sweep the floor?
    6. 1 parent to wash dishes, and 2 girls or 2 boys to dry dishes?

  4. bags
    Keoni, packing for his trip to Denver, finds that he has 6 clean shirts and 5 clean pairs of pants. How many ways can he choose
    1. 5 shirts and 3 pairs of pants to take on his trip?
    2. 3 shirts and 2 pairs of pants for his larger bag, and 2 shirts and 1 pair of pants for his smaller bag?

  5. From a dance class of 5 men and 6 women, how many ways can the instructor choose
    high-stepping dancers
    1. one couple to dance the samba, and a second to dance the rhumba?   
    2. two couples to dance the samba?
    3. two couples to dance the samba, and a third to dance the rhumba?
    4. two couples for the samba, and two more couples for the rhumba?
    latin dancers

  6. cowgirl
    A Big Island rancher has 5 horses, 4 daughters, 3 sons, and 6 ten-gallon hats each of a different color. He will choose 2 daughters and 2 sons, give each a ten-gallon hat, set each upon a horse, and then line up the four horses for a picture. How many possible pictures are there if
    1. there are no further restrictions?
    2. sons and daughters are to alternate in the picture?
    3. the two daughters will be in the middle of the picture, one wearing the black hat and the other the white hat?