Set Decomposition Principle 429Final Result:
(# Choices) = (# Choices for subproblem 1) + (# Choices subproblem 2)
+ (# Choices subproblem 3)
=6.7+6.5+7.5=107 U
Example 6 introduces a very useful strategy for counting problems. The strategy in-
volves breaking a problem into a number of subcases, each of which can be solved inde-
pendently. The insights that are needed to see how to break a problem into subproblems
can be developed by examining the solutions of similar problems and then attempting to
solve other similar problems.7.3.1 Counting the Complement
To count the number of objects in a subset of a class of objects that have a common prop-
erty, you can begin by counting all the objects in the class. Then, you can count the number
of objects in the class that do not have the required property. The difference between these
two counts is the number of objects in the subset that have the property in question.
Example 7. How many 3-strings or words with three letters have a letter repeated if the
words are formed from {a, b, c, d, e)?
Solution. It is easier to determine this count indirectly. We will count the total number
of 3-strings possible and the total number of 3-strings with no repeated letters. The answer
will be the difference between these two counts.
There are five possibilities for each of the letter positions in forming an arbitrary word.
By the Multiplication Principle, there are 53 words in all. For the words with distinct letters,
the first position can be filled with any of the five letters, the second position with any of
the four remaining letters after the first letter is chosen, and the third position with any
of the three remaining letters after the first two choices are made. By the Multiplication
Principle, this gives 5 • 4 • 3 possible words with all letters distinct:
(# Words with repeated letters) = (# Words) - (# Words with distinct letters)=53 - 5 .4. 3
=65 U
The same idea of counting the complement will tell us how many functions are not
1-1. It would not be as easy to do this count directly as it would have been with the previous
example.Example 8. Let S = {a, b, c, d, e} and T = [ 1, 2, 3, 4, 5, 6}. How many functions from
S to T are not 1-1?
Solution. The general class of objects to count is the number of functions from S to T.
The second count that is needed determines how many of these functions are 1-1. The
answer is the difference between these two counts:
(# Functions) = (# Possible images of a) • (# Possible images of b)
... (# Possible images of e)