How many bit strings of length n contain k ones in a row?

Question

Inspired by:

http://nz.answers.yahoo.com/question/index?qid=20080829150641AAj6n4A

The difference is that I require the equal tosses to be in a row and don't care about the rest, as in THHTHHHH.

Clarification: each considered string must contain at least one substring of ones at least k digits long.

Answer 1

Let A(k-1,n) be the set of length n strings whose longest run of 1′s has, at most, length k-1. Then A(k-1,n) splits as:

A(k-1,n)=0A(k-1,n-1)∪

∪10A(k-1,n-2)∪⋅⋅⋅∪

∪1^(k-1)0A(k-1,n-k+1)

Where 1^(i)0 denotes the sequence of i 1′s followed by a 0 and 1^(i)0A(k-1,n) the set of sequences obtained by concatenating the prefix 1^(i)0 with the any member of the set A(k-1,n-i); then, as the above splitting is disjoint, if we define   a(k-1,n-i) = |A(k-1,n-i)|, then:

a(k-1,n)=∑[i=1,k]a(k-1,n-i)

Which gives the recurrence:

a(k-1,j) = 2^j,  0 ≤ j ≤ k-1

a(k-1,n+k) = ∑{i=1,k}a(k-1,n+k-i),  n ≥ 0

And the number of sequences with at least one substring of  1's with length ≥ k is given by 2^n − a(k-1,n).

I don't know any closed form solutions for this recurrence, especially if we don't particularize k, but it's generating function is:

(1/(1-2x)) − A(k-1,x)

Where A(k-1,x) is the generating function of the sequence       a(k-1,n), and this is then given by:

(A(k-1,x) −

                  Ã¢ÂˆÂ’ ∑[n=0,k-1](2x)^n)x^(-k) =

= ∑[i=1,k]{A(k-1,x) − ∑[n=0,k-i-1](2x)^n}x^(i-k)

Therefore:

A(k-1,x) − ∑[n=0,k-1](2x)^n =

= ∑[i=1,k](A(k-1,x) −

  

                                  Ã¢ÂˆÂ’ ∑[n=0,k-i-1](2x)^n)x^i ⇔

⇔ A(k-1,x) − ∑[i=1,k]A(k-1,x)x^i =

     =∑[n=0,k-1](2x)^n − ∑[i=1,k]x^i∑[n=0,k-i-1](2x)^n ⇔

⇔ A(k-1,x)(1-∑[i=1,k]x^i) =

  

    =(2x)^k − 1)/(2x-1) −

        Ã¢ÂˆÂ’ (1 / 2x − 1)∑[i=1,k]x^i((2x)^(k-i)-1) ⇔

⇔ A(k-1,x) =

= (2x^(k+1)-x^k-2x+1) divided by

  

(2x-1)(2x-1-x^(k+1))

And:

1/(1-2x)-A(k-1,x)=

  =(x^k)(x-1) divided by

     (2x-1)(x^(k+1)-2x+1)

For example, taking k=1 (sequences that contain at least a 1) and expanding the above in powers of x, we have:

(x/(2x-1))((x-1)/(x²-2x+1)) =

= x+3x^2+7x^3+15x^4+

  

  +31x^5+63x^6+127x^7+

  + 255x^8+511x^9+O(x^10)

    And notice that the coefficient of the x^n term is 2^n − 1, as it should be.