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: |
|||
|
(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
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 |
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
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
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.
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
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
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
|
|
|
|
|
|
|
|
|