Problem: In a sequence of coin tosses, one can keep a record of instances in which a tail is immediately followed by a head, a head is immediately followed by a head, and etc. We denote these by TH, HH, and etc. For example, in the sequence TTTHHTHTTTHHTTH of 15 coin tosses we observe that there are two HH, three HT, four TH , and five TT subsequences. How many different sequences of 15 coin tosses will contain exactly two HH, three HT, four TH, and five TT subsequences? Solution: This is a beautifully logical problem. After thinking about what limitations you can impose on the string sequence of length $15$, you may notice a few things. For one, any valid string has exactly $9$ Ts and $6$ $H$s. you may come to believe that the string starts with $T$ and ends with $H$. Let's prove it. Assume, for the sake of a contradiction, that the string ends with $T$. Then, we can write our string as [A]HT[B]HT[C]HT[D]T. Notice that there cannot be a $H$ in [D], otherwise, we have more than three HT. So, $H$ must go in [A], [B], or [C] and for similar reasoning as before, in each of [A], [B], and [C], we must have all $T$s procede all $Hs (otherwise there will be more than three HT). This immediately implies that there are at most three TH, a contradiction. So, the string ends with $H$. Assume, for the sake of a contradiction, that the string starts with $H$. Then, our string looks like H[A]HT[B]HT[C]HT[D]H. Notice that there cannot be a $T$ in [A] since otherwise we have more than thre HT. We directly find that there can be at most 3 TH, a clear contradiction. So, the string starts with $T$. We now catergorize our string and it looks like T[A]HT[B]HT[C]HT[D]H. In each of [A],[B],[C],[D], there will be a number of $T$s (potentially zero up to $5$) followed by a number of $H$s (potentially zero up to $2$), and any arbitrary placement will specify a valid string. So we count the distributions with $\binom{5+4-1}{4-1}\binom{2+4-1}{4-1} = \binom{8}{3}\binom{5}{3} = 560$.