A190666 Number of walks from (0,0) to (n+3,n) which take steps from {E, N, NE}.

1, 9, 61, 377, 2241, 13073, 75517, 433905, 2485825, 14218905, 81270333, 464387817, 2653649025, 15167050785, 86716873725, 495998874593, 2838240338817, 16248650965289, 93065296937533, 533285164334169, 3057236753252161, 17534423944871729, 100609937775369981

Offset: 0

Author

Shanzhen Gao, May 25 2011

Keywords

• nonn
• walk
• easy

Comments

+-3-diagonal of A008288 as a square array. - Shel Kaphan, Jan 07 2023

References

• S. Gao, H. Niederhausen, Counting New Lattice Paths and Walks with Several Step Vectors (submitted to Congr. Numer.). - Shanzhen Gao, May 25 2011

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..400
• Shanzhen Gao and Keh-Hsun Chen, Counting Lattice Paths and Walks with Several Step Vectors, FCS 2014.

Crossrefs

Cf. A001850, A008288, A113139, A002002, A026002.

Programs

Maple

b:= proc(i, j) option remember;
      if i<0 or j<0 then 0
    elif i=0 and j=0 then 1
    else b(i-1, j) +b(i, j-1) +b(i-1, j-1)
      fi
    end:
a:= n-> b(n+3, n):
seq(a(n), n=0..30);  # Alois P. Heinz, May 28 2011

Mathematica

b[i_, j_] /; i<0 || j<0 = 0; b[0, 0] = 1; b[i_, j_]:= b[i, j]= b[i-1, j] + b[i, j-1] + b[i-1, j-1]; a[n_] := b[n+3, n]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jun 01 2011, after Maple prog. *)
CoefficientList[Series[(-1+3*x-x^2+(1-6*x+6*x^2-x^3)/Sqrt[x^2-6*x+1])/(2*x^3), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 20 2012 *)
Table[(-1)^n Hypergeometric2F1[-n, n+4, 1, 2], {n,0,22}] (* Peter Luschny, Mar 02 2017 *)

Formula

a(n) = Sum_{k=0..n} C(n,k) * C(n+k+3,k+3) = A113139 (n+3,3). - Alois P. Heinz, Jun 01 2011

G.f.: (-1 + 3*x - x^2 + (1 - 6*x + 6*x^2 - x^3)/sqrt(x^2 - 6*x + 1))/(2*x^3). - Alois P. Heinz, Jun 03 2011

Recurrence: n*(n+3)*a(n) = (5*n^2 + 15*n + 16)*a(n-1) + (5*n^2 - 5*n + 6)*a(n-2) - (n-2)*(n+1)*a(n-3). - Vaclav Kotesovec, Oct 20 2012

a(n) ~ sqrt(1632 + 1154*sqrt(2))*(3 + 2*sqrt(2))^n/(4*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 20 2012

From Peter Bala, Mar 02 2017: (Start)

a(n) = (1/2^(n+1))*Sum_{k >= 3} (1/2^k)*binomial(n+k, k)*binomial(n+k, n+3).

a(n) = (-1)^n*Sum_{k = 0..n} (-2)^k*binomial(n,k) * binomial(n+k+3,k).

n*(n+3)*(2*n + 1)*a(n) = 6*(n+1)*(2*n^2 + 4*n + 3)*a(n-1) - (n-1)*(n+2)*(2*n + 3)*a(n-2) with a(0) = 1 and a(1) = 9. (End)

a(n) = (-1)^n*hypergeom([-n, n+4], [1], 2). - Peter Luschny, Mar 02 2017