A151282 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, 0), (0, 1), (1, 1)}.

1, 2, 6, 18, 58, 190, 638, 2170, 7474, 25974, 90982, 320738, 1137002, 4049838, 14485326, 52001290, 187292514, 676546790, 2450311862, 8895769714, 32366225562, 117995832990, 430960312862, 1576675041434, 5777325893266, 21200338220630, 77901645076998, 286615385651970, 1055762834791114, 3893279267979662

Offset

0,2

Comments

From Paul Barry, Jan 19 2009: (Start)

Hankel transform is 2^C(n+1,2).

Row sums of Riordan array ((1-2x)/(1-x+2x^2),x(1-x)/(1-x+2x^2))^{-1}.

G.f.: 1/(1-2x-2x^2/(1-x-2x^2/(1-x-2x^2/(1-x-2x^2/(1-...))))) (continued fraction).

First column of Riordan array ((1-x)/(1+x+2x^2),x/(1+x+2x^2))^{-1}. (End)

Links

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

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

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

Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.

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

Formula

Conjecture: (n+1)*a(n)-3*(2n+1)*a(n-1) +(n+10)*a(n-2) +28(n-2)*a(n-3)=0. - R. J. Mathar, Dec 08 2011

a(n) ~ sqrt(1348+953*sqrt(2)) * (1+2*sqrt(2))^n/(2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 14 2013

Example

G.f. = 1 + 2*x + 6*x^2 + 18*x^3 + 58*x^4 + 190*x^5 + 638*x^6 + 2170*x^7 + ...

Maple

b:= proc(n, l) option remember; `if`(-1 in {l[]}, 0, `if`(n=0, 1,
      add(b(n-1, l+d), d=[[-1, -1], [-1, 0], [0, 1], [1, 1]])))
    end:
a:= n-> b(n, [0$2]):
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 18 2013

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[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}]

Crossrefs

Sequence in context: A304200 A081057 A000137 * A193777 A157004 A293067

Adjacent sequences: A151279 A151280 A151281 * A151283 A151284 A151285

Keyword

nonn,walk

Author

Manuel Kauers, Nov 18 2008

Status

approved