A180722 The number of walks (sequences starting with 0 and changing by plus or minus 1 at each step) of length 4n such that every window therein of width 2n has its left half summing to strictly less than its right half.

1, 4, 247, 2947, 67015, 885946, 17161239, 244111975, 4394140309

Offset

1,2

Comments

For n odd, one in about 7.82 of all walks have this property, while for n even it fluctuates more initially but converges to the same limit as n odd. This small constant ratio demonstrates the weakness of this test for proving with confidence better than 87.2% that an ostensibly increasing sequence is not just a purely random walk.

Links

Table of n, a(n) for n=1..9.

Prog

(C)
#include <math.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX 10
int n, w[4*MAX+1];
double
f(int i, int wk, int lh, int rh)
{
  w[i] = wk;
  return
    i < n? f(i+1, wk-1, lh+wk, 0) + f(i+1, wk+1, lh+wk, 0): // init lh
    i < 2*n? f(i+1, wk-1, lh, rh+wk) + f(i+1, wk+1, lh, rh+wk): // init rh
    i < 4*n? (lh >= rh? 0:
              f(i+1, wk-1, lh+w[i-n]-w[i-2*n], rh+wk-w[i-n]) + // walk
              f(i+1, wk+1, lh+w[i-n]-w[i-2*n], rh+wk-w[i-n])):
    lh < rh; // stop
}
int
main()
{
  for (n = 1; n <= MAX; n++)
    printf("%2d %0.f\n", n, f(0, 0, 0, 0)/2);
  return 0;
}

Crossrefs

Sequence in context: A395075 A320418 A090602 * A087587 A382925 A346919

Adjacent sequences: A180719 A180720 A180721 * A180723 A180724 A180725

Keyword

hard,more,nonn,walk

Author

Vaughan Pratt (pratt(AT)cs.stanford.edu), Sep 18 2010

Status

approved