I would like to know if anyone can give me an algorithm or formula to solve the following problem:
Given two binary numbers A and C, such that C>A and both have a X number of '1' digits, how many binaries B are there, such that C>B>A and B also has exactly X number of '1' digits?
Example: For A=01001 and C=10100, there are 4 binaries with 2 '1' digits: 01010,01100,10001,10010.
If A and C would be the limits for its' number of digits (for example 000111 and 111000) it would be easy to calculate. Problem I'm having is that A and C can end on other numbers.
It's enough to be able to determine, for each of these binary numbers, the position it would have if you sorted all of them in increasing order. For example, when the numbers are $n=5$ digits long and $k=2$ of them are $1$'s, the list is $$00011, 00101, 00110, 01001, 01010, 01100, 10001, 10010, 10100, 11000$$ so we want a function $F$ such that $F(00011) = 0$, $F(00101)=1$, and so on.
I claim that the following rule works to do this. Given a number with digits $b_{n-1} b_{n-2} \dots b_0$, $k$ of which are $1$'s, we define: $$ F(b_{n-1} b_{n-2} \dots b_0) = \begin{cases} F(b_{n-2} \dots b_0) & \text{if } b_{n-1} = 0, \\ \binom{n-1}{k} + F(b_{n-2} \dots b_0) & \text{if } b_{n-1} = 1. \end{cases}$$ The logic is simple: if $b_{n-1} = 1$, then there were $\binom{n-1}{k}$ sequences we skipped that began with a $0$ in that position. So we should count all of those, and then find the tail's position among the sequences that begin with a $1$.
For example, this gives $$F(01010) = F(1010) = \binom{3}{2} + F(010) = \binom{3}{2} + F(10) = \\ = \binom{3}{2} + \binom{1}{1} + F(0) = \binom{3}{2} + \binom{1}{1} = 4.$$ From seeing how this calculation went and noting where we got a binomial coefficient, we can also give an alternate definition. If the $1$'s in the number $b$ are at positions $a_1, a_2, \dots, a_k$ from the right, then $$F(b) = \binom{a_1}{1} + \binom{a_2}{2} + \dots + \binom{a_k}{k}.$$ For example, $1001001$ has a $1$ in positions $0$, $3$, and $6$, so $$F(1001001) = \binom{0}{1} + \binom{3}{2} + \binom{6}{3} = 0 + 3 + 20 = 23.$$
Now answering the original question is easy. If you want to know how many binary numbers between $A$ and $C$ have $k$ $1$'s, the answer is $$F(C) - F(A) - 1$$ because there are $F(C)$ of them smaller than $C$, but $F(A)$ of those are smaller than $A$ (and one of them is $A$).