# Formula providing binary numbers based on digit 1 occurences

I would like to find a formula which gives me all binary numbers which contain the digit "1" a certain number of times. For example to times as in this sequence:

11,101,110,1001,1010,1100,10001,...


I only found a formular with two occurences of the digit:

a(n) = b^i + b^j,
where i = floor((sqrt(8*n - 1) + 1)/2)
j = n - 1 - i*(i - 1)/2
b=2 for decimal representation
b=10 for dual representation


(Source: http://oeis.org/A018900)

But I'd like to be able to specify any number of occurences, for example three:

111, 1011, 1101, 1110, 10011, 10101, 10110, 11001, ...


Unfortunately, this page didn't provide any hint to its formula: http://oeis.org/A038445

Does anybody know the formula?

• Not sure what you want, but the number of binary sequences of length $n$ with exactly $m$ ones is given by $\binom{n}{m}$. Jun 18 '14 at 21:54
• I believe the OP is describing a family of functions $a_k(n)$, defined to be the $n$th natural number with exactly $k$ ones in its binary expansion, and asking for a closed-form formula for $a_k$. The example given is such a formula for $a_2$, which (as we see from the expressions for $i$ and $j$) is equivalent to writing down closed-form formulas for the ordered pairs of positive integers $(i,j)$ with $i>j$ in lexicographical order. Jun 18 '14 at 22:09
• @GregMartin You're right, that's my intention! Jun 18 '14 at 22:18

$a_k(n)=2^{a_k}+2^{a_{k-1}}\dots 2^{a_1}$ where $\binom{a_k}{k}+\binom{a_{k}}{k-1}+\dots\binom{a_1}{1}=n-1$. and $a_k<a_{k-1}<\dots< a_1$
For example $a_3(1)=7=2^2+2^1+2^0$ since $\binom{2}{3}+\binom{1}{2}+\binom{0}{1}=0$
$a_3(5)=19=2^4+2^1+2^0$ since $\binom{4}{3}+\binom{1}{2}+\binom{0}{1}=4$
$a_5(31)=358=2^7+ 2^5+2^4+2^1+2^0$ since $\binom{7}{5}+\binom{5}{4}+\binom{4}{3}+\binom{1}{2}+\binom{0}{1}=30$
• For example for the case $a_5(31)$ we want to get to $30$ by adding the binomial coefficients. So first we pick $\binom{7}{5}=21$ since it is the largest which is less than or equal to $30$, we want to make $9$ with the remaining binomial coefficients, we chose ${5}{4}=5$ since it is the largest smaller than or equal to $9$. Now we want to make $4$, so we pick ${4}{3}=4$ we now have $30$ so we let the last two digits be the smallest possible. Jun 19 '14 at 3:05