A151312 Number of walks within N^2 (the first quadrant of Z^2) starting at (0, 0) and consisting of n steps taken from {(-1, -1), (-1, 1), (-1, 0), (1, -1), (1, 0), (1, 1)}.

1, 2, 10, 39, 210, 960, 5340, 26250, 148610, 761796, 4360356, 22971102, 132469260, 711426144, 4124979144, 22471772895, 130833575730, 720642479700, 4209268283220, 23389011317958, 136971640993044, 766537623135648, 4498668129173400, 25325478605719656, 148897823229533196, 842422760884567800

Offset

0,2

Links

Robert Israel, Table of n, a(n) for n = 0..600

A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.

Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.

Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers, and Lucien Pech, Hypergeometric expressions for generating functions of walks with small steps in the quarter plane. Eur. J. Comb. 61, 242-275 (2017)

A. Bostan and M. Kauers, 2008. Automatic Classification of Restricted Lattice Walks, ArXiv 0811.2899.

M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, ArXiv 0810.4387.

Formula

G.f.: Int(hypergeom([3/2,3/2],[2],16*x/((2*x+1)*(6*x+1)))*(1-2*x)/((2*x+1)*(6*x+1))^(3/2),x)/x. - Mark van Hoeij, Aug 14 2014

a(n) = A001405(n) * A005773(n+1). - Natalia L. Skirrow, Feb 27 2026

Maple

Gf:= Int(hypergeom([3/2, 3/2], [2], 16*x/((2*x+1)*(6*x+1)))*(1-2*x)/((2*x+1)*(6*x+1))^(3/2), x)/x:
S:= series(Gf, x, 101):
seq(coeff(S, x, j), j=0..100); # Robert Israel, Aug 14 2014
# Alternative:
# The following programs a0 and a1 give the even and odd terms:
a0 := proc(n) options remember;
  if n=0 then 1 elif n=1 then 10
  else  2*(-18*(2*n-3)^2*a0(n-2)+(2*n-1)*(20*n^2-2*n-3)*a0(n-1)/(2*n+1))/n^2
  fi
end:
a1 := proc(n) options remember;
  if n=0 then 2 elif n=1 then 39 else
   2*(-18*(2*n-1)^2*(1-1/n^2)*a1(n-2)+(20*n^2+18*n+1)*a1(n-1))/(n+1)^2
  fi
end:
seq(op([a0(n), a1(n)]), n=0..50); # - Mark van Hoeij, Jul 15 2022
# Alternative:
C := binomial: a := n -> C(n, iquo(n, 2))*add(C(n, i)*C(n-i, iquo(n-i, 2)), i = 0..n): seq(a(n), n = 0..25);  # Peter Luschny, Mar 06 2026

Mathematica

aux[i_Integer, j_Integer, n_Integer] := Which[Min[i, j, n] < 0 || Max[i, j] > n, 0, n == 0, KroneckerDelta[i, j, n], True, aux[i, j, n] = aux[-1 + i, -1 + j, -1 + n] + aux[-1 + i, j, -1 + n] + aux[-1 + i, 1 + j, -1 + n] + aux[1 + i, -1 + j, -1 + n] + aux[1 + i, j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[Sum[aux[i, j, n], {i, 0, n}, {j, 0, n}], {n, 0, 25}]

Prog

(Python)
from math import comb as C
def a(n: int) -> int:
    return C(n, n >> 1) * sum(C(n, i) * C(n - i, (n - i) >> 1) for i in range(n + 1))
print([a(n) for n in range(26)])  # Peter Luschny, Mar 06 2026

Crossrefs

Cf. A001405, A005773.

Sequence in context: A384066 A165814 A151311 * A253590 A184433 A339090

Adjacent sequences: A151309 A151310 A151311 * A151313 A151314 A151315

Keyword

nonn,walk

Author

Manuel Kauers, Nov 18 2008

Status

approved