A129400 Number of walks of length n on one 60-degree wedge of the equilateral triangular lattice. The walk can go along the walls of the wedge, but cannot cross the walls.

1, 2, 8, 32, 144, 672, 3264, 16256, 82688, 427520, 2240512, 11874304, 63533056, 342712320, 1861779456, 10176823296, 55932813312, 308907737088, 1713473323008, 9541666209792, 53322206674944, 298943898451968

Offset

0,2

Comments

Counts colored Motzkin paths where each of the steps has two possible colors. Series reversion of x/(1+2x+4x^2). - Paul Barry, Sep 04 2007

Hankel transform is 4^C(n+1,2). - Paul Barry, Oct 01 2009

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..300

Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire 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.

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

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

Formula

a(n) = 2^n*A001006(n) = Sum_{k=0..floor(n/2)} C(n,2k)*C(k)*2^(n-2k)*2^k*2^k where C(n) = A000108(n). - Paul Barry, Sep 04 2007

G.f.: 1/(1-2x-4x^2/(1-2x-4x^2/(1-2x-4x^2/(1-2x-4x^2/(1-.... (continued fraction). - Paul Barry, Oct 01 2009

G.f.: (1/(8*x^2)) * (1-2*x-(1-4*x-12*x^2)^(1/2)). - Mark van Hoeij, Nov 02 2009

E.g.f.: a(n) = n! * [x^n] exp(2*x)*BesselI(1,4*x)/(2*x). - Peter Luschny, Aug 25 2012

Recurrence: (n+2)*a(n) = 2*(2*n+1)*a(n-1) + 12*(n-1)*a(n-2) . - Vaclav Kotesovec, Oct 20 2012

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

a(n) = 2^n*GegenbauerC(n, -n-1, -1/2)/(n+1). - Peter Luschny, May 09 2016

G.f.: A(x) = 1/(1 + 2*x)*c(2*x/(1 + 2*x))^2, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. Cf. A005572. - Peter Bala, Aug 18 2021

Example

a(1) = 2 because we can go east or northeast.

Maple

countwalk2 := proc (i::integer, j::integer, n::integer) option remember: if n < 0 or j < 0 or i < j then 0 elif n = 0 and i = 0 and j = 0 then 1 elif n = 0 then 0 else procname(i-2, j, n-1)+procname(i+2, j, n-1)+procname(i-1, j+1, n-1)+procname(i+1, j+1, n-1)+procname(i+1, j-1, n-1)+procname(i-1, j-1, n-1) end if end proc: counter2 := proc (n::nonnegint) option remember: add(add(countwalk2(i, j, n), i = 0 .. 2*n), j = 0 .. n) end proc:
g := n -> simplify(2^n*GegenbauerC(n, -n-1, -1/2)/(n+1)):
seq(g(n), n=0..21); # Peter Luschny, May 09 2016
T := proc(n, k) option remember;
if n < 0 or k < 0 then 0
elif n = 0 then binomial(2*k, k)/(k+1)
else 2*(T(n-1, k+1) - T(n-1, k)) fi end:
a := n -> T(n, 1): seq(a(n), n=0..21); # Peter Luschny, Aug 23 2017

Mathematica

CoefficientList[Series[1/(8*x^2)*(1-2*x-Sqrt[1-4*x-12*x^2]), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 20 2012 *)

Crossrefs

Cf. A000108, A005572.

Sequence in context: A150862 A150863 A084137 * A003304 A150864 A202814

Adjacent sequences: A129397 A129398 A129399 * A129401 A129402 A129403

Keyword

nonn,walk,easy

Author

Rebecca Xiaoxi Nie (rebecca.nie(AT)utoronto.ca), May 28 2007

Status

approved