No three tails

Probability Level 5

There are 13 ways to toss a fair coin 4 times so that tails never comes up three times in a row.

How many ways are there to toss a fair coin 12 times so that tails never comes up three times in a row?

The answer is 1705.

2 solutions

Mark Hennings
Apr 3, 2016

In view of Patrick's comments below, I now give an alternative derivation. Let $Z_n$ be the number of sequences of length $n$ which do not contain $TTT$ anywhere. Then $Z_1 = 2$ , $Z_2 = 4$ , $Z_3 = 7$ and $Z_n \; = \; Z_{n-1} + Z_{n-2} + Z_{n-3} \;, \qquad \qquad n \ge 4 \;,$ where we obtain this recurrence relation by spltting up the sequences into those that start with $H$ , those that start with $TH$ , and those that start with $TTH$ . Then $Z_{12} = \boxed{1705}$ .

Let $X_n$ be the number of sequences of length $n$ that can be built from the sequence elements $H$ , $TH$ and $TTH$ . Then $X_0 = 1$ , $X_1 = 1$ , $X_2 = 2$ and $X_n \; = \; X_{n-1} + X_{n-2} + X_{n-3} \qquad \qquad n \ge 3 \;,$ counting the sequences by considering which sequence element is used first. Thus the terms $X_n$ can be determined inductively.

For any $N \ge 3$ and any $3 \le n \le N$ , let $Y_{N,n}$ be the number of sequences of length $N$ which do contain the subsequence $TTT$ , and for which the subsequence $TTT$ first occurs at positions $n-2,n-1,n$ . The first $n-3$ terms of such a sequence must be built up from the elements $H$ , $TH$ and $TTH$ , since $TTT$ cannot occur within the sequence, and the $(n-3)$ rd term must be $H$ , in order to ensure that $TTT$ occurs for the first time in positions $n-2,n-1,n$ . The last $N-n$ terms of such a sequence can be chosen freely. Thus $Y_{N,n} \; = \; X_{n-3} \times 2^{N-n} \qquad \qquad 3 \le n \le N \;,$ Since the number of sequences containing the subsequence $TTT$ is the sum of $Y_{N,n}$ for $3 \le n \le N$ , it follows that $2^N - \sum_{n=3}^N Y_{N,n} \; = \; 2^N - \sum_{n=3}^N 2^{N-n}X_{n-3}$ is the number of sequences of length $N$ which do not contain the subsequence $TTT$ . For $N=4$ this gives the answer $13$ . For $N=12$ this gives the answer $\boxed{1705}$ .

Hmm, is it a coincidence that the answer is just $X_{n-1}?$ Seems like this could be simplified with the right argument. Maybe instead of using the "building blocks," you could note that the same recurrence is satisfied by the number of sequences with no three tails, by the same inductive argument about what they start with.

Patrick Corn - 5 years, 2 months ago

$X_{n+1}$ , not $X_{n-1}$ , I think, since $X_4=7$ is the number of TTT-free sequences of length $3$ . Your argument is much better, though. The recurrence relation, of course, works for TTT-free sequences of length $n$ ; we just need to change the initial conditions.

Mark Hennings - 5 years, 2 months ago

We could use principle of inclusion and exclusion.

Indraneel Mukhopadhyaya - 5 years, 2 months ago

My method used the recursive relation a n=2a (n-1)-2^(n-4) where a 3=7. Can someone explain where I went wrong. My method gave me 1280.

Sal Gard - 5 years, 2 months ago

I think you want the recurrence relation $a_n \; = \; 2a_{n-1} - a_{n-4}$ (not $2^{n-4}$ ). This works, with $a_0 = 1, a_1 =2, a_2 =4,a_3=7$ .

To get a $TTT$ -free sequence of length $n$ , start with a $TTT$ -free sequence of length $n-1$ . You can then add either $H$ or $T$ to the end, except when the length $n-1$ sequence ends $TT$ . Thus $a_n \; = \; 2a_{n-1} - b_{n-1}$ where $b_{n-1}$ is the number of $TTT$ -free sequences of length $n-1$ which end $TT$ . But all such sequences are obtained from a $TTT$ -free sequence of length $n-4$ , followed by $HTT$ , and hence $b_{n-1} = a_{n-4}$ . Thus we obtain the recurrence relation at the start.

Mark Hennings - 5 years, 2 months ago

@Mark Hennings – Thanks this makes sense. I'm glad I was on the right track.

Sal Gard - 5 years, 2 months ago

Using Patrick's argument shouldn't we split up the sequences into those starting with $H$ , $TH$ and $TTH$ instead of $T$ , $HT$ and $HHT$ ?

Also is there any way to find a closed form expression of this recurrence relation ? (I had to do it manually)

Nitish Joshi - 5 years, 2 months ago

I believe you are right about your first question.

For the second question, the answer is yes, but it's fairly ugly and requires some complex numbers, namely two of the three roots of the polynomial $x^3-x^2-x-1.$ See the tribonacci sequence wiki for some details. There are formulas for large $n$ that are not in the wiki, involving the nearest integer to powers of the tribonacci constant times another constant.

Anyway, in practice, doing it manually will probably be fastest!

Patrick Corn - 5 years, 2 months ago

Oops. Corrected.

As Patrick says, there is no nice closed formula. There are general techniques for solving recurrence relations like this. Recurrence relations can be regarded as discrete versions of differential equations, and many of the techniques that can be used to solve some types of differential equation yield analogous technqiues.

If we consider the recurrence relation $X_{n+k} + a_{k-1}X_{n+k-1} + a_{k-2}X_{n+k-2} + \cdots + a_1X_{n+1} + a_0X_n = 0$ (where $a_{k-1},\ldots, a_0$ are constants) then we note that $X_n = \lambda^n$ will be a solution provided that $\lambda^{n+k} + a_{k-1}\lambda^{n+k-1} + \cdots + a_1\lambda^{n+1} + a_0\lambda^n = 0$ for all $n$ , and hence provided that $\lambda^k + a_{k-1}\lambda^{k-1} + \cdots + a_1\lambda + a_0 = 0 \;. \qquad \qquad (\star)$ In general there will be $k$ distinct roots $\lambda_1,\lambda_2,\ldots,\lambda_k$ of this polynomial equation, yielding a general solution $X_n \; = \; A_1\lambda_1^n + A_2\lambda_2^n + \cdots + A_k\lambda_k^n$ of the recurrence relation, for arbitrary constants $A_1,\ldots,A_k$ . (You should recognise this as being like solving homogeneous differential equations with constant coefficients.)

If $\lambda$ is a double root of $(\star)$ , its contribution to the solution becomes $(A+Bn)\lambda^n$ . If $\lambda$ is a triple root of $(\star)$ , its contribution becomes $(A+Bn+Cn^2)\lambda^n$ . Similarly for higher levels of multiplicity. (Again, the analogy with differential equations is clear.)

If the recurrence relation is nonhomogeneous (so $(\star)$ ends with " $= \mathrm{something}$ " instead of just $0$ ), find a particular integral, and add the general solution of the homogeneous equation. (Analogous techniques to those used to find particular integrals for differential equations will work here as well)

However, since the recurrence relation of this problem yields the moderately unpleasant (i.e., without elegant factors) cubic $X^3 - X^2 - X - 1 = 0$ ,. there is no particular gain to solving the recurrence relation exactly when we are only interested in the first few terms.

Mark Hennings - 5 years, 2 months ago

Thanks a lot!

Nitish Joshi - 5 years, 2 months ago

Adwait Godbole
Apr 5, 2016

I have a direct solution (without considering cases of negation).

Note that the ways of tossing and of $H$ and $T$ have a bijection with each other.

Let ${ t }_{ 2 }^{ n }, { t }_{ 1 }^{ n }, { t }_{ 0 }^{ n }$ represent the allowable sequences ending with 2,1 and 0 consecutive tails respectively.

We have:

${ t }_{ 2 }^{ n } = { t }_{ 1 }^{ n-1 }$ ...(i)
${ t }_{ 1 }^{ n } = { t }_{ 0 }^{ n-1 }$ ...(ii)

The above two results can be shown by considering that we can append a $T$ to the end of the $n-1$ length chain to create an $n$ length chain with one more consecutive $T$ at the end.

Now let $W_{n}$ denote the total number of acceptable sequences.

Now, we have:

${ t }_{ 0 }^{ n } = W_{n-1}$ ...(iii)

(By appending an $H$ to the end of any acceptable sequence and removing $H$ from end of any (acceptable) sequence ending with $H$ ... bijection can be proved)

Also (obviously):

$W_{n} = { t }_{ 0 }^{ n } + { t }_{ 1 }^{ n } + { t }_{ 2 }^{ n }$

Thus, we can show:

$W_{n} = W_{n-1} + W_{n-2} + W_{n-3}$ ...by (i), (ii), (iii)

No three tails

The answer is 1705.

2 solutions

0 pending reports