What is the formula for finding all binary numbers below B with the number of bits == 1 staying constant?

Question

Maybe better explained with an example:

Binary number B = 1100, every number less than B is 1010, 1001, 0110, 0101, 0011. (With 2 bits == 1)

So the total ways of expressing the number B and all numbers less than B that contains 2 bits == 1 is 6, or 3+2+1.

I suspect this is a Combinations problem, but my math skills are kind of rusty, and I cannot deduce a consistent formula for different binary numbers.

I have done my search on the web, but could not find anything that gave me an answer to this particular problem.

Answer 1

Let $F(x,y) = \sum_{n = 0}^\infty x^n y^{s_2(n)}$, where $s_2(n)$ is the number of 1s in $n$'s binary representation. Then $$ F(x,y) = F(x^2, y) + xy F(x^2,y) $$ Hence $$ F(x,y) = (1 + xy)F(x^2,y) $$ For a given $n$, we want to calculate the number of $n' \le n$ which have the same number of 1s in binary as $n$. So let $G(x,y)$ be the generating function where the coefficient of $x^n y^k$ is the number of integers less than or equal to $n$ with $k$ 1s in their binary representation. Then $$ G(x,y) = (1 + x + x^2 + \cdots) F(x,y) \implies F(x,y) = (1-x)G(x,y) $$ Hence \begin{align*} (1-x)G(x,y) &= (1 + xy)(1 - x^2)G(x^2,y) \\ G(x,y) &= (1 + xy)(1 + x) G(x^2,y) \end{align*}

The problem amounts to extracting the coefficients of the generating function $G(x,y)$. One can write an algorithm to do this, but an exact formula is probably not going to easy.

Answer 2

If $B$ is not of the form $2^k-1$, so the largest number with $k$ bits, it is easier to split the problem into two. Find $k$, the largest number such that $2^k-1 \lt B$. Let $n$ be the number of bits you want. Then up to $2^k-1$ there are $k \choose n$ such numbers. In the range $[2^k,B]$ you have to have the leading bit a $1$, so can choose $n-1$ more bits. It is the same as the number of numbers with $n-1$ bits in the range $[0,B-2k]$, which gives a recursive algorithm:

function nums(B,n): returns the number of numbers less than or equal to $B$ with $n$ bits in base 2

$k=\lfloor \log_2 (B+1) \rfloor$: let $k$ be the largest number such that $2^k-1 \le B$

if $B=2^k-1$: return $k \choose n$
else: return ${k \choose n} + \text{nums}(B-2^k,n-1)$

Answer 3

Short version: if the number $n$ has $1$s in bit positions $\{i_1,i_2,\dots,i_k\}$ (where we count from the right starting with bit position $1$) then the number of binary numbers that are less than $n$ and have exactly $k$ $1$s is $$ \binom{i_k-1}{k} + \binom{i_{k-1}-1}{k-1} + \dots + \binom{i_1-1}{1} . $$ In your example you have $k=2$, bit positions $\{3,4\}$ so the number is $\binom{3}{2}+\binom{2}{1}=5$.

Long version: I think of this problem as one of ranking and unranking $k$-subsets of $[n]=\{1,2,\dots,n\}$ in the colex order. We order subsets of $\mathbb N$ in the colex order by saying $B<A$ if $\max(A \Delta B) \in A$, or in other words the largest element that they treat differently is in $A$. The correspondence with numbers in binary is by positions of $1$s. If $A$ is a $k$-set then the number of predecessors in colex order is the union of $k$-sets $B$ with $\max(B)<\max(A)$, $k$-sets with $\max(B)=\max(A)$ but which differ in the second largest element, and so on down. These sets are counted by the terms in the sum above.

Answer 4

Thanks to all who posted answers. Some of your math is a mouthful (for me!).

http://en.wikipedia.org/wiki/Permutations gave me the answer, utilizing factorials. The figure called "Permutations of multisets" gave me the solution. See the rightmost column in the figure with 2 red balls and 2 blue balls. When we disregard the ordering of the balls, the solution is perfect for the stated problem.