Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the number $N(k)$ of sequences with $k$ terms $a_1,a_2,\dotsc,a_k$ satisfying $a_1=0$, ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$), and $a_i\neq a_j$ for $i\neq j$. How to prove that $\lim_{k\to\infty} \ln N(k)/k=1/2$?

Alternately, is there a heuristic argument for this conjecture?

Is there any chance of a reccurence relation, closed form or asymptotics for N(k)?

This is OEIS sequence A175941.

share|improve this question
    
The first statement, $\lim_{k\to\infty} \ln N(k)/k=1/2$, is well-defined. The second one, $N(k)\rightarrow\sqrt{\mathrm e}^k$, isn't, and when interpreted as $N(k)\sim\sqrt{\mathrm e}^k$ it means something else. The equivalent of the first statement would be $N(k)\sim a\sqrt{\mathrm e}^k$ with $a\in\mathbb R^+$. –  joriki Feb 18 '12 at 16:50
1  
@Joriki: Careful, that last part isn't true. The equivalent of the first would be $N(k)\sim \sqrt{e}^k e^{f(k)}$ for some function $f(k)=o(k)$. For example, if $N(k)=\sqrt{e}^k e^{\sqrt{k}}$, then we still have $\log(N(k))/k\rightarrow \frac{1}{2}$ as $k\rightarrow \infty$. –  Eric Naslund Feb 18 '12 at 17:11
    
The OEIS sequence is indexed by the number of steps; yours is indexed by the number of terms. –  joriki Feb 18 '12 at 17:17
    
@Eric: Thanks, I didn't think about that carefully enough. –  joriki Feb 18 '12 at 17:18

1 Answer 1

up vote 3 down vote accepted

Here's numerical evidence against that conjecture (with the numbering as in your question, shifted by one with respect to the OEIS sequence). Here $R(k)=N(k)/N(k-1)$. This factor is systematically above $\sqrt{\mathrm e}$ for $k\ge26$. If it tends to a limit that has a closed form, a more likely guess is $5/3$, with $\log 5/3\approx0.5108$.

$$ \begin{array}{r|r} k&N(k)&\log R(k)&\log N(k)/k\\\hline 1&1&&0.000000\\ 2&2&0.693147&0.346574\\ 3&4&0.693147&0.462098\\ 4&6&0.405465&0.447940\\ 5&10&0.510826&0.460517\\ 6&18&0.587787&0.481729\\ 7&30&0.510826&0.485885\\ 8&50&0.510826&0.489003\\ 9&78&0.444686&0.484079\\ 10&130&0.510826&0.486753\\ 11&210&0.479573&0.486101\\ 12&350&0.510826&0.488161\\ 13&586&0.515387&0.490255\\ 14&954&0.487344&0.490047\\ 15&1606&0.520838&0.492100\\ 16&2588&0.477139&0.491165\\ 17&4234&0.492262&0.491230\\ 18&6944&0.494731&0.491424\\ 19&11342&0.490635&0.491383\\ 20&18948&0.513186&0.492473\\ 21&31450&0.506701&0.493150\\ 22&52206&0.506798&0.493771\\ 23&85662&0.495212&0.493833\\ 24&141680&0.503162&0.494222\\ 25&233040&0.497639&0.494359\\ 26&385428&0.503144&0.494697\\ 27&644910&0.514756&0.495439\\ 28&1072074&0.508240&0.495897\\ 29&1783342&0.508894&0.496345\\ 30&2953094&0.504364&0.496612\\ 31&4897922&0.505958&0.496914\\ 32&8157096&0.510077&0.497325\\ 33&13571014&0.509048&0.497680\\ 34&22552212&0.507897&0.497981\\ 35&37486916&0.508159&0.498272\\ 36&62325564&0.508380&0.498552\\ 37&103508754&0.507285&0.498788\\ 38&172765524&0.512279&0.499143\\ 39&287428656&0.509039&0.499397\\ 40&479052200&0.510835&0.499683\\ 41&798944976&0.511483&0.499971\\ 42&1334245184&0.512829&0.500277\\ \end{array} $$

Here's the Java code to produce this table:

public class Question110661 {
    final static int k = 42;
    static int [] counts = new int [k];
    static boolean [] used = new boolean [k * (k - 1) + 1];

    static void recurse (int n,int an) {
        if (n == k || used [an])
            return;

        counts [n++]++;

        used [an] = true;
        recurse (n,an + n);
        recurse (n,an - n);
        used [an] = false;
    }

    public static void main (String [] args) {
        recurse (0,used.length / 2);

        for (int n = 0;n < k;n++)
            System.out.printf (java.util.Locale.ENGLISH,"%d&%d&%.6f&%.6f\\\\\n",n + 1,counts [n],n == 0 ? 0 : Math.log (counts [n] / (double) counts [n-1]),Math.log (counts [n]) / (n + 1));
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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