Secuencias$a_{n+1}=a_n-n$ o$a_{n+1}=a_n+n$

Question

Considere el número$N(k)$ de secuencias con$k$ términos$a_1,a_2,\dotsc,a_k$ satisfactorio$a_1=0$, ($a_{n+1}=a_n-n$ o$a_{n+1}=a_n+n$), y$a_i\neq a_j$ para $i\neq j$. ¿Cómo probar que$\lim_{k\to\infty} \ln N(k)/k=1/2$?

Alternativamente, ¿hay un argumento heurístico para esta conjetura?

¿Existe alguna posibilidad de una relación de recurrencia, forma cerrada o asintótica para N (k)?

Esta es la secuencia OEIS A175941 .

Answer 1

Aquí hay evidencia numérica en contra de esa conjetura (con la numeración como en su pregunta, cambiada por una con respecto a la secuencia OEIS). Aquí $R(k)=N(k)/N(k-1)$. Este factor está sistemáticamente por encima de$\sqrt{\mathrm e}$ para$k\ge26$. Si tiende a un límite que tiene una forma cerrada, una estimación más probable es$5/3$, con$\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} $$

Aquí está el código de Java para producir esta tabla:

 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));
    }
}