A005789 - OEIS

%I M3997 #172 Jan 02 2024 09:37:32

%S 1,1,5,42,462,6006,87516,1385670,23371634,414315330,7646001090,

%T 145862174640,2861142656400,57468093927120,1178095925505960,

%U 24584089974896430,521086299271824330,11198784501894470250,243661974372798631650,5360563436201569896300

%N 3-dimensional Catalan numbers.

%C Number of standard tableaux of shape (n,n,n). - _Emeric Deutsch_, May 13 2004

%C 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

%C 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

%C 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

%C 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

%C 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]

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

%D 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.

%H Alois P. Heinz, <a href="/A005789/b005789.txt">Table of n, a(n) for n = 0..700</a>

%H Joerg Arndt, <a href="/A005789/a005789.txt">The a(3)=42 Young tableaux of shape [3,3,3]</a>.

%H Nicolas Borie, <a href="https://arxiv.org/abs/1704.00212">Three-dimensional Catalan numbers and product-coproduct prographs</a>, arXiv:1704.00212 [math.CO], 2017.

%H M. Bousquet-Mélou and M. Mishna, <a href="http://arxiv.org/abs/0810.4387">Walks with small steps in the quarter plane</a>, arXiv:0810.4387 [math.CO], 2008-2009.

%H Paul Drube, Maxwell Krueger, Ashley Skalsky, and Meghan Wren, <a href="https://arxiv.org/abs/1710.02709">Set-Valued Young Tableaux and Product-Coproduct Prographs</a>, arXiv:1710.02709 [math.CO], 2017.

%H Shalosh B. Ekhad and Doron Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/ssyt.html">Computational and Theoretical Challenges on Counting Solid Standard Young Tableaux</a>. Also arXiv preprint arXiv:1202.6229, 2012. - _N. J. A. Sloane_, Jul 07 2012

%H K. Gorska and K. A. Penson, <a href="http://arxiv.org/abs/1304.6008">Multidimensional Catalan and related numbers as Hausdorff moments</a>, arXiv preprint arXiv:1304.6008 [math.CO], 2013.

%H Martin Griffiths and Nick Lord, <a href="http://www.jstor.org/stable/23248614">The hook-length formula and generalised Catalan numbers</a>, The Mathematical Gazette Vol. 95, No. 532 (March 2011), pp. 23-30

%H R. Kenyon, J. Miller, S. Sheffield, and D. B. Wilson, <a href="http://arxiv.org/abs/1511.04068">Bipolar orientations on planar maps and SLE_12</a>, arXiv preprint arXiv:1511.04068 [math.PR], 2015. Also <a href="https://doi.org/10.1214/18-AOP1282">The Annals of Probability</a> (2019) Vol. 47, No. 3, 1240-1269.

%H J. B. Lewis, <a href="http://arxiv.org/abs/0909.4966">Pattern avoidance and RSK-like algorithms for alternating permutations and Young tableaux</a>, arXiv:0909.4966 [math.CO], 2009-2011. [From _Joel B. Lewis_, Oct 04 2009]

%H J. B. Lewis, <a href="https://dspace.mit.edu/handle/1721.1/73444">Pattern Avoidance for Alternating Permutations and Reading Words of Tableaux</a>, Ph. D. Dissertation, Department of Mathematics, MIT, 2012. - From _N. J. A. Sloane_, Oct 12 2012

%H Andrew Lohr, <a href="https://arxiv.org/abs/1805.00076">Several Topics in Experimental Mathematics</a>, arXiv:1805.00076 [math.CO], 2018.

%H Michaël Moortgat, <a href="https://cla.tcs.uj.edu.pl/history/2020/pdfs/CLA_Moortgat.pdf">The Tamari order for D^3 and derivability in semi-associative Lambek-Grishin Calculus</a>, 15th Workshop: Computational Logic and Applications (CLA 2020).

%H Maya Sankar, <a href="https://arxiv.org/abs/1910.08895">Further Bijections to Pattern-Avoiding Valid Hook Configurations</a>, arXiv:1910.08895 [math.CO], 2019.

%H S. Snover, <a href="/A005789/a005789.pdf">Letter to N. J. A. Sloane, May 1991</a>

%H R. A. Sulanke, <a href="https://doi.org/10.1016/j.tcs.2005.08.014">Three-dimensional Narayana and Schröder numbers</a>, Theoretical Computer Science, Volume 346, Issues 2-3, 28 November 2005, Pages 455-468.

%H R. A. Sulanke, <a href="https://doi.org/10.37236/1807">Generalizing Narayana and Schroeder Numbers to Higher Dimensions</a>, Electron. J. Combin. 11 (2004), Research Paper 54, 20 pp. (see page 16)

%H S. F. Troyer and S. L. Snover, <a href="/A005789/a005789_1.pdf">m-Dimensional Catalan numbers</a>, Preprint, 1989. (Annotated scanned copy)

%H Wolfgang Unger, <a href="http://arxiv.org/abs/1411.4493">Combinatorics of Lattice QCD at Strong Coupling</a>, arXiv:1411.4493 [hep-lat], 2014.

%H Manuel Wettstein, <a href="http://arxiv.org/abs/1602.07235">Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers</a>, arXiv:1602.07235 [cs.CG], 2016 and <a href="http://dx.doi.org/10.1007/s00454-017-9896-5">Discr. Comp. Geom. 58 (2017) 505-525</a>.

%H Sherry H. F. Yan, <a href="https://doi.org/10.37236/3243">On Wilf equivalence for alternating permutations</a>, Elect. J. Combinat.; 20 (2013), #P58.

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

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

%F 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

%F a(n) ~ 3^(3*n+1/2) / (Pi*n^4). - _Vaclav Kotesovec_, Nov 13 2014

%F a(n) = 2*A001700(n+1)*A001764(n+1)/(3*(3*n+1)*(3*n+2)). - _R. J. Mathar_, Aug 10 2015

%F 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

%F G.f.: x*3F2(4/3,5/3,1;4,3;27x). - _R. J. Mathar_, Aug 10 2015

%F E.g.f.: 2F2(1/3,2/3; 2,3; 27*x). - _Ilya Gutkovskiy_, Oct 13 2017

%p a:= n-> (3*n)! *mul(i!/(n+i)!, i=0..2):

%p seq(a(n), n=0..20);  # _Alois P. Heinz_, Feb 23 2012

%t Needs["Combinatorica`"]

%t Table[ NumberOfTableaux@ {n, n, n}], {n, 17}] (* _Robert G. Wilson v_, Nov 15 2006 *)

%t Table[2*(3*n)!/(n!*(n+1)!*(n+2)!),{n,1,20}] (* _Vaclav Kotesovec_, Nov 13 2014 *)

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

%o (Magma) [2*Factorial(3*n)/(Factorial(n)*Factorial(n+1)*Factorial(n+2)): n in [0..20]]; // _Vincenzo Librandi_, Oct 14 2017

%o (PARI) a(n) = 2*(3*n)!/(n!*(n+1)!*(n+2)!); \\ _Altug Alkan_, Mar 14 2018

%Y A row of A060854.

%Y A subset of A025035.

%Y See A268538 for primitive terms.

%K nonn,easy,walk,nice

%O 0,3

%A _N. J. A. Sloane_

%E Added a(0), merged A151334 into this one. - _N. J. A. Sloane_, Feb 24 2016