2

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?

xampper
  • 23
  • 3
  • 1
    Not sure what you want, but the number of binary sequences of length $n$ with exactly $m$ ones is given by $\binom{n}{m}$. – mathse 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. – Greg Martin Jun 18 '14 at 22:09
  • @GregMartin You're right, that's my intention! – xampper Jun 18 '14 at 22:18

1 Answers1

1

$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$

Asinomás
  • 105,651
  • Wow, seems to be very good... But how do I get the binomial coefficients on the right side? – xampper Jun 19 '14 at 00:18
  • I've got an idea (http://upload.wikimedia.org/math/5/b/1/5b1910ee2c949bbe482062ba41ebbf44.png), I'll ponder on it... – xampper Jun 19 '14 at 00:24
  • 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. – Asinomás Jun 19 '14 at 03:05
  • 1
    Okay, thank you, I'm trying to program a JavaScript function. I'm getting closer and closer :-) – xampper Jun 19 '14 at 23:17