[seqfan] Counting bitcounts

[David Wilson]

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.