2
$\begingroup$

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?

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

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

$\endgroup$
4
  • $\begingroup$ Wow, seems to be very good... But how do I get the binomial coefficients on the right side? $\endgroup$
    – xampper
    Jun 19 '14 at 0:18
  • $\begingroup$ I've got an idea (upload.wikimedia.org/math/5/b/1/…), I'll ponder on it... $\endgroup$
    – xampper
    Jun 19 '14 at 0:24
  • $\begingroup$ 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. $\endgroup$
    – Asinomas
    Jun 19 '14 at 3:05
  • 1
    $\begingroup$ Okay, thank you, I'm trying to program a JavaScript function. I'm getting closer and closer :-) $\endgroup$
    – xampper
    Jun 19 '14 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.