a) In this part the permutation 5,6,32,7, for example, is to be counted. since it contains the consecutive
numbers 5, 6, and 7 in their correct order (even though separated by the 32). In order to specify such a
4-permutation, we first need to choose the 3 consecutive integers. They can be anything from {I, 2, 3} to
{98, 99, 100}; thus there are 98 possibilities. Next we need to decide which slot is to contain a number not
in this set; there are 4 possibilities. Finally, we need to decide which of the 97 other positive integers not
exceeding 100 is to fill this slot, and there are of course 97 choices. Thus our first attempt at an answer gives
us, by the product rule, 98· 4 . 97.
Unfortunately, this answer is not correct, because we have counted some 4-permutations more than once.
Consider the 4-permutation 4. 5. 6. 7, for example. We cannot tell whether it arose from choosing 4, 5, and 6
as the consecutive numbers, or from choosing 5, 6, and 7. (These are the only two ways it could have arisen.)
In fact, every 4-permutation consisting of 4 consecutive numbers. in order, has been double counted. Therefore
to correct our count, we need to subtract the number of such 4-permutations. Clearly there are 97 of them
(they can begin with any number from 1 to 97). Further thought shows that every other 4-permutation in our
collection arises in a unique way (in other words, there is a unique subsequence of three consecutive integers).
Thus our final answer is 98·4·97 - 97 = 37.927.
b) In this part we are insisting that the consecutive numbers be consecutive in the 4-permutation as well.
The analysis in part (a) works here, except that there are only 2 places to put the fourth number-in slot 1
or in slot 4. Therefore the answer is 98·2·97 - 97 = 18,915.
