Bernoulli's Coin Flipping

We can solve it recursively:

Let $a_n$ be the number of sequences possible for n results. That sequence can end with either 'H' or 'T'.

Suppose it ends with 'T', we can represent it as: $a_{n-1}T$

If it ends with 'H', it would have a constraint that there must be 'TT' before 'H' and it can be represented as: $a_{n-3}TTH$

Therefore, the recursive solution can be written as:

$a_n = a_{n-1}+a_{n-3}$ with $a_0=1, a_1=2, a_2=3$

From this, we can find that $a_{12}= \fbox{129}$

Let f(N) = Number of sequences made out of {H,T} with length N that satisfy the conditions.

Then f(1)=2, f(2)=3.

Let N>2. The first letter of the sequence can be T or H. If T, it can be followed by any valid sequence of length N-1. If H, it has to be followed by TT and then by any valid sequence of length N-3.

Hence f(N)=f(N-1)+f(N-3)

Using the base case and recurrence, we obtan f(12)=129

Let $a_n$ be the number of ways Bernoulli could get a string of $n$ coin flips with no "HH" or "HTH" substrings. Let's call such strings "valid strings"

.

Case 1: First flip is a H.

If the 2nd flip is a H, then we have "HH", which is not allowed.

If the 2nd flip is a T and the 3rd flip is a H, we have "HTH", which is not allowed.

If the 2nd flip is a T and the 3rd flip is a T, we have "HTT", after which, we may append any valid string of $n-3$ coin flips. There are $a_{n-3}$ such strings.

This exhausts all possibilities in Case 1.

.

Case 2: First flip is a T.

We have "T", after which, we may append any valid string of $n-1$ coin flips. There are $a_{n-1}$ such strings.

This exhausts all possibilities in Case 2.

.

Thus, the total number of valid strings of length $n$ is $a_n = a_{n-1}+a_{n-3}$ .

Since "" is the only (valid) string of length $0$ , we have $a_0 = 1$ .

Since "H" and "T" are both valid strings of length $1$ , we have $a_1 = 2$ .

Since "HT", "TH", and "TT" are valid strings of length $2$ , but "HH" is not, $a_2 = 3$ .

.

Using the recursive equation with initial values yields: $a_3 = 4$ , $a_4 = 6$ , $a_5 = 9$ , $a_6 = 13$ , $a_7 = 19$ , $a_8 = 28$ , $a_9 = 41$ , $a_{10} = 60$ , $a_{11} = 88$ , $a_{12} = 129$ .

Therefore, the number of valid sequences of length $12$ is $a_{12} = \boxed{129}$ .

We must break up the problem into cases.

If we have no heads, there is only one possible sequence (namely, all tails).

If there is one head, then that head can be in any of 12 positions, for 12 different cases.

If there are two heads, we must have three slots to put the tails in _ H _ H _ , but two tails must be in between the heads to separate them, leaving us with 12 - 2 - 2 = 8 tails to place where we like. This means that we are looking for the number of solutions to $a + b + c = 8$ , which by stars and bars has $\binom{8+2}{2}$ solutions.

We can proceed in a similar fashion for cases with a larger number of heads and getting the following results:

3 heads yields $\displaystyle \binom{8}{3}$ possibilities.

4 heads yields $\displaystyle \binom{6}{2}$ possibilities.

And 5 heads require 8 tails to separate them, which means there must be at least 13 tosses in the sequence, which is impossible. So no sequence will exist with 5 heads (or any number greater than 5 for that matter).

This means that our final answer is $\binom{12}{0} + \binom{12}{1} + \binom{10}{2} + \binom{8}{3} + \binom{6}{2} = \boxed{129}$

Consider a sequence of 12 tails, $T T T T T T T T T T T T$ . We can replace $T's$ in this sequence with $H's$ . However, once the number of $H's$ exceeds 1, we have to remove 2 $T's$ , for each additional $H$ , from the sequence before selecting the positions of the H's, so that we can insure that the $H's$ are separated by at least 2 $T's$ . Thus, the combinations are as follows:

$\binom{12}{0}+\binom{12}{1}+\binom{10}{2}+\binom{8}{3}+\binom{6}{4}$ .

The maximum number of $H's$ in a sequence is 4, because with 5 $H's$ , there are not enough $T's$ to ensure a separation of 2 between each $H$ . This sum of combinations yields $\boxed{129}$ .

Let $f(n)$ denote the number of possible sequences that contain $n$ H's. Note that the maximum number of H's in such a sequence is $4$ , due to the conditions.

First, let's consider $f(4)$ . Let $H_1,H_2,H_3,H_4$ denote the positions of the H's in the sequence from left to right. We know that there have to be at least 2 T's between any two H's, so the sequence $H_1,H_2-2,H_3-4,H_4-6$ is strictly increasing. Also, $H_4 \leq 12 \implies H_4 - 6 \leq 6,$ which means that we can position the four H's in $f(4) = {6 \choose 4} = 15$ ways.

Similarly, if we consider $f(3)$ , then the sequence $H_1,H_2-2,H_3-4$ is strictly increasing and $H_3 \leq 12 \implies H_3 - 4 \leq 8,$ so $f(3) = {8 \choose 3} = 56$ .

Similarly, $f(2) = {{12-2} \choose 2} = 45$ . $f(1)=12$ and $f(0)=1$ are trivial. So, the number of possible sequences Bernoulli could have had is

$f(0) + f(1) + f(2) + f(3) + f(4) = 1 + 12 + 45 + 56 + 15 = \boxed{129}.$

Suppose that Bernoulli ends his sequence with two additional T's, so that the sequence has 14 characters but the last two are guaranteed to be T's. This obviously forms a bijection.

Now, let $X$ be the string $HTT$ . This guarantees that no two heads are separated by less than two tails, because after every heads we have two tails following. For example, the string $XXTTTXTT$ becomes $HTTHTTTTTHTTTT$ , which in turn after removing the additional two tails becomes $HTTHTTTTTHTT$ . Additionally, since we pad (only) two tails at the end, there cannot be any heads as the last two characters; any heads must be followed by at least two tails, and there's not enough space to do so. But we can always transform an original HT-sequence to our XT-sequence; the padding of two tails at the end allows X's to replace any heads, even if they are at the end of the string; the padding gives enough tails for the X's to replace. So we also have a bijection.

Finally, we will count the number of ways according to the number of X's in the sequence.

Note that we have 14 characters. $x$ of them are X's, and so $14-3x$ of them are T's (X's occupy three characters). Since $14-3x \ge 0$ , we have $x \le 4$ .

• If $x = 0$ , then there is $\binom{0+14}{0} = 1$ way to arrange $0$ X's and $14$ T's.
• If $x = 1$ , then there are $\binom{1+11}{1} = 12$ ways to arrange $1$ X and $11$ T's.
• If $x = 2$ , then there are $\binom{2+8}{2} = 45$ ways to arrange $2$ X's and $8$ T's.
• If $x = 3$ , then there are $\binom{3+5}{3} = 56$ ways to arrange $3$ X's and $5$ T's.
• If $x = 4$ , then there are $\binom{4+2}{4} = 15$ ways to arrange $4$ X's and $2$ T's.

In total, there are $1 + 12 + 45 + 56 + 15 = \boxed{129}$ sequences.

---

There's also another way to do this by recursion. Let $x_n$ be the number of sequences of $n$ characters. We know that $x_1 = 2, x_2 = 3, x_3 = 4$ ; when there are less than 4 characters, it's impossible to have two heads.

Now, observe the last character of a $n$ -character string. There are two cases: H or T.

• If the last character is H, then the second-to-last and the third-to-last characters are both T. After that, the string is free; there are $x_{n-3}$ strings.
• If the last character is T, then the string is free; there are $x_{n-1}$ strings.

So our recursion is $x_n = x_{n-1} + x_{n-3}$ . With the initial values, we can easily find $x_{12} = \boxed{129}$ .

At minimum, the each head needs to be separated by 2 tails, and we can have at most 4 heads. So let's do some casework.

Case 1: No heads. There is clearly one solution, where they are all Tails.

Case 2: One head. Since there is only one head it can appear anywhere in twelve positions in the sequence, so there are 12 solutions.

Case 3: Two heads. First, we have HTTH. Then, we can add the remaining 8 tails to the sequence in position before the first heads, between the two heads, or after the second heads. So, effectively this is distributing 8 things to 3 people, the formula for which is (8 + 3 - 1) choose (8), which is 45.

Case 4: Three heads. So at minimum we have HTTHTTH. Using the same as before, the number of sequences equals 8 choose 5.

Case 5: Four heads. Same deal, and we get 15 solutions.

Adding all of these together, we have 129 sequences.

By the Carlitz-Scoville-Vaughan theorem, the generating function for the number of combinations omitting the sequence HH or HTH is $\frac{1}{1-t-\sum _{n=0}^5 \left(\sum _{k=n+1}^{12-n} (-1)^{k-1} \binom{k-1}{n} h^k t^n\right)}$ . The answer is the sum of the coefficients for $h^a t^{12-a}$ in the Taylor series expansion of our generating function, which only has non-zero coefficients for $0 \leq a \leq 4$ . These coefficients are $1, 12, 45, 56, \text{and } 15$ , which sum to $\boxed{129}$ .

Total 5 cases:-

case 1: 0 HEAD

1 sequence

case 2: 1 HEAD

12 sequences

case 3: 2 HEAD

total - sequences with HH - sequences with HTH

12C2-11C1-10C1=45 sequences

case 4: 3 HEADS

x1 H x2 H x3 H x4

x1,x2,x3,x4 represent the no. of tails with conditions x1,x4>=0 and x2,x3>=2

x1+x2+x3+x4=9

on solving we get 56 sequences

case 5: 4 HEADS

solving similarly we get 15 sequences.

adding 1+12+45+56+15=129

Since we cannot have consecutive heads or a tail between heads, there has to be at least $2$ tails between heads. Thus the maximum number of heads we can have is $4$ because with $5$ heads the minimum number of coins we need with $2$ tails between each pair of heads is $13$ . $$ We count the number of possible sequences with $0,1,2,3,4$ heads. With $0$ heads there is only $1$ possible sequence. With $1$ head we have $12$ possible sequences. For two heads and on, we have to do a trick. In order to ensure that any sequence with $2$ heads does not violate the conditions, we insert two tails between any two heads and subtract two from the total number of spaces. Hence the number of sequences for two is $10\choose 2$ . Proceeding in the same manner for $3$ and $4$ we get $8\choose 3$ and $6 \choose 4$ respectively. Adding all of them up we get: $1+12+45+56+15=\fbox{129}$

Let $f(x)$ be the number of ways in which you can fill $x+1$ places, with $T$ at 1st place.

Back to the problem, let us try to fill the 12 spaces abiding by the above rules. Observe this pattern, which makes this hard seeming problem, trivial:

• You can place $H$ at first,then 2nd must be $T$ , so 3rd one must be $T$ . Now go to step 2.

• You can continue the above algorithm, or place a $T$ & repeat this step.

So,if with $n$ places left, you can place $HTT...$ (3 places filled) OR $T...$ (1 place filled). Thus there is a recursion at work.

$f(x) = f(x-1) + f(x-3)$ .

Evaluate manually $f(0) = 1$ , $f(1) = 2$ , $f(2) = 3$ , & continue. Our target is $f(11) + f(9) = 129$

Let A(n) be the number of allowable sequences from n tosses. For n>2 there are two possibilities: a) the first toss is a tail and the remaining tosses are an allowable sequence of length n-1 b) the first toss is a Head, followed by two tails (HTT) followed by an allowable sequence of length n-3. It is easy to count early cases by hand: A(1)=2,A(2)=3 A(3)=4 and we can then find A(12)=129 via the recurrence:

• $A_{n}=A_{n-1}+A_{n-3}$

The sequence is made of pieces of 2 kinds: HTT or T.

In this kind of sequences, there aren't one ending with H or HT, so I can imagine of having sequences of 14 results, knowing that last two results will be TT, so the number is the same.

So, I have to order pieces of length 3 (HTT) or 1 (T) to obtain 14 results.

• $14 = 3*4+1*2 \rightarrow {6 \choose 2} = 15$ possibilities
• $14 = 3*3+1*5 \rightarrow {8 \choose 3} = 56$ possibilities
• $14 = 3*2+1*8 \rightarrow {10 \choose 2} = 45$ possibilities
• $14 = 3*1+1*11 \rightarrow {12 \choose 1} = 12$ possibilities
• $14 = 1*14 \rightarrow 1$ possibility

$15+56+45+12+1 = \boxed{129}$

The conditions imply that a $H$ must be followed by $TT$ , with the exceptions of the sequence ending in $-H$ or $-HT$ .

Let $f(n)$ be the number of ways of creating a sequence of length $n$ from the units ${T, HTT}$ .

Then the number of possible sequences for each of the 3 cases listed above (which are exhaustive and mutually exclusive) are:

• Ends in -HT: $f(10)$
• Ends in -H: $f(11)$
• All other cases: $f(12)$

and the answer we are looking for is therefore $f(10) + f(11) + f(12)$

To find the value of $f(12)$ for example, we consider all possibilities for which units are involved, and then give the number of ways of ordering those units. $\begin{aligned} \\&4 * {HTT}, &0 * {T} &\longrightarrow &{}^{4}C_{4} \\ &3 * {HTT}, &3 * {T} &\longrightarrow &{}^{6}C_{3} \\ &2 * {HTT}, &6 * {T} &\longrightarrow &{}^{8}C_{2} \\ &1 * {HTT}, &9 * {T} &\longrightarrow &{}^{10}C_{1} \\ &0 * {HTT}, &12 * {T} &\longrightarrow &{}^{12}C_{0} \end{aligned}$

so $f(12) = 1 + 20 + 28 + 10 + 1 = 60$

Similarly we find $f(11) = {}^{5}C_{3} + {}^{7}C_{2} + {}^{9}C_{1} + {}^{11}C_{0} = 41$ and $f(10) = {}^{4}C_{3} + {}^{6}C_{2} + {}^{8}C_{1} + {}^{10}C_{0} = 28$ giving us a final sum of $60 + 41 + 28 = \boxed{129}$