[seqfan] Re: Number of n-digit numbers the binary expansion of which contains k runs of 1's

[Georgi Guninski]

On Fri, Jul 30, 2010 at 01:51:13PM +0000, Vladimir Shevelev wrote:
> Dear SeqFans,
> 
> I have just submitted two sequences:
> 
> 
> %I A179867
> %S A179867 0,0,0,0,1,6,21,56,126,252,462,522
> %N A179867 a(n) is the number of n-digit numbers the binary expansion of which contains 3 runs of 1's 
> %F A179867 a(n)=Sum{i=2,n-3})C(i,2)*C(n-i-1,2). A generalization. For k>=1, the number of n-digit numbers the binary expansion of which contains k runs of 1's equals to Sum{k-1,n-k}C(i,k-1)*C(n-i-1,k-1). 
> %Y A179867 A000292 A000332 A179865 A179866 
> %K A179867 nonn
> %O A179867 1,6
> 
>

relatively fast pari code:

a(n)=sum(i=2,n-3,binomial(i,2)*binomial(n-i-1,2)) ;


the first 2000 terms seem to satisfy:

-a(n - 3) + 5*a(n - 2) - 10*a(n - 1) - 5*a(n + 1) + a(n + 2) + 10*a(n) -
1 = 0