How many numbers with given amount of ones in their binary form?

Question

I was practicing for a programming competition and I got the following problem, which I was unable to solve:

It is given a number $N$. Find the amount of $x, y$ values, where $x > N$, $y < N$ and the amount of ones in binary form of $x$ and $ y$ is equal with the amount of ones in the binary form of $N$ ($x,y,N$ have the same number of digits in their binary form).

Thank you in advance.

Answer 1

Ok, If I understand correctly for a given $N$ you want the number of pairs $(x,y)$ such that $x,y$ and $N$ all have the same number of digits, moreover $x,y$ and $N$ have the same number of digits and finally $x>N>y$ holds.

To solve this problem we first write $N$ in its binary form and denote by $n$ the number of digits it has and by $k$ the number of one digits.

Now proceed to calculate how many numbers are strictly smaller than $N$ and have $n$ digits and $k$ one digits. To do this characterise $N$ by the list of positions at which it's $1$ digits appear. the list will look something like this: $(n,a_1,a_2\dots a_{k-1})$

For example the number $1110000$ is represented by the list $(7,6,5)$

Given two numbers $N$ and $M$ of the type considered in the problem they both have a sequence, one number is larger than the other if and only if it's list is greater (lexicographically). Sow given a list $(n,a_1,a_2\dots a_{k-1})$ How many lists are smaller?

We can classify the lists that are smaller than $N$ depending on which is the first term of their sequence in which they differ. If they differ in $a_1$ then the number of sequences is $\binom{a_1-1}{k-1}$ since all of the digits except the first must be smaller than $a_1$.

If they differ in $a_2$ for the first time then we know the lists of this type start $(n,a_1\dots)$ and all the terms after must be smaller than $a_2$, thus there are $\binom{a_2-1}{k-2}$.

In general what you want is $\sum_{i=1}^{k-1}\binom{a_i-1}{k-i}$.

So the final answer is $\sum_{i=1}^{k-1}\binom{a_i-1}{k-i}(\binom{n}{k}-\sum_{i=1}^{k-1}\binom{a_i-1}{k-i}-1)$

Answer 2

Your question is not quite clear. However, it would seem that your problem (whatever it is) is essentially solved if you know the position of $N$, in natural (lexicographic) order, among the $\binom nk$ different $n$-bit numbers whose sum of bits is $k$. That position (counted from$~0$) is the value represented by the bits of $N$ in the combinatorial number system, which as the link describes is easy to compute.