How many times is the string 10001000 counted in the erroneous argument given in Example 6.2.23?
Like the Fibona pected places (eg. Ever! Section 7.11. Our next example illustrates a common en objects more than once. Example 6.2.23 What is wrong with the following argument, which purports to show that there are SOLUTION We can construct bit strings of length 8 by filling each of eight slots C18512' bit strings of length 8 containing at least five o's2 with either 0 or 1. To ensure that there are at least five O's, we choose five slots and place a 0 in each of them. The five slots can be chosen in C(8, 5) ways. We then fill the remaining three slots with either 0 or 1. Since each of the three remaining slots can be filled in two ways, the remaining slots can be filled in 2 ways. Thus there are C(8.52 bir strings of length 8 containing at least five o's. The problem is that some strings are counted more than one time. For example, suppose that we choose the first five slots and place 0's in them 0 0 0 0 0 If we then place 0 1 0 in the last three slots, we obtain the string (6.2.1) 0 0 0 0 0 0 1 0 Now suppose that we choose the second through sixth slots and place 0's in them 0 0 0 0 0 If we then place in the first slot and 10 in the last two slots, we obtain the string 0 0 0 0 0 0 1 0 (6.2.2) In the argument given, strings (6.2.1) and (6.2.2) are counted as distinct strings. A correct way to count the bit strings of length 8 containing at least five O's is to count the number of strings containing exactly five O's, the number of strings containing exactly six o's, the number of strings containing exactly seven O's, and the number of strings containing exactly eight 0's and sum these numbers. Notice that here each string Like the Fibona pected places (eg. Ever! Section 7.11. Our next example illustrates a common en objects more than once. Example 6.2.23 What is wrong with the following argument, which purports to show that there are SOLUTION We can construct bit strings of length 8 by filling each of eight slots C18512' bit strings of length 8 containing at least five o's2 with either 0 or 1. To ensure that there are at least five O's, we choose five slots and place a 0 in each of them. The five slots can be chosen in C(8, 5) ways. We then fill the remaining three slots with either 0 or 1. Since each of the three remaining slots can be filled in two ways, the remaining slots can be filled in 2 ways. Thus there are C(8.52 bir strings of length 8 containing at least five o's. The problem is that some strings are counted more than one time. For example, suppose that we choose the first five slots and place 0's in them 0 0 0 0 0 If we then place 0 1 0 in the last three slots, we obtain the string (6.2.1) 0 0 0 0 0 0 1 0 Now suppose that we choose the second through sixth slots and place 0's in them 0 0 0 0 0 If we then place in the first slot and 10 in the last two slots, we obtain the string 0 0 0 0 0 0 1 0 (6.2.2) In the argument given, strings (6.2.1) and (6.2.2) are counted as distinct strings. A correct way to count the bit strings of length 8 containing at least five O's is to count the number of strings containing exactly five O's, the number of strings containing exactly six o's, the number of strings containing exactly seven O's, and the number of strings containing exactly eight 0's and sum these numbers. Notice that here each string
