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
Examples
a(1) = 2 because we can go east or northeast.
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.
- 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)
- 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.
Programs
-
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 *)
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
Comments