A216212 Number of n step walks (each step +-1 starting from 0) which are never more than 4 or less than -4.

1, 2, 4, 8, 16, 30, 60, 110, 220, 400, 800, 1450, 2900, 5250, 10500, 19000, 38000, 68750, 137500, 248750, 497500, 900000, 1800000, 3256250, 6512500, 11781250, 23562500, 42625000, 85250000, 154218750, 308437500, 557968750, 1115937500, 2018750000, 4037500000

Offset: 0

Author

Philippe Deléham, Mar 13 2013

Keywords

• nonn
• walk

Comments

The number of n step walks (each step +-1 starting from 0) which are never more than k or less than -k is given by a(n,k) = 2^n/(k+1)*Sum_{r=1..k+1} (-1)^r*cos((Pi*(2*r-1))/(2*(k+1)))^n*cot((Pi*(1-2*r))/(4*(k+1))), n<>0 if k even. Here we have k=4. - Herbert Kociemba, Sep 22 2020

Links

• Index entries for linear recurrences with constant coefficients, signature (0,5,0,-5).

Crossrefs

Cf. A068911, A068912, A068913, A178381 (starting from 4).

Programs

Mathematica

nn=30;CoefficientList[Series[(1+x-x^2)^2/(1-5x^2+5x^4),{x,0,nn}],x] (* Geoffrey Critzer, Jan 14 2014 *)
a[0,4]=1; a[n_,k_]:=2^n/(k+1) Sum[(-1)^r Cos[(Pi (2r-1))/(2 (k+1))]^n Cot[(Pi (1-2r))/(4 (k+1))],{r,1,k+1}]
Table[a[n,4],{n,0,40}]//Round (* Herbert Kociemba, Sep 22 2020 *)

Formula

a(n) = A068913(4,n).

G.f.: (1+2*x-x^2-2*x^3+x^4)/(1-5*x^2+5*x^4).

a(n) = 5*a(n-2) - 5*a(n-4), a(0) = 1, a(1) = 2, a(2) = 4, a(3) = 8, a(4) = 16.

a(2*n+1) = 2*A039717(n+1), a(2*n+2) = 4*A039717(n+1).

a(n) = (2^n/5)*Sum_{r=1..5} (-1)^r*cos(Pi*(2*r-1)/10)^n*cot(Pi*(1-2*r)/20), n>0. - Herbert Kociemba, Sep 22 2020