What is the formula for finding all binary numbers below B with the number of bits == 1 staying constant? 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.
 A: 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)$
A: 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.
A: 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.
A: 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.
