We flip a fair coin 12 times in a row and record the results of the flips. How many sequences of flips are there in which two heads do not follow each other?
I. Solution. We use the solution of problem B. 3858. published in KöMaL, which includes the following formula: if $n$ is the number of tosses, and $f$ is the number of heads, then the number of toss sequences in which no two of the $f$ heads are adjacent is $\binom{n-f+1}{f}$. (The derivation appeared in the May issue.)

In our case, $n=12$ (we toss $n$ times), and the number of heads is $f$, where $f=0,1, \ldots, 6$.

If $f=0$, then $\binom{12-0+1}{0}=1$. So if we get 0 heads, there is $1$ valid toss sequence.

If $f=1$, then $\binom{12-1+1}{1}=12$. So if we get 1 head, there are $12$ valid toss sequences. Similarly, with the values $\binom{12-2+1}{2}=55, \binom{12-3+1}{3}=120, \binom{12-4+1}{4}=126, \binom{12-5+1}{5}=56, \binom{12-6+1}{6}=7$, the total number of valid toss sequences is: $1+12+55+120+126+56+7=377$.

(If $f>6$, there are clearly no valid toss sequences.)

Therefore, there are 377 toss sequences in which no two heads are adjacent.

II. Solution. The first toss can be heads or tails (henceforth $f$ and $i$). Let's look at the valid toss sequences. According to the condition, $f$ can only be followed by $i$, and $i$ can be followed by both $f$ and $i$. Therefore, the number of cases increases at $i$.

The 12th row of the diagram shows the number of cases. In each row, there will be as many $i$ as there were $f$ and $i$ in the previous row, since $i$ can follow both $f$ and $i$. Thus, the number of cases in a row will increase by the number of elements in the row two steps back. This is called a Fibonacci sequence, where each element is the sum of the two preceding elements. After that, it is easy to calculate how many possibilities there will be in the 12th row: as many as the 12th term of the sequence 2, 3, 5, 8, 13, 21, 34, $55,89,144,233,377$, which is 377.
![](https://cdn.mathpix.com/cropped/2024_05_02_a2379ce886fb23168517g-1.jpg?height=218&width=552&top_left_y=1080&top_left_x=776)

Therefore, there are 377 toss sequences in which no two heads are adjacent.