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

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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

Examples

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

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.

Crossrefs

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

Cf. A098272. First row of array A098273.

Column of A176129, A214631, A214722, A340591.

Programs

Magma

[4^n*Factorial(3*n)/(Factorial(n+1)*Factorial(2*n+1)) : n in [0..20]]; // Wesley Ivan Hurt, Nov 16 2014

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 *)

PARI

{a(n) = if( n<0, 0, 4^n * (3*n)! / ((n+1)! * (2*n+1)!))}; /* Michael Somos, Jan 23 2003 */

Sage

def a(n):
    return (4**n * binomial(3 * n, 2 * n)) // ((n + 1) * (2 * n + 1))
# F. Chapoton, Jun 01 2020

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

Extensions

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