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,2

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

Table of n, a(n) for n=0..34.

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

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

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 *)

Crossrefs

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

Sequence in context: A027423 A140410 A213368 * A164263 A283836 A244825

Adjacent sequences: A216209 A216210 A216211 * A216213 A216214 A216215

Keyword

nonn,walk

Author

Philippe Deléham, Mar 13 2013

Status

approved