A005789 3-dimensional Catalan numbers.

1, 1, 5, 42, 462, 6006, 87516, 1385670, 23371634, 414315330, 7646001090, 145862174640, 2861142656400, 57468093927120, 1178095925505960, 24584089974896430, 521086299271824330, 11198784501894470250, 243661974372798631650, 5360563436201569896300

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• walk
• nice
• changed

Comments

Number of standard tableaux of shape (n,n,n). - Emeric Deutsch, May 13 2004

Number of walks within N^2 (the first quadrant of Z^2) starting and ending at (0,0) and consisting of 3 n steps taken from {(-1, 0), (0, 1), (1, -1)}. - Manuel Kauers, Nov 18 2008

Number of up-down permutations of length 2n with no four-term increasing subsequence, or equivalently the number of down-up permutations of length 2n with no four-term decreasing subsequence. (An up-down permutation is one whose descent set is {2, 4, 6, ...}.) - Joel B. Lewis, Oct 04 2009

Equivalent to the number of standard tableaux: number of rectangular arrangements of [1..3n] into n increasing sequences of size 3 and 3 increasing sequences of size n. a(n) counts a subset of A025035(n). - Olivier Gérard, Feb 15 2011

Number of walks in 3-dimensions using steps (1,0,0), (0,1,0), and (0,0,1) from (0,0,0) to (n,n,n) such that after each step we have z>=y>=x. - Thotsaporn Thanatipanonda, Feb 21 2012

Number of words consisting of n 'x' letters, n 'y' letters and n 'z' letters such that the 'x' count is always greater than or equal to the 'y' count and the 'y' count is always greater than or equal to the 'z' count; e.g., for n=2 we have xxyyzz, xxyzyz, xyxyzz, xyxzyz and xyzxyz. - Jon Perry, Nov 16 2012 [here "count" is meant as "number of symbols in any prefix", Joerg Arndt, Jan 02 2024]

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• Snover, Stephen L.; and Troyer, Stephanie F.; A four-dimensional Catalan formula. Proceedings of the Nineteenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1989). Congr. Numer. 75 (1990), 123-126.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..700
• Joerg Arndt, The a(3)=42 Young tableaux of shape [3,3,3].
• Nicolas Borie, Three-dimensional Catalan numbers and product-coproduct prographs, arXiv:1704.00212 [math.CO], 2017.
• Mireille Bousquet-Mélou and Marni Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.
• Paul Drube, Maxwell Krueger, Ashley Skalsky, and Meghan Wren, Set-Valued Young Tableaux and Product-Coproduct Prographs, arXiv:1710.02709 [math.CO], 2017.
• Shalosh B. Ekhad and Doron Zeilberger, Computational and Theoretical Challenges on Counting Solid Standard Young Tableaux. Also arXiv preprint arXiv:1202.6229, 2012. - _N. J. A. Sloane_, Jul 07 2012
• Katarzyna Górska and Karol A. Penson, Multidimensional Catalan and related numbers as Hausdorff moments, arXiv preprint arXiv:1304.6008 [math.CO], 2013.
• Martin Griffiths and Nick Lord, The hook-length formula and generalised Catalan numbers, The Mathematical Gazette Vol. 95, No. 532 (March 2011), pp. 23-30
• Richard Kenyon, Jason Miller, Scott Sheffield, and David B. Wilson, Bipolar orientations on planar maps and SLE_12, arXiv preprint arXiv:1511.04068 [math.PR], 2015. Also The Annals of Probability (2019) Vol. 47, No. 3, 1240-1269.
• Joel Brewster Lewis, Pattern avoidance and RSK-like algorithms for alternating permutations and Young tableaux, arXiv:0909.4966 [math.CO], 2009-2011. [From _Joel B. Lewis_, Oct 04 2009]
• Joel Brewster Lewis, Pattern Avoidance for Alternating Permutations and Reading Words of Tableaux, Ph. D. Dissertation, Department of Mathematics, MIT, 2012. - From _N. J. A. Sloane_, Oct 12 2012
• Andrew Lohr, Several Topics in Experimental Mathematics, arXiv:1805.00076 [math.CO], 2018.
• Michaël Moortgat, The Tamari order for D^3 and derivability in semi-associative Lambek-Grishin Calculus, 15th Workshop: Computational Logic and Applications (CLA 2020).
• Dimana Miroslavova Pramatarova, Investigating the Periodicity of Weighted Catalan Numbers and Generalizing Them to Higher Dimensions, MIT Res. Sci. Instit. (2025). See p. 13.
• Maya Sankar, Further Bijections to Pattern-Avoiding Valid Hook Configurations, arXiv:1910.08895 [math.CO], 2019.
• Stephen Snover, Letter to N. J. A. Sloane, May 1991
• Robert A. Sulanke, Three-dimensional Narayana and Schröder numbers, Theoretical Computer Science, Volume 346, Issues 2-3, 28 November 2005, Pages 455-468.
• Robert A. Sulanke, Generalizing Narayana and Schroeder Numbers to Higher Dimensions, Electron. J. Combin. 11 (2004), Research Paper 54, 20 pp. (see page 16)
• Stephanie F. Troyer and Stephen L. Snover, m-Dimensional Catalan numbers, Preprint, 1989. (Annotated scanned copy)
• Wolfgang Unger, Combinatorics of Lattice QCD at Strong Coupling, arXiv:1411.4493 [hep-lat], 2014.
• Manuel Wettstein, Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers, arXiv:1602.07235 [cs.CG], 2016 and Discr. Comp. Geom. 58 (2017) 505-525.
• Sherry H. F. Yan, On Wilf equivalence for alternating permutations, Elect. J. Combinat.; 20 (2013), #P58.

Crossrefs

A row of A060854.

A subset of A025035.

See A268538 for primitive terms.

Programs

Magma

[2*Factorial(3*n)/(Factorial(n)*Factorial(n+1)*Factorial(n+2)): n in [0..20]]; // Vincenzo Librandi, Oct 14 2017

Maple

a:= n-> (3*n)! *mul(i!/(n+i)!, i=0..2):
seq(a(n), n=0..20);  # Alois P. Heinz, Feb 23 2012

Mathematica

Needs["Combinatorica`"]
Table[ NumberOfTableaux@ {n, n, n}, {n, 0, 17}] (* Robert G. Wilson v, Nov 15 2006 *)
Table[2*(3*n)!/(n!*(n+1)!*(n+2)!),{n,0,20}] (* Vaclav Kotesovec, Nov 13 2014 *)
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]]; Table[aux[0, 0, 3 n], {n, 0, 25}] (* Manuel Kauers, Nov 18 2008 *)

PARI

a(n) = 2*(3*n)!/(n!*(n+1)!*(n+2)!); \\ Altug Alkan, Mar 14 2018

Formula

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

a(n) = 0!*1!*..*(k-1)! *(k*n)! / ( n!*(n+1)!*..*(n+k-1)! ) for k=3.

G.f.: (1/30)*(1/x-27)*(9*hypergeom([1/3, 2/3],[1],27*x)+(216*x+1)* hypergeom([4/3, 5/3],[2],27*x))-1/(3*x). - Mark van Hoeij, Oct 14 2009

a(n) ~ 3^(3*n+1/2) / (Pi*n^4). - Vaclav Kotesovec, Nov 13 2014

a(n) = 2*A001700(n+1)*A001764(n+1)/(3*(3*n+1)*(3*n+2)). - R. J. Mathar, Aug 10 2015

D-finite with recurrence (n+2)*(n+1)*a(n) -3*(3*n-1)*(3*n-2)*a(n-1)=0. - R. J. Mathar, Aug 10 2015

G.f.: x*3F2(4/3,5/3,1;4,3;27x). - R. J. Mathar, Aug 10 2015

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

Extensions

Added a(0), merged A151334 into this one. - N. J. A. Sloane, Feb 24 2016