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

Author

Jon Perry, Nov 01 2012

Keywords

• nonn
• easy

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

Examples

			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].
		

Links

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

Crossrefs

Cf. A094061.

Programs

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

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

Extensions

More terms from Joerg Arndt, Nov 02 2012