Generating function with tough restrictions

Question

In how many ways can a coin be flipped $25$ times in a row so that exactly $5$ heads occur and no more than $7$ tails occur consecutively?

For the heads, I think that it is $\binom{25}{5}$, but I do not know what to do with the tails restriction.

Not sure how to approach this problem. It is from the advanced section in the generating functions chapter in my book.

Answer 1

The right terms to think of are the lengths of the sequences of tails. We have six of them - one before we flip any heads, one between the first head and the second, one between the second and third, and so on until the last sequence after the fifth head. Each of these sequences can be of length $0$, $1$, $2$, $3$, $4$, $5$, $6$, or $7$.

Can you set up a generating function for this now?

Answer 2

This answer is based upon the Goulden-Jackson Cluster Method.

We consider the set words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{H,T\}$$ and the set $B=\{TTTTTTTT\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^n$ being the number of searched words of length $n$.

According to the paper (p.7) the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=|\mathcal{V}|=2$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[TTTTTTTT]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[T^8])&=-s^8-s\cdot \text{weight}(\mathcal{C}[T^8])-\cdots-s^7\cdot\text{weight}(\mathcal{C}[T^8])\tag{1}\\ \end{align*}

and get \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[T^8])=-\frac{s^8(1-s)}{1-s^8} \end{align*}

It follows

\begin{align*} f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2s+\frac{s^8(1-s)}{1-s^8}}\tag{2}\\ &=\frac{1+s^8}{1-2s+s^9}\\ &=1 + 2 s + 4 s^2 + 8 s^3 + 16 s^4 +\cdots+\color{blue}{32\,316\,160}s^{25}+\cdots\\ \end{align*}

The last line was calculated with the help of Wolfram Alpha. The coefficient of $s^{25}$ shows that out of $2^{25}=33\,554\,432$ words of length $25$ from the alphabet $\{H,T\}$ there are $\color{blue}{32\,316\,160}$ words which do not contain the word $TTTTTTTT$.

But we also want to keep track of the number of heads and tails. In order to do so we make a refinement of $f(s)$ by marking the heads with $x$ and the tails with $y$. We obtain from (1) \begin{align*} \text{weight}(\mathcal{C}[T^8])&=-(ys)^8-(ys)\text{weight}(\mathcal{C}[T^8])-\cdots-(ys)^7\text{weight}(\mathcal{C}[T^8]) \end{align*} and get \begin{align*} \text{weight}(\mathcal{C})=-\frac{(ys)^8(1-ys)}{1-(ys)^8}\tag{2} \end{align*}

Using this generalized weight we obtain from (2) a generating function $g(s;x,y)$ \begin{align*} g(s;x,y)&=\frac{1}{1-(x+y)s+\frac{(ys)^8(1-ys)}{1-(ys)^8}}\\ &=1+(x+y)s+(x+y)s^2+(x+y)^3s+\cdots\\ &\qquad+(x^{25} + 25 x^{24} y + 300 x^{23} y^2 + 2\,300 x^{22 }y^3 +\cdots+\color{blue}{ 17\ 892} x^5 y^{20} \\ &\qquad\qquad+ 2\,010 x^4 y^{21} + 84 x^3 y^{22})s^{25}+\cdots\tag{3} \end{align*}

We finally conclude from (3) there are $\color{blue}{ 17\ 892}$ words of length $25$ which contain exactly $5$ heads and do not contain more than $7$ consecutive tails.

Answer 3

So you have $5$ H and a total of $20$ T that you have to place in $6$ batches, before the first and after each H.
Each batch may be void, but cannot exceed a length of 7.

So we are looking for $$N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right.$$ with $s=20,\; r=7,\;m=6$

Now it turns out that $N_b$ is expressible as $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$ as widely explained in this post.

Also there it is explained that the relevant o.g.f. is $$ F_b (x,r,m) = \sum\limits_{0\,\, \leqslant \,\,s\,\,\left( { \leqslant \,\,r\,m} \right)} {N_b (s,r,m)\;x^{\,s} } = \left( {1 + x + \cdots + x^{\,r} } \right)^m = \left( {\frac{{1 - x^{\,r + 1} }}{{1 - x}}} \right)^m $$

So it is just a matter to insert the values for $s,r,m$ , to get $17892$.

Answer 4

More generally, we might ask how many sequences of flips of length $n$ have $m$ heads and no more than seven tails in a row. We will find a bivariate generating function for this problem.

First suppose we drop the constraint that the sequence must contain exactly $m$ heads, retaining the requirement that there be no more than seven tails in a row; let's say such a sequence is "acceptable". Let $f(z)$ be the generating function for the number of acceptable sequences of length $n$. An acceptable sequence consists of a sequence of zero to seven tails, or a sequence of zero to seven tails followed by a head, followed by an acceptable sequence. In terms of the generating function,this translates to $$f(z) = (1+z+z^2+ \dots +z^7) (1 + z f(z))$$ We can insert a "marker" for the head in this equation and convert the generating function into a bivariate generating function where the number of acceptable strings of length $n$ with $m$ heads is the coefficient of $u^m z^n$: $$f(u,z) = (1+z+z^2+ \dots +z^7) (1 + uz f(u,z))$$ Noting that $1+z+z^2+ \dots +z^7 = (1-z^8)/(1-z)$, we can solve the preceding equation for $f(u,z)$: $$f(u,z) = \frac{(1-z^8)/(1-z)}{1-uz(1-z^8)/(1-z)}$$

In a sense this bivariate generating function is the general solution, but let's see if we can find the answer to the original problem, which is the coefficient of $u^5 z^{25}$ in $f(u,z)$. We start by expanding $f(u,z)$ as a series in $u$. $$f(u,z) = \frac{1-z^8}{1-z} \sum_{i=0}^{\infty} z^i \left( \frac{1-z^8}{1-z} \right)^i u^i$$ The coefficient of $u^5$ is $$\begin{align} [u^5] f(u,z) &= \frac{1-z^8}{1-z} z^5 \left( \frac{1-z^8}{1-z} \right)^5 \\ &= z^5 (1-z^8)^6 (1-z)^{-6} \\ &= z^5 (1 - 6z^8 + 15 z^{16} - O(z^{24})) \sum_{i=0}^{\infty} \binom{6+i-1}{i} z^i \end{align}$$ From this last equation we see that the coefficient of $u^5 z^{25}$ is $$[z^{25}][u^5]f(u,z) = \binom{6+20-1}{20} -6 \binom{6+12-1}{12} + 15 \binom{6+4-1}{4} = \boxed{17,892}$$