278
Sets, Combinatorics, and Probability
There are C(19, 1) ways to choose 1 freshman. Once a freshman has been selected,
that guarantees that at least 1 freshman will be on the committee, so we are free to
choose the remaining 7 members of the committee from the remaining 52 people
without any restrictions, giving us C(52, 7) choices. By the multiplication principle, this gives C(19, 1) # C(52, 7). However, this is a bigger number than the
correct answer.
The problem is this: Suppose Derek and Felicia are both freshmen. In one of
the choices we have counted, Derek is the one guaranteed freshman, and we pick
the rest of the committee in such a way that Felicia is on it along with 6 others. But
we have also counted the option of making Felicia the guaranteed freshman and
having Derek and the same 6 others be the rest of the committee. This is the same
committee as before, and we have counted it twice.
Practice 33 A committee of 2 to be chosen from 4 math majors and 3 physics majors must include at
least 1 math major. Compute the following 2 values.
a. C(7, 2) − C(3, 2) (correct solution: all committees minus those with no math majors)
b. C(4, 1) # C(6, 1) (bogus solution: choose 1 math major and then choose the rest of the committee)
The expression C(4, 1) # C(6, 1) − C(4, 2) also gives the correct answer because C(4, 2) is the number
of committees with 2 math majors, and these are the committees counted twice in C(4, 1) # C(6, 1).
■
ExamplE 57
a. How many distinct permutations can be made from the characters in the
word FLORIDA?
b. How many distinct permutations can be made from the characters in the
word MISSISSIPPI?
Part (a) is a simple problem of the number of ordered arrangements of seven
distinct objects, which is 7!. However, the answer to part (b) is not 11! because the
11 characters in MISSISSIPPI are not all distinct. This means that 11! counts some
of the same arrangements more than once (the same arrangement meaning that we
cannot tell the difference between MIS 1 S 2 ISSIPPI and MIS 2 S 1 ISSIPPI.)
Consider any one arrangement of the characters. The four S’s occupy certain
positions in the string. Rearranging the S’s within those positions would result in
no distinguishable change, so our one arrangement has 4! look-alikes. In order to
avoid overcounting, we must divide 11! by 4! to take care of all the ways of moving the S’s around. Similarly, we must divide by 4! to take care of the four I’s and
by 2! to take care of the two P’s. The number of distinct permutations is thus
11!
4!4!2!
In general, suppose there are n objects of which a set of n 1 are indistinguishable from each other, another set of n 2 are indistinguishable from each other, and
so on, down to n k objects that are indistinguishable from each other. The number
of distinct permutations of the n objects is
n!
(n 1 !)(n 2 !) c (n k !)
Sets, Combinatorics, and Probability
There are C(19, 1) ways to choose 1 freshman. Once a freshman has been selected,
that guarantees that at least 1 freshman will be on the committee, so we are free to
choose the remaining 7 members of the committee from the remaining 52 people
without any restrictions, giving us C(52, 7) choices. By the multiplication principle, this gives C(19, 1) # C(52, 7). However, this is a bigger number than the
correct answer.
The problem is this: Suppose Derek and Felicia are both freshmen. In one of
the choices we have counted, Derek is the one guaranteed freshman, and we pick
the rest of the committee in such a way that Felicia is on it along with 6 others. But
we have also counted the option of making Felicia the guaranteed freshman and
having Derek and the same 6 others be the rest of the committee. This is the same
committee as before, and we have counted it twice.
Practice 33 A committee of 2 to be chosen from 4 math majors and 3 physics majors must include at
least 1 math major. Compute the following 2 values.
a. C(7, 2) − C(3, 2) (correct solution: all committees minus those with no math majors)
b. C(4, 1) # C(6, 1) (bogus solution: choose 1 math major and then choose the rest of the committee)
The expression C(4, 1) # C(6, 1) − C(4, 2) also gives the correct answer because C(4, 2) is the number
of committees with 2 math majors, and these are the committees counted twice in C(4, 1) # C(6, 1).
■
ExamplE 57
a. How many distinct permutations can be made from the characters in the
word FLORIDA?
b. How many distinct permutations can be made from the characters in the
word MISSISSIPPI?
Part (a) is a simple problem of the number of ordered arrangements of seven
distinct objects, which is 7!. However, the answer to part (b) is not 11! because the
11 characters in MISSISSIPPI are not all distinct. This means that 11! counts some
of the same arrangements more than once (the same arrangement meaning that we
cannot tell the difference between MIS 1 S 2 ISSIPPI and MIS 2 S 1 ISSIPPI.)
Consider any one arrangement of the characters. The four S’s occupy certain
positions in the string. Rearranging the S’s within those positions would result in
no distinguishable change, so our one arrangement has 4! look-alikes. In order to
avoid overcounting, we must divide 11! by 4! to take care of all the ways of moving the S’s around. Similarly, we must divide by 4! to take care of the four I’s and
by 2! to take care of the two P’s. The number of distinct permutations is thus
11!
4!4!2!
In general, suppose there are n objects of which a set of n 1 are indistinguishable from each other, another set of n 2 are indistinguishable from each other, and
so on, down to n k objects that are indistinguishable from each other. The number
of distinct permutations of the n objects is
n!
(n 1 !)(n 2 !) c (n k !)