A180722 - OEIS

%I #8 Aug 08 2013 05:15:04

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

%N 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.

%C 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.

%o (C) .#include <math.h>

%o .#include <unistd.h>

%o .#include <stdlib.h>

%o .#include <stdio.h>

%o .

%o .#define MAX 10

%o .

%o .int n, w[4*MAX+1];

%o .

%o .double

%o .f(int i, int wk, int lh, int rh)

%o .{

%o . w[i] = wk;

%o . return

%o . i < n? f(i+1, wk-1, lh+wk, 0) + f(i+1, wk+1, lh+wk, 0): // init lh

%o . i < 2*n? f(i+1, wk-1, lh, rh+wk) + f(i+1, wk+1, lh, rh+wk): // init rh

%o . i < 4*n? (lh >= rh? 0:

%o . f(i+1, wk-1, lh+w[i-n]-w[i-2*n], rh+wk-w[i-n]) + // walk

%o . f(i+1, wk+1, lh+w[i-n]-w[i-2*n], rh+wk-w[i-n])):

%o . lh < rh; // stop

%o .}

%o .

%o .int

%o .main()

%o .{

%o . for (n = 1; n <= MAX; n++)

%o . printf("%2d %0.f\n", n, f(0, 0, 0, 0)/2);

%o . return 0;

%o .}

%K hard,more,nonn,walk

%O 1,2

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