Problem:
In a sequence of coin tosses one can keep a record of the number of instances when a tail is immediately followed by a head, a head is immediately followed by a head, etc. We denote these by , etc. For example, in the sequence of coin tosses we observe that there are five , three , two and four subsequences. How many different sequences of coin tosses will contain exactly two , three , four and five subsequences?
Solution:
Think of such sequences of coin tosses as progressions of blocks of and 's, to be denoted by and , respectively. Next note that each and subsequence signifies a transition from to and from to , respectively. Since there should be three of the first kind and four of the second kind in each of the sequences of coin tosses, one may conclude that each such sequence is of the form
Our next concern is the placement of 's and 's in their respective blocks, so as to assure that each sequence will have two and five subsequences. To this end, we will assume that each block in initially contains only one member. Then, to satisfy the conditions of the problem, it will suffice to place more 's into the 's and more 's into the 's. Thus, to solve the problem, we must count the number of ways this can be accomplished.
Recall that the number of ways to put indistinguishable balls (the extra 's and 's in our case) into q distinguishable boxes (the 's and 's, distinguished by their order in the sequence) is given by the formula . (Students who are not familiar with this fact should verify it.) In our case, it implies that the 's can be placed in the 's in or ways, and the 's can be placed in the 's in or ways. The desired answer is the product, , of these numbers.
The problems on this page are the property of the MAA's American Mathematics Competitions