Section 5-5-Generalized Permutations and Combinations - Discrete Mathematics and Its Applications

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.5—Generalized Permutations and Combinations

p.373, icon at Example 4

#1. A jar contains 30 pennies, 20 nickels, 20 dimes, and 15 quarters. (The coins of each denomination are considered to be identical.)

(a) Find the number of ways to put all 85 coins in a row.
(b) Find the number of possible handfuls of 12 coins.

Solution:

(a) The answer is not 85! because not all the coins are distinct. Think of the problem as one of taking 30 p’s, 20 n’s, 20 d’s, and 15 q’s, and putting these letters in a row. Taking into account the identical letters,

we have 85! / 30! · 20! · 20! · 15! .

(b) The number of handfuls of 12 coins is equal to the number of nonnegative integer solutions to the equation p + n + d + q = 12.

The number of solutions to this equation is C(15, 3) = 455.

p.373, icon at Example 4

#2. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose:

(a) at least 3 chocolate cookies and at least 6 peanut butter cookies.
(b) exactly 3 chocolate cookies and exactly 6 peanut butter cookies.

Solution:

We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.

(a) We must have c ≥ 3 and p ≥ 6. Picture yourself in the bakery with an empty bag in which you will place 30 cookies. Put into the bag three chocolate cookies and six peanut butter cookies. The bag now has nine cookies in it, so you need to place 21 more cookies into the bag. You have met the two conditions, so you do not care about the numbers of each of the four types you choose for the remaining 21 cookies.
Therefore, you need to find the number of nonnegative integer solutions to the equation c + j + s + p = 21.

The number of nonnegative integer solutions to this equation is C(24, 3). Therefore there are C(24, 3) = 2,024 ways to buy 30 cookies with at least 3 chocolate cookies and at least 6 peanut butter cookies.

(b) We must have c = 3 and p = 6. Picture yourself in the bakery with an empty bag in which you will place 30 cookies. Put into the bag three chocolate cookies and six peanut butter cookies. The bag now has nine cookies in it, so you need to place 21 more cookies in to the bag, but you cannot select more chocolate or peanut butter cookies. Therefore you need to find the number of nonnegative integer solutions to the equation j + s = 21.

The number of nonnegative integer solutions to this equation is C(22, 1) = 22. Therefore there are 22 ways to buy 30 cookies with exactly 3 chocolate cookies and exactly 6 peanut butter cookies.


p.373, icon at Example 4

#3. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose at most 5 sugar cookies.

Solution:

We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.

To solve the problem, we use “complement counting”. That is, we find the number of possible bags of 30 cookies with more than 5 sugar cookies, and then subtract that number from the total number of bags of 30 cookies. That is, we find the number of solutions to c + j + s + p = 30 with s ≥ 6. This is the number of solutions to the equation c + j + s + p = 24, which equals C(27, 3).

Thus, the answer to the question is the total number of nonnegative integer solutions to the equation c + j + s + p = 30, C(33, 3), with C(27, 3) subtracted: (total number of solutions) − (number of solutions with s ≥ 6) = C(33, 3) − C(27, 3) = 2,531.

p.373, icon at Example 4

#4. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose at least one of each of the four types of cookies.

Solution:

We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.

To “see” the solution, take an empty bag and place in it one cookie of each of the four types. This leaves 26 more cookies to be selected and there are no additional restrictions on the cookies. This yields the equation c + j + s + p = 26. The number of nonnegative integer solutions to this new equation is C(29, 3) = 3,654.


p.375, icon at Example 7

#1. In how many ways can the letters in DECEIVED be arranged in a row?

Solution:

The word has two D’s, three E’s, one C, one I, and one V. Therefore, the number of permutations of DECEIVED is 8! / (2! · 3! · 1! · 1! · 1!) = 8! /( 2! · 3!) = 3,360.


p.375, icon at Example 7

#2. In how many ways can 7 of the 8 letters in CHEMISTS be put in a row?

Solution:

There are two patterns to consider:
(a) seven distinct letters are selected (that is, only one S is selected), and
(b) the two S’s are selected.
In the first pattern, there are 7! ways to put the 7 distinct letters in a row.
In the second pattern, we select the two S’s and use all but one of the six other letters. For example, we could use the letters S,S and C,H,E,M,T, or S,S and C,H,E,M,I. Each of these sets of seven letters can be put in a row in 7!/2 ways. There are 6 ways to choose five of the six letters that are not S’s; therefore, there are 6 · 7!/2 ways to have the second pattern.

Adding the totals obtained from the two cases, we have the total number of ways to put seven of the eight letters in a row is 7! + 6 · (7!/2!) = 20,160.

p.376, icon after start of ”Distributing Objects into Boxes” subsection

#1. Four players are playing bridge. In how many ways can they be dealt hands of cards? (In bridge, a hand of cards consists of 13 out of 52 cards.)

Solution:

This is a problem of placing 52 distinguishable objects (the cards) in four distinguishable piles of size 13 (one pile for each of the four players). This can be done is 52! / 13!·13!·13!·13! ways.

p.376, icon after start of ”Distributing Objects into Boxes” subsection

#2. In how many ways can ten books be put in four labeled boxes, if one or more of the boxes can be empty? Assume that the books are:
(a) distinct.
(b) identical.

Solution:

(a) Each book can be placed in any of the four boxes. By the product rule, this can be done in 410 ways.
(b) Let xi be the number of books in box i. We need to find the number of nonnegative integer solutions to the equation x1 + x2 + x3 + x4 = 10. There are C(13, 3) such solutions.

Section 5.3 Permutations and Combinations - Discrete Mathematics and Its Applications-Extra Examples

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.3—Permutations and Combinations


p.355, icon at Example 1
#1. A class has 30 students enrolled. In how many ways can:
(a) four be put in a row for a picture?
(b) all 30 be put in a row for a picture?
(c) all 30 be put in two rows of 15 each (that is, a front row and a back row) for a picture?


Solution:
(a) We need to fill in the following row of four blanks: . This can be done in 30 · 29 · 28 · 27 ways.
This is the number of 4-permutations from a set of 30, which is P(30, 4).


(b) The answer can be visualized as the number of ways to fill in a row of 30 blanks with the 30 students,
which is 30!, or P(30, 30).


(c) The answer can be visualized as the number of ways to fill in two rows, each with 15 blanks, with the 30 students:
We can begin by filling in the bottom row, which can be done in 30 · 29 · 28 · . . . · 17 · 16 ways. Then we fill in the top row, which can be done in 15 · 14 · 13 · . . . · 2 · 1 ways. Therefore the answer is  (30 · 29 · 28 · · · 17 · 16) · (15 · 14 · 13 · · · 2 · 1) = 30 ! .




p.355, icon at Example 1
#2. A class has 20 women and 16 men. In how many ways can you
(a) put all the students in a row?
(b) put 7 of the students in a row?
(c) put all the students in a row if all the women are on the left and all the men are on the right?


Solution:
(a) There are 36 students. They can be put in a row in 36! ways.


(b) You need to have an ordered arrangement of 7 out of 36 students. The number of such arrangements is P(36, 7).


(c) You need to have an ordered arrangement of all 20 women AND and ordered arrangement of all 16 men.
By the product rule, this can be done in 20!·16! ways.




p.360, icon at Example 12
#1. A certain type of push-button door lock requires you to enter a code before the lock will open. The lock has five buttons, numbered 1, 2, 3, 4, 5. The lock is programmed to recognize six different 4-digit codes, with repeated digits allowed in each code. How many different sets of recognizable codes are there?


Solution:
There are 5^4 = 625 possible four-digit codes. Therefore, there are C(625, 6) different sets of six codes that the lock can be programmed to recognize.




p.360, icon at Example 12
#2. Several states play a lottery game called Mega Millions. On a Mega Millions lottery game ticket, you pick a set of five numbers from the numbers 1 through 56 on the top panel of the ticket, and one number (the Mega Ball number) from 1 through 46 on the bottom half of the ticket. (The Mega Ball number can be the same as one of the five numbers picked on the top half of the ticket.) A set of six winning numbers is selected: five numbers from 1 through 56 and one Mega Ball number from the numbers 1 through 46. You win a prize if your selections match some or all of the winning numbers, as follows: five and Mega Ball, five and no Mega Ball, four and Mega Ball, four and no Mega Ball, three and Mega Ball, three and no Mega Ball, two and Mega Ball, one and Mega Ball, only the Mega Ball.
Find the number of ways in which you can have one ticket with
(a) five winning numbers, but no Mega Ball.
(b) two winning numbers and the Mega Ball.


Solution:
(a) The number of ways in which all five numbers can be chosen correctly is C(5, 5) = 1 and the number of ways of choosing a number other than the Mega Ball is C(45, 1) = 45. Therefore, the number of ways to choose five numbers and miss the Mega Ball is C(5, 5)· C(45, 1) = 45.


(b) The number of ways in which exactly two of the five numbers can be chosen correctly is C(5, 2)· C(51, 3) — you choose two of the five winning numbers and three of the 51 losing numbers. The number of ways of choosing the Mega Ball is C(1, 1). Therefore, the number of ways to choose exactly two winning numbers and the Mega Ball is C(5, 2)· C(51, 3)· C(1, 1) = 208, 250.




p.360, icon at Example 12
#3. How many ways are there to choose a committee of size five consisting of three women and two men from a group of ten women and seven men?


Solution:
The number of ways to choose three women is C(10, 3) and the number of ways to choose two men is C(7, 2). Using the product rule to choose three women and two men, the answer is C(10, 3) · C(7, 2) = 2, 520.


Note: The answer is not C(17, 5) (which counts all committees of size five) because this ignores that fact that the committees must have exactly three women and exactly two men. Also, the answer is not C(10, 3) + C(7, 2), which is a commonly made mistake. This says that you are choosing either three women or two 2men; it does not count committees of size five.




p.360, icon at Example 12
#4. Let S = {1, 2, . . . , 19}. Find the number of subsets of S with equal numbers of odd integers and even integers.


Solution:
Note that there are 10 odd integers and 9 even integers in S. The subsets to be counted must consist of k odd integers and k even integers, where k = 1, 2, 3, . . . , 9. Therefore, by the product rule, the number of each type is C(10, k)· C(9, k). Therefore, by the sum rule the answer is
C(10, 0) · C(9, 0) subsets with 0 odd and 0 even + C(10, 1)· C(9, 1) subsets with 1 odd and 1 even + C(10, 2)· C(9, 2)m subsets with 2 odd and 2 even + · · · + C(10, 9)· C(9, 9) subsets with 9 odd and 9 even = 92,377.
or 
C(10, 0) · C(9, 0)  + C(10, 1)· C(9, 1) + C(10, 2)· C(9, 2) + · · · + C(10, 9)· C(9, 9) = 92,377.




p.360, icon at Example 12
#5. Find the number of words of length 10 of letters of the alphabet, with no repeated letters, such that each word has equal numbers of vowels and consonants.


Solution:
Visualize a row of ten blanks. Each word of length 10 must contain all five vowels and five of the 21 consonants. There are different ways to solve this problem.
Here is one way to solve the problem. Choose a set of five of the ten blanks for the vowels. Then place the five vowels in these positions. These two steps can be done in C(10, 5)· 5! ways. Next, choose 5 consonants from the 21 consonants, and place them in the remaining five blanks. These two steps can be done in C(21, 5)· 5! ways. Thus, the number of ways of forming the desired words by placing the vowels and consonants is C(10, 5)·5!·C(21, 5)·5! = (10!/5!5!)·5!·(21!/5!16!)·5! =10!21!5!16!= 10·9·8·7·6·21·20·19·18·17 = 73,842,451,200.


Here is a second way to approach the problem. Choose any set of five consonants, and form a set consisting of these five consonants and the five vowels. These ten letters can be arranged in 10! ways, each of which forms one of the words we are counting. But there are C(21, 5) ways to choose the five consonants. Therefore, there are C(21, 5) · 10! = 10·9·8·7·6 · 21·20·19·18·17 words.
Here is a third way to approach the problem. First, place the five vowels in five of the ten blanks (10 choices for A, 9 choices for E, etc.) — this can be done in 10·9·8·7·6 ways. Then place five of the 21 consonants in the five remaining blanks (21 choices for the first blank, 20 choices for the second blank, etc.) — this can be done in 21·20·19·18·17 ways. Therefore, by the product rule, the number of words with the five vowels and five consonants is 10·9·8·7·6 · 21·20·19·18·17.




p.360, icon at Example 12
#6. Find the number of ways to take an ordinary deck of 52 playing cards and break it into:
(a) four equal piles, labeled A, B, C, D.
(b) four equal piles that are not labeled.


Solution:
(a) Each pile must have 52/4 = 13 cards in it. In sequence, we form pile A, then pile B, then pile C, and finally pile D. There are C(52, 13) ways to obtain pile A, C(39, 13) ways to obtain pile B, C(26, 13) ways to obtain pile C, and C(13, 13) = 1 way to obtain pile D. Therefore, by the product rule the answer is 
C(52, 13)· C(39, 13)· C(26, 13)· C(13, 13) = (52!/13! · 39!)·(39!/13! · 26!)·(26!/13! · 13!)·(13!/13! · 0!) = 52!/(13!)^4.


(b) If the four piles are not labeled, there is no distinction to be made among piles A, B, C, D. We can permute these in 4! ways. Hence the answer is the answer to part (a) divided by 4!:
(C(52, 13)· C(39, 13)· C(26, 13)· C(13, 13))/4! = 52! / ((13!)^4)· 4!).




p.360, icon at Example 12
#7. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T consists of two odd numbers and three even numbers.


Solution:
There are 13 odd numbers; we can choose two in C(13, 2) ways. There are 12 even numbers; we can choose three in C(12, 3) ways. Using the product rule to find the number of elements in T , we have C(13, 2) · C(12, 3) =17,160 subsets.




p.360, icon at Example 12
#8. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T consists of exactly three prime numbers.


Solution:
(b) The prime numbers in S are 2, 3, 5, 7, 11, 13, 17, 19, and 23, and there are C(9, 3) ways to select three


of them. But we also need to select two of the 16 composite numbers to make T have size five; there are C(16, 2) ways to this. Therefore, the product rule gives C(9, 3) · C(16, 2) = 10,080 possible subsets T .




p.360, icon at Example 12
#9. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T has the sum of its elements less than 18.


Solution:
There are very few subsets with this property. It is easiest in this case to count directly the set of five numbers whose sum is less than 18: 1, 2, 3, 4, 5, 1, 2, 3, 4, 6, 1, 2, 3, 4, 7, 1, 2, 3, 5, 6. Thus, there are four such subsets.




p.360, icon at Example 12
#10. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T has at least one even number in it.


Solution:
It is easiest to count the total number of subsets of size five, and then subtract the number of subsets with no even numbers in them: C(25, 5) − C(13, 5) = 51,843.
Note: When you need to count objects that have a certain property, a good problem solving strategy to consider is “complement counting” — count the total number of objects in the universe and then subtract the number of objects that fail to have the desired property.