[seqfan] Re: Counting bitcounts

[Peter Pein]

David Wilson schrieb:
> For b >= 0 and n >= 0, let C(b, n) be the number of nonnegative integers
> < n having exactly b 1's in their binary representation.
> 
> Suppose we wish to compute, say, C(3, 1000).  First we write 1000 in binary:
> 
>         1111101000
> 
> Then we form the finite sequence e of the places of the 1's within this 
> numeral:
> 
>         e = (9,8,7,6,5,3)
> 
> This sequence is indexed starting at 0.
> 
> 
> Then we have
> 
>         SUM (x^i*(x+1)^e(i)) = SUM C(b, n) x^b
> 
> 
> In our example, this becomes
> 
>         x^0*(x+1)^9 + x^1*(x+1)^8 + x^2*(x+1)^7 + x^3*(x+1)^6 + 
> x^4*(x+1)^5 + x^5*(x+1)^3
>         = 5x^9 + 36x^8 + 113x^7 + 208x^6 + 252x^5 + 210x^4 + 120x^3 + 
> 45x^2 + 10x + 1
>         = SUM C(b, 1000) x^b
> 
> so that C(3, 1000) = 120 is the coefficient of x^3. Thus there are 120 
> nonnegative integers
> < 1000 with exactly 3 1's in their binary representation.
> 
> It is possible to express C(b, n) as a sum of binomial coefficients.
> 
> 

As far as I can see,

C(b,Sum(2^e[i],i,0..ceil(ld(n+1))))=Sum(binomial(e[i],b-i),i=0..b)=1+Sum(binomial(e[i],b-i),i=0..b-1)

should be correct.