A006335 a(n) = 4^n*(3*n)!/((n+1)!*(2*n+1)!). (Formerly M2094)

1, 2, 16, 192, 2816, 46592, 835584, 15876096, 315031552, 6466437120, 136383037440, 2941129850880, 64614360416256, 1442028424527872, 32619677465182208, 746569714888605696, 17262927525017812992, 402801642250415636480, 9474719710174783733760, 224477974671833337692160

Offset

0,2

Comments

Number of planar lattice walks of length 3n starting and ending at (0,0), remaining in the first quadrant and using only NE,W,S steps.

Equals row sums of triangle A140136. - Michel Marcus, Nov 16 2014

Number of linear extensions of the poset V x [n], where V is the 3-element poset with one least element and two incomparable elements: see Kreweras and Niederhausen (1981) and Hopkins and Rubey (2020) references. - Noam Zeilberger, May 28 2020

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

G. C. Greubel, Table of n, a(n) for n = 0..700

Andrei Asinowski, Cyril Banderier, and Sarah J. Selkirk, From Kreweras to Gessel: A walk through patterns in the quarter plane, Séminaire Lotharingien de Combinatoire, Proc. 35th Conf. Formal Power Series and Alg. Comb. (Davis, 2023) Vol. 89B, Art. #30.

Olivier Bernardi, Bijective counting of Kreweras walks and loopless triangulations, Journal of Combinatorial Theory, Series A 114:5 (2007), 931-956.

M. Bousquet-Mélou, Walks in the quarter plane: Kreweras' algebraic model, arXiv:math/0401067 [math.CO], 2004-2006.

M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008.

Sam Hopkins and Martin Rubey, Promotion of Kreweras words, arXiv:2005.14031 [math.CO], 2020.

G. Kreweras, Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers, Cahiers du Bureau Universitaire de Recherche Opérationnelle}, Institut de Statistique, Université de Paris, 6 (1965), circa p. 82.

G. Kreweras and H. Niederhausen, Solution of an enumerative problem connected with lattice paths, European J. Combin., 2 (1981), 55-60.

Formula

G.f.: (1/(12*x)) * (hypergeom([ -2/3, -1/3],[1/2],27*x)-1). - Mark van Hoeij, Nov 02 2009

a(n+1) = 6*(3*n+2)*(3*n+1)*a(n)/((2+n)*(2*n+3)). - Robert Israel, Nov 17 2014

a(n) ~ 3^(3*n + 1/2) / (4*sqrt(Pi)*n^(5/2)). - Vaclav Kotesovec, Mar 26 2016

E.g.f.: 2F2(1/3,2/3; 3/2,2; 27*x). - Ilya Gutkovskiy, Jan 25 2017

Example

G.f. = 1 + 2*x + 16*x^2 + 192*x^3 + 2816*x^4+ 46592*x^5 + 835584*x^6 + ...

Maple

A006335:=n->4^n*(3*n)!/((n+1)!*(2*n+1)!): seq(A006335(n), n=0..20); # Wesley Ivan Hurt, Nov 16 2014

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, j, -1 + n] + aux[i, -1 + j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[aux[0, 0, 3 n], {n, 0, 25}] (* Manuel Kauers, Nov 18 2008 *)
Table[(4^n (3 n)! / ((n + 1)! (2 n + 1)!)), {n, 0, 200}] (* Vincenzo Librandi, Nov 17 2014 *)

Prog

(PARI) {a(n) = if( n<0, 0, 4^n * (3*n)! / ((n+1)! * (2*n+1)!))}; /* Michael Somos, Jan 23 2003 */
(Magma) [4^n*Factorial(3*n)/(Factorial(n+1)*Factorial(2*n+1)) : n in [0..20]]; // Wesley Ivan Hurt, Nov 16 2014
(Sage)
def a(n):
    return (4**n * binomial(3 * n, 2 * n)) // ((n + 1) * (2 * n + 1))
# F. Chapoton, Jun 01 2020

Crossrefs

Equals 2^(n-1) * A000309(n-1) for n>1.

Cf. A098272. First row of array A098273.

Column of A176129, A214631, A214722, A340591.

Sequence in context: A123898 A118644 A183205 * A273591 A292347 A051711

Adjacent sequences: A006332 A006333 A006334 * A006336 A006337 A006338

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Edited by N. J. A. Sloane, Dec 20 2008 at the suggestion of R. J. Mathar

Status

approved