Discrete Structures Problems
nohj666
week10.pdf
A. Doerr
1
Week 10
Permutations, Combinations and the Binomial Coefficient
The first part of section 6.3 in the text is on “permutations”. You may recall that back in
week 2 I asked you to do exercise 25 of this section using the Rule of Products. I
wanted to show you that every single “permutation problem” can done, in fact, more
easily, using the more natural counting technique, the Rule of Products. Permutations problems are just a subset of “Rule of Products” problems. Every problem
that the text does using "permutations” can just as easily (in fact easier) using the rule of
products. Try it!
However, There are problems where the Rule of Products technique applies
but the Permutation process cannot be used.
The Permutation Rule is given by Theorem 1
Example 1. How many three digit numbers can be formed using the 9 digits 1 through 9,
where repetition of digits is not allowed.
Method 1. Using the Rule of Products. The solution is 9 8 7 since there are 9 choices
for the first digit, 8 choices for the second digit and 7 for the third .
Method 2. The Permutation formula can also be used and the solution can be obtained
by a Corollary 1 of Theorem 1, section 6.3:
In general, where 0 ≤ r ≤ n we have P(n , r) =
n!
n - r !
So for this example
P(9,3) = 9! 9!
(9 3)! 6!
= 9 8 7.
Example 2. How many three digit numbers can be formed using the 9 digits 1 through 9,
where repetition of digits is allowed.
Method 1. Using the Rule of Products the solution is 9 9 9. Why?
Method 2. The Permutation formula cannot be used because repetition of digits is not
allowed using the Permutation formula. Notice in Theorem 1 the Permutation formula
applies only if we have “n distinct elements”. This says that repetition of digits is not
allowed
The second key counting technique of section 6.3 is the Combination Rule (Theorem 2).
Read this material carefully. For rule of product and permutation problems order or
arrangement is important. In fact the word to permute means to arrange, to order. A
A. Doerr
2
combination is an unordered listing. I explain the difference between an ordered listing
and an unordered list in the following two examples:
Example 3. Suppose that three different prizes (1 st prize $1,000 or 2
nd prize $500 or 3
rd
prize $100) are going to be awarded to three of the 6 finalists in a drawing. Assume that
a person can only win one prize.
(Note, I am assuming that it makes a difference which prize you are awarded.) How
many ways are there to award these prizes?
The 1 st prize can be awarded to any one of 6 people so there are 6 choices for the 1
st
prize. There are 5 people left so the 2 nd
prize can be awarded to any one of 5 people.
Next there are only 4 people left so there are 4 people to choose from to award prize 3.
Therefore, there are, by the rule of products 6 . 5
. 4 = 120 ways of awarding the three
prizes. Or, if you prefer to use the Permutation Rule the solution is P(6,3) which of
course equals 6 . 5
. 4 = 120 .
Example 4. Now suppose that three prizes are all the same prize. That is three $200
prizes will be awarded. Assume that a person can only win one prize. Here it does not
make any difference whether your name is the first name drawn for a prize or the second
or the third. All three receive the same prize. The ordering of the names drawn does not
make a difference.
The solution is: 6
3
= 20.
The r-Combinations Rule is given by Theorem 2. This rule is similar to the Permutation
rule and makes use of the formula C(n, r) = n!
r! n-r !
The Binomial Theorem is defined by Theorem 1 in section 2.4. Several properties of this
theorem can be found as corollaries in the text.
Here’s a problem that you did in week 2 using the Rule of Products. It is worth studying
again.
Example 5. An ice cream parlor advertises that you may have your choice of five
different toppings, and you may choose none, one, two, three, four, or all five toppings.
How many choices are there in all?
Solution. Method 1. Using the Rule of Products that we first studied in week 2. For
each topping you have 2 choices. Either accept the topping or not. Therefore we have
25 choices.
Method 2. Using combinations. We want the number of different ways to
select either 0, 1, 2, 3, 4, or 5 toppings from a total of 5 possibilities. We assume that it
A. Doerr
3
does not make any difference which topping goes on first or second etc. Also, when we
say “we want the number of different ways to select 0, 1, 2, 3, 4, or 5 elements from a
total of 5” we mean we must select either 0 toppings OR 1 topping OR 3 toppings and so
on we cannot select 2 toppings and also 3 toppings at the same time. We must do one or
the other. So the SUM rule applies. So this problem involves both the sum rule and the
combination rule. You should take five minutes to compute each of the summands
0
5
,
1
5 , . . ,
5
5 and note that they form a palindrome (read the same forwards as
backwards). Why? See section 6.4, the Binomial Theorem and Binomial Coefficients
and Pascal’s triangle.
0
5 +
1
5 +
2
5 +
3
5 +
4
5 +
5
5 = 25
Example 6. A woman wants to invite 5 of her 9 close friends for dinner.
(a) How many ways can she do this with no restrictions? Since we are selecting 5 people out of 9 without ordering the solution is:
9 9! 9 8 7 6 5 4 3 2 1 9 8 7 6
5 5! 9 5 ! (5 4 3 2 1)(4 3 2 1) (4 3 2 1)
= 126
(b) How many ways can she do this if two of her friends do not like each other? If she invites one of them she cannot invite the other.
Let’s call the two people who do not like each other person a and person b.
Situation 1. If she selects person a for dinner she cannot select person b.
The selection of person a leaves only 4 people to select out of 7 (a was selected
and b can’t be) to make up the 5 for dinner. This can be done 7
4
ways.
Situation 2. This is simply the “flip-flop” of the above. If she selects person b for
dinner she cannot select person a. This can be done 7
4
ways.
Situation 3. She invites neither person a nor person b. Here she must invite 5 out
of the remaining 7 friends. This can be done 7
5
ways.
So the solution for part (b) is: 7
4
+ 7
4
+ 7
5
or 2 7
4
+ 7
5
. Can you
explain why this is the solution? You should work out the details
A. Doerr
4
(c) How many ways can she do this if two of her friends are a couple? If she invites one of them she must invite the other. There are two situations here:
Situation 1. She invites the couple. This can be done 7
3
ways, Why?
Situation 2. She doesn’t invite the couple. This can be done 7
5
ways, Why?
Example 7. Suppose each single character stored in a computer uses eight bits. Then
each character is represented by a different sequence of eight 0s and is called a bit
pattern.
(a) How many different bit patterns contain exactly 3 ones? Before you solve the problem you may want to write several bit patterns that contain 3 ones.
Since if we decide to put ones in the first , third and seventh places it does not
make any difference if we put a 1 in the 7 th
place first and then in the 1 st place and
finally in the 3 rd
place. The ordering of placing the 1’s is immaterial so the
Combination Rule applies so the number bit patterns that contain exactly 3 ones is
8
3
.
(b) How many different bit patterns contain at least 3 ones? To contain at least 3 ones means to contain 3 ones or 4 ones or . . . or 8 ones. This can be done
8
3
+ 8
4
+ 8
5
+ . . . +
8
8
ways. You should be able to explain this. Can this
problem be done another way?
Read and study the rest of section 6.3 and 6.4 and do the assignments from this
sections.
Here are some additional problems if you feel you need more practice.
15. The Green Lawn Tennis Club has scheduled a round-robin tennis tournament in which
each player plays one match against every other player. If 12 players are signed up for
the tournament, how many matches have been scheduled? ans = 66
16. Suppose that a 9-member committee is to vote on an amendment. How many different
ways can the votes be cast so that the amendment passes by a simple majority? (A
simple majority means 5 or more yes votes.)
17. In Exercise 16, how many different favorable ways can the votes be case if the
amendment needs at least a 2/3 majority? ans = 130
A. Doerr
5
18. A certain shirt comes in four sizes and six colors. One also has the choice of a
dragon, an alligator, or no emblem on the pocket. How many different shirts can you
order?
ans = 72
19. A builder of modular homes would like to impress his potential customers with the
variety of styles of his houses. For each house he has blueprints for three different living
rooms, four different bedroom configurations, and two different garage styles. In
addition, the outside can be finished in cedar shingles or brick. How many different
houses can be designed from these plans?
20. An automobile dealer has several options available for each of three different
packages of a particular model car: a choice of two styles of seats in three different
colors, a choice of four different radios, and five different exteriors. How many choices
of automobile does a customer have?
21. A clothing manufacturer has put out a mix-and-match collection consisting of two
blouses, two pairs of pants, a skirt, and a blazer. How many outfits can you make? Did
you consider that the blazer is optional? How many outfits can you make if the
manufacturer adds a sweater to the collection?
22. (a) Suppose each single character stored in a computer uses eight bits. Then each
character is represented by a different sequence of eight 0s and is called a bit pattern.
How many different bit patterns are there? (That is, how many different characters could
be represented?)
(b) How many bit patterns are palindromes (the same backwards as forwards)?
(c) How many different bit patterns have an even number of 1s?
23. Automobile license plates in Massachusetts usually consist of three digits followed
by three letters. The first digit is never zero. How many different plates of this type
could be made?
24. How many integers from 100 to 999 can be written with no 7s?
25. How many ways can a student do a ten-question true-false exam if he or she can
choose not to answer any number of questions?
26. If a raffle has three different prizes and there are 1,000 raffle tickets sold, how many
different ways can the prizes be distributed?
(a) How many three-digit numbers can be formed from the digits 1,2, 3 if no
repetition of digits is allowed? List the three-digit numbers.
(b) How many two-digit numbers can be formed if no repetition of digits is
allowed? List them.
(c) How many two-digit numbers can be obtained if repetition is allowed?
27. The state finals of a high school track meet involves fifteen schools. How many
A. Doerr
6
ways can these schools be listed in the program?
28. (a) How many ways can the coach of Tall U. fill the five starting positions on a
basketball team if each of his 15 players can play any position?
(b) What is the answer if the center must be one of two people?
29. The judiciary committee at a college is made up of three faculty members and four
students. If ten faculty members and 25 students have been nominated for the committee,
how many judiciary committees are possible?
30. Suppose that a single character is stored in a computer using eight bits.
(a) How many bit patterns have exactly three 1s?
(b) How many bit patterns have at least two 1s?
31. There are ten points P1,…, P10 on a plane, no three on the same line.
(a) How many lines are determined by the points?
(b) How many triangles are determined by the points?
More Counting problems (Some from The Magic of Numbers by Gross)
Example 8. Suppose that you are playing scrabble and you have in your rack the letters
“E, E, E, E, N, N, N”. How many ways are there of arranging these tiles in your rack?
That is, how many seven-letter words (strings of length 7 of these letters) can be formed
that contain exactly four Es and three Ns?
This problem is simple. To determine or write any seven-letter word with these
letters all we have to specify which of the 4 places the Es are to fill (or equivalently
which of the 3 places the Ns are to fill). 7 7
35 4 3
Example 9. work
home
Suppose we live in a city where the streets are arrayed in a rectangular grid as above.
How many different paths from home to work can we take? For example, using N for
north and E for east one path is E, E, N, E, N, N, E. That is, we need seven moves that
A. Doerr
7
contain exactly four Es and three Ns. This is the above problem so the answer is 35 as in
example 8.
In general if we have a k by l rectangular grid the number of different paths from the
lowest left corner to the top right corner is k l
k
.
Example 10. Home
School
(a) Consider the grid above. How many paths of shortest possible length are there from the point labeled “school” to the point labeled “home”?
Solution: As above, any path from the point “school” to the point “home” will
contain a total of 13 N’s (north) and E’s (east). We have a 5 blocks north (N’s) and 8
blocks east (E’s). So we only have to specify which of the 5 places (of the 13) we
wish to fill with N’s (the directions north), 13
5
. Or we could specify which of the
13 places we could specify the easterly direction, 13
8
. In either case the answer is
1,287.
(b) Now suppose, a student going from school to home must first go to work, which is at the point indicated by the circle. How many paths are there of minimum
length going from school to home stopping at work? Is the following correct?
6 7
4 4
or
6 7
2 3
or ?
A. Doerr
8
(c) Now suppose that you have called in sick at work and you do not want to drive through that intersection. How many paths are there from school to home
omitting that intersection?
Example 11. Assume that your job as a senior on campus is to assign students to dorm
rooms. Assume you have nine students to assign to rooms and the rooms are a quad, a
triple and a double. How many ways can you make the assignments?
Solution, 9 5
1, 260 4 3
. Why? But wait, what if you assigned the rooms in a
different order? That is, assigned 2 students to the double first and the 4 to the quad and
the remaining 3 to the triple? 9 7
2 4
. Is the answer the same? Let’s look at both
results again.
9 5 9! 5! 9!
4 3 4!5! 3!2! 4!3!2!
9 7 9! 7! 9!
2 4 2!7! 4!3! 4!3!2!
.
This type of problem appears frequently and deserves more thought. In each of the
above, we had 9 students which we wanted to assign to three rooms so we assign the first
group of students to one room (the quad) the second group to a second room (the triple)
and the remaining students to the only room left (a double).
In general if we have a number n and three numbers a, b, and c that add up to n, the
number of ways of distributing n objects into 3 collections of sizes a, b and c is !
! ! !
n
a b c .
This number is called a multinomial coefficient and it is denoted by the symbol , ,
n
a b c
.
That is, !
, , ! ! !
n n
a b c a b c
. This is Theorem 4 in section 5.5.
The derivation of the multinomial coefficient formula is as follows:
We first choose which “a” of our “n” objects go into the first group. This can be done
!
!( )!
n n
a a n a
ways. Next, we choose which “b” of the remaining n – a objects go in
the second group. This can be done ( )!
!( )!
n a n a
b b n a b
ways. The remaining c
A. Doerr
9
objects go into the third group. This can be done in only one way. So by the product rule
we have:
! ( )! 1
!( )! !( )!
n n a n n a
a b a n a b n a b
Note “the remaining c objects”
is n - a – b = c. So the above
becomes.
! ( )!
!( )! ! !
n n a
a n a b c
!
! ! !
n
a b c .
Fill in the following blank: The number of ways of distributing n objects into groups of
sizes a1, a2, a3, a4, …, ak is _______________
The number is called a multinomial coefficient and it is denoted by the symbol , ,
n
a b c
.
The number !
, , ! ! !
n n
a b c a b c
is called a multinomial coefficient since it a coefficient
of a multinomial.
Example 12. For example we know that if to expand the trinomial (x + y + z) 6 to
multiply
(x + y + z) (x + y + z) (x + y + z) (x + y + z) (x + y + z) (x + y + z). One of the terms of
this expansion is x 2 y z
3 . Note the powers of the x, y and z add up to 6. Will this always
happen for this expansion? The coefficient of the term x 2 y z
3 is
6!
1!2!3! . This is so since
we are doing exactly what we did above, namely, choose x from 2 factors, y from a
different factor and z from the remaining 3 factors or 6!
2!1!3! =
6!
1!2!3! .
What is the coefficient of x 1 y z
4 in the above expansion?
