[seqfan] Counting bitcounts
dwilson at gambitcomm.com
Mon Apr 20 21:00:29 CEST 2009
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:
Then we form the finite sequence e of the places of the 1's within this
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
< 1000 with exactly 3 1's in their binary representation.
It is possible to express C(b, n) as a sum of binomial coefficients.
More information about the SeqFan