[seqfan] Re: Number of n-digit numbers the binary expansion of which contains k runs of 1's
Georgi Guninski
guninski at guninski.com
Fri Jul 30 16:31:05 CEST 2010
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
More information about the SeqFan
mailing list