I approached the problem using a toy example. Let C(f, h) be the number of flip possibilities out of the 2^f that satisfy the condition that h heads appear in a row. Enumerating C(5,2) gives the following truth table (X is don't care, ? will be explained later).
HHXXX | True
THHXX | True
?THHX | True
??THH | True
Other | False
The ? marks are combinations that don't include the target sequence. So in the third line with one ? it can be either T or H. But the fourth line ?? can only be TT HT TH, not HH (otherwise it would be double counted in line 1.)
Let ~C(f,h) = 2^f - C(f,h)
for C(5,2) we have: 2^3 (first line) + 2^2 (second line) + 2 (third line ?) * 2 (third line X) + ~C(2,2)
If we move from C(5,2) to C(6, 2) we get:
HHXXXX | True
THHXXX | True
?THHXX | True
??THHX | True
???THH | True
Other | False
Which can be examined line this:
HHXXX(X) | True
THHXX(X) | True
?THHX(X) | True
??THH(X) | True
(???THH) | True
Other | False
And so we have C(6,2) = 2 * C(5,2) (X on each line from 1-4) + ~C(3, 2) (last line)
From here the recurrence is simply:
C(f+1,h) = 2 * C(f,h) + ~C(f-(h+1), h)
And then we can use the initial conditions:
C(f=h, h) = 1
C(f<h, h) = 0
To find any given C(f, h) using a recurrence relationship.
Now that we have a recurrence relationship and we can use eigendecomposition to find an explicit formula.
First we have to get rid of the annoying constant:
C(f+1, h) = 2 * C(f, h) - 2^(f-(h+1)) + C(f-(h+1), h)
C(f, h) = 2 * C(f-1, h) - 2^(f-(h+2)) + C(f-(h+2), h)
C(f+1, h) - 2 * C(f, h) = 2 * C(f, h) - 2^(f-(h+1)) + C(f-(h+1), h) - 2 * (2 * C(f-1, h) - 2^(f-(h+2)) + C(f-(h+2), h))
C(f+1, h) = 4 * C(f, h) - 4 * C(f-1, h) + C(f-(h+1), h) - 2 * C(f-(h+2), h)
So for any given h we can construct a matrix A that when you multiply {C(f, h), C(f-1, h), ... C(f-(h+2), h)} against it you receive {C(f+1, h), C(f, h), ... C(f-(h+1), h)}, or the next iteration.
Given that matrix, we can perform an eigendecomposition, let S be a matrix of the eigenvectors of A, and Λ be a diagonal matrix of the corresponding eigenvalues of A. Then SΛS^-1 = A (by some matrix math)
Then because Λ is diagonal, it's very simple to take the nth power of and
A^n = S Λ^n S^-1
(Because S and S^-1 cancel when multiplied.)
I allowed Mathematica to chew on the condition where h=2, and it spit out:
-(1/(4 Sqrt[11]))i (2 i Sqrt[11] (1+2^(3+f))+Root[-1-#1-#1^2+#1^3&,2]^(f-2) Root[704-10128 #1^2+42340 #1^4+#1^6&,2]+Root[-1-#1-#1^2+#1^3&,1]^(f-2) Root[704-10128 #1^2+42340 #1^4+#1^6&,3]+Root[-1-#1-#1^2+#1^3&,3]^(f-2) Root[704-10128 #1^2+42340 #1^4+#1^6&,6])
It's interesting that FractalFusion's answer does contain the x^3-x^2-x-1 pattern, but I'm curious where the strange x^6 formula comes from.
You can construct a similar recurrence on h using the following:
C(6,2)
HHXXXX | True
THHXXX | True
?THHXX | True
??THHX | True
???THH | True
Other | False
C(6,3)
HH(H)XXX | True
THH(H)XX | True
?THH(H)X | True
??THH(H) | True
(???THH) | False
Other | False
So we can say:
C(f, h+1) = (C(f, h) - ~C(f-h, h))/2
With the initial conditions:
C(f, h=0) = 2^f
C(f, h=1) = 2^f - 1
So:
2 * C(f, h+1) = C(f, h) - 2^(f-h) + C(f-h, h)
2 * C(f, h) = C(f, h-1) - 2^(f-(h+1)) + C(f-(h+1), h)
2 * C(f, h+1) - 4 * C(f, h) = C(f, h) - 2^(f-h) + C(f-h, h) - 2 * (C(f, h-1) - 2^(f-(h+1)) + C(f-(h+1), h))
2 * C(f, h+1) = 5 * C(f, h) - 2 * C(f, h-1) + C(f-h, h) - 2 * C(f-(h+1), h)
C(f, h+1) = 5/2 * C(f, h) - C(f, h-1) + 1/2 * C(f-h, h) - C(f-(h+1), h)
And the matrix can be set up in the same way, let's call this one B with eigenvector matrix T, and eigenvalue matrix M.
Now I'm stuck. I have two matrices, and two degrees of freedom, but the matrix size of the f formula depends on the size of h, and vice versa. How do I put these together to find an explicit formula in two variables of C(f, h)?
