A218274 Number of n-step paths from (0,0) to (1,0) where all diagonal, vertical and horizontal steps are allowed.

0, 1, 4, 27, 168, 1140, 7800, 54845, 390320, 2815344, 20494320, 150442908, 1111782672, 8264558016, 61743361680, 463306724595, 3489942222624, 26378657835816, 199991245341888, 1520403553182800, 11587257160313120, 88506896001503616, 677426230547667744

Offset

0,3

Comments

Equivalent to which linear combinations of (-1,-1), (-1,0), (-1,1), (0,1), (0,-1), (1,1), (1,0), (1,-1) equal (1,0).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Example

a(2) = 4 because we have [0,1]+[1,-1], [1,1]+[0,-1] and the y-negatives [0,-1]+[1,1], [1,-1]+[0,1].

Maple

a:= proc(n) option remember; `if`(n<3, n^2,
      ((9*n^4-9*n^3-8*n^2+4*n) *a(n-1)
      +4*(n-1)*(27*n^3-84*n^2+80*n-21) *a(n-2)
      +32*(3*n-1)*(n-1)*(n-2)^2 *a(n-3))/ (n*(n-1)*(n+1)*(3*n-4)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 02 2012

Mathematica

a[n_] := a[n] = If[n<3, n^2,
     ((9n^4-9n^3-8n^2+4n) a[n-1] +
     4(n-1)(27n^3-84n^2+80n-21) a[n-2] +
     32(3n-1)(n-1)(n-2)^2 a[n-3]) /
     (n(n-1)(n+1)(3n-4))];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Aug 29 2021, after Alois P. Heinz *)

Prog

(Maxima)
a[0]:0$
a[1]:1$
a[2]:4$
a[n]:= ((9*n^4-9*n^3-8*n^2+4*n)*a[n-1]+4*(n-1)*(27*n^3-84*n^2+80*n-21)*a[n-2]+32*(3*n-1)*(n-1)*(n-2)^2 *a[n-3])/(n*(n-1)*(n+1)*(3*n-4))$
A218274(n):=a[n]$
makelist(A218274(n), n, 0, 30); /* Martin Ettl, Nov 03 2012 */

Crossrefs

Cf. A094061.

Sequence in context: A274751 A015534 A306054 * A061693 A005974 A289718

Adjacent sequences: A218271 A218272 A218273 * A218275 A218276 A218277

Keyword

nonn,easy

Author

Jon Perry, Nov 01 2012

Extensions

More terms from Joerg Arndt, Nov 02 2012

Status

approved