Out of $n$ coin flips, how many sequences have no $2$ consecutive heads?

Question

Suppose I flip a coin $n$ times. I want to calculate the number of all possible sequences of heads/tails such that I don't have two consecutive heads. For example, when $n = 3$, I have $5$ such sequences: $TTT$, $HTT$, $HTH$, $TTH$, $THT$.

My solution. We can have $k$ heads and $n-k$ tails, with $0 \leq k \leq n/2$ for $n$ even, and $0 \leq k \leq [n/2]+1$ if $n$ is odd.

Now for each $k$, there are $\frac{n!}{k!(n-k)!}$ ALL possible sequences (including consecutive heads).

At this point I am stuck - out of $\frac{n!}{k!(n-k)!}$ choices, how do I pick the ones that don't have two or more consecutive heads?

I would also appreciate it if you could point out a reference / general method for approaching such arrangement problems. This question is of my own device, so I don't know how easy or complicated the solution must be.

Answer 1

Here is an approach based upon generating functions. We start considering words with no consecutive equal letters at all.

These words are called Smirnov words or Carlitz words. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.)

A generating function for the number of Smirnov words over a two letter alphabet $\{H,T\}$ is given by \begin{align*} \left(1-\frac{2z}{1+z}\right)^{-1}\tag{1} \end{align*}

Generating function: $A(z)$

Since there are no restrictions to the tails $T$ at all, we replace occurrences of $T$ in a Smirnov word by any runs of $T$'s with length $\geq 1$. \begin{align*} z&\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z}\tag{2}\\ \end{align*}

We obtain by substituting (2) in (1) a generating function $A(z)=\sum_{n=0}^\infty a_nz^n$ \begin{align*} \color{blue}{A(z)}&=\left(1-\frac{z}{1+z}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}\\ &\color{blue}{=\frac{1+z}{1-z-z^2}}\tag{3}\\ \end{align*} with $a_n$ giving the number of all valid sequences of length $n$ having no $H$-runs of length $2$.

Recurrence relation:

From (3) we derive a recurrence relation of the coefficients $a_n$ of $A(z)=\sum_{n=0}^\infty a_nz^n$ from which we derive the wanted number $a_n, n\geq 0$.

At first we clear the denominator \begin{align*} A(z)&=\frac{1+z}{1-z-z^2}\\ \left(1-z-z^2\right)A(z)&=1+z\\ \left(1-z-z^2\right)(a_0+a_1z+a_2z^2+\cdots)&=1+z\tag{4}\\ \end{align*}

We obtain from (4) by coefficient comparison \begin{align*} \color{blue}{a_n-a_{n-1}-a_{n-2}}&\color{blue}{=0\qquad n \geq 2}\tag{5}\\ \color{blue}{a_0}&\color{blue}{=1}\\ \color{blue}{a_1}&\color{blue}{=2} \end{align*}

We get from the recurrence relation the numbers $(a_n)_{n\geq 0}=(1,2,3,5,8,13,21,\ldots)$ and see $a_n=F_{n+1}$, with $F_n$ the $n$-th Fibonacci Number.

In terms of the generating function $A(z)$ we have \begin{align*} A(z)=\frac{1+z}{1-z-z^2}=1+2z+3z^2+5z^3+8z^4+\color{blue}{13}z^5+21z^6+\cdots \end{align*}

Example: We consider the number $a_5=F_6\color{blue}{=13}$ the number of all valid sequences of length $5$. We obtain $$ \begin{array}{cccccc} HTHTH&THTHT&TTHTH&TTTHT&TTTTH&TTTTT\\ HTHTT&THTTH&TTHTT\\ HTTHT&THTTT\\ HTTTH\\ HTTTT\\ \end{array} $$