Counting Binary Strings

I think you could build up a table using a variation of dynamic programming, if you expand the state space. Suppose that you calculate f(n,k,e) defined as the number of different binary strings of length n with the longest substring of 1s length at most k and ending with e 1s in a row. If you have calculated f(n,k,e) for all possible values of k and e associated with a given n, then, because you have the values split up by e, you can calculate f(n+1,k,e) for all possible values of k and e - what happens to an n-long string when you extend it with 0 or 1 depends on how many 1s it ends with at the moment, and you know that because of e.

Let s be the start index of the length k pattern. Then s is in: 1 to n-k.

For each s, we divide the Sting S into three strings:

PRE(s,k,n) = S[1:s-1] 
POST(s,k,n)=S[s+k-1:n] 
ONE(s,k,n) which has all 1s from S[s] to S[s+k-1]

The longest sub-string of 1s for PRE and POST should be less than k.

Let

x = s-1 
y = n-(s+k)-1

Let NS(p,k) is total number of ways you can have a longest sub-string of size greater than equal to k.

NS(p,k) = sum{f(p,k), f(p,k+1),... f(p,p)} 

Terminating condition:

NS(p,k) = 1 if p==k, 0 if k>p
f(n,k) = 1 if n==k, 0, if k > n.

For a string of length n, the number of permutations such that the longest substring of 1s is of size less than k = 2^n - NS(n,k).

f(n,k) = Sum over all s=1 to n-k 
         {2^x - NS(x,k)}*{2^y - NS(y,k)}

i.e. product of the number of permutations of each of the pre and post substrings where the longest sub-string is less than size k.

So we have a repeating sub-problem, and a whole bunch of reuse which can be DPed

Added Later: Based on the comment below, I guess we really do not need to go into NS. We can define S(p,k) as

S(p,k) = sum{f(p,1), f(p,2),... f(p,k-1)} 

and

f(n,k) = Sum over all s=1 to n-k 
         S(x,k)*S(y,k)

I know this is quite an old question if any one wants I can clarify my small answer..

Here is my code

#include<bits/stdc++.h>
using namespace std;
long long DP[64][64];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int i,j,k;
    DP[1][0]=1;
    DP[1][1]=1;
    DP[0][0]=1;
    cout<<"1 1\n";
    for(i=2;i<=63;i++,cout<<"\n")
        {
            DP[i][0]=1;
            DP[i][i]=1;
            cout<<"1 ";
            for(j=1;j<i;j++)
            {
                for(k=0;k<=j;k++)
                    DP[i][j]+=DP[i-k-1][j]+DP[i-j-1][k];
                DP[i][j]-=DP[i-j-1][j];
                cout<<DP[i][j]<<" ";
            }
            cout<<"1 ";
        }
    return 0;
}

DP[i][j] represents F(i,j) .

Transitions/Recurrence (Hard to think):

Considering F(i,j):

1)I can put k 1s on the right and seperate them using a 0 i.e String + 0 + k times '1' . F(i-k-1,j) Note : k=0 signifies I am only keeping 0 at the right!

2) I am missing out the ways in which the right j+1 positions are filled with 0 and j '1' s and All the left do not form any consecutive string of length j !! F(i-j-1,k) (Note I have used k to signify both just because I have done so in my Code , you can define other variables too!)