A060854 Array T(m,n) read by antidiagonals: T(m,n) (m >= 1, n >= 1) = number of ways to arrange the numbers 1,2,...,m*n in an m X n matrix so that each row and each column is increasing.

1, 1, 1, 1, 2, 1, 1, 5, 5, 1, 1, 14, 42, 14, 1, 1, 42, 462, 462, 42, 1, 1, 132, 6006, 24024, 6006, 132, 1, 1, 429, 87516, 1662804, 1662804, 87516, 429, 1, 1, 1430, 1385670, 140229804, 701149020, 140229804, 1385670, 1430, 1, 1, 4862, 23371634, 13672405890, 396499770810, 396499770810, 13672405890, 23371634, 4862, 1

Offset: 1

Author

R. H. Hardin, May 03 2001

Keywords

• nonn
• tabl
• easy
• nice
• changed

Comments

Multidimensional Catalan numbers; a special case of the "hook-number formula".

Number of paths from (0,0,...,0) to (n,n,...,n) in m dimensions, all coordinates increasing: if (x_1,x_2,...,x_m) is on the path, then x_1 <= x_2 <= ... <= x_m. Number of ways to label an n by m array with all the values 1..n*m such that each row and column is strictly increasing. Number of rectangular Young Tableaux. Number of linear extensions of the n X m lattice (the divisor lattice of a number having exactly two prime divisors). - Mitch Harris, Dec 27 2005

Given m*n lines in a {(m + 1)(n - 1)}-dimensional space, T(m, n) is the number of {n*(m-1)-1}-dimensional spaces cutting these lines in points (see Fontanari and Castelnuovo). - Stefano Spezia, Jun 19 2022

Examples

			Array begins:
  1,   1,     1,         1,            1,                1, ...
  1,   2,     5,        14,           42,              132, ...
  1,   5,    42,       462,         6006,            87516, ...
  1,  14,   462,     24024,      1662804,        140229804, ...
  1,  42,  6006,   1662804,    701149020,     396499770810, ...
  1, 132, 87516, 140229804, 396499770810, 1671643033734960, ...
		

References

• Guido Castelnuovo, Numero degli spazi che segano più rette in uno spazio ad n dimensioni, Rendiconti della R. Accademia dei Lincei, s. IV, vol. V, 4 agosto 1889. In Guido Castelnuovo, Memorie scelte, Zanichelli, Bologna 1937, pp. 55-64 (in Italian).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 7.23.19(b).

Links

• Alois P. Heinz, Antidiagonals n = 1..36
• Albrecht Böttcher, Wiener-Hopf Determinants with Rational Symbols, Math. Nachr. 144 (1989), 39-64.
• Freddy Cachazo and Nick Early, Minimal Kinematics: An all k and n peek into Trop^+G(k,n), arXiv:2003.07958 [hep-th], 2020.
• Freddy Cachazo and Nick Early, Planar Kinematics: Cyclic Fixed Points, Mirror Superpotential, k-Dimensional Catalan Numbers, and Root Polytopes, arXiv:2010.09708 [math.CO], 2020.
• Freddy Cachazo and Nick Early, Biadjoint Scalars and Associahedra from Residues of Generalized Amplitudes, arXiv:2204.01743 [hep-th], 2022.
• Andrzej Dudek, Jarosław Grytczuk, Jakub Przybyło, and Andrzej Ruciński, Homogeneous substructures in random ordered hyper-matchings, arXiv:2507.20374 [math.CO], 2025. See p. 19.
• Nick Early, Planarity in Generalized Scattering Amplitudes: PK Polytope, Generalized Root Systems and Worldsheet Associahedra, arXiv:2106.07142 [math.CO], 2021, see p. 14.
• Ömer Eğecioğlu, On Böttcher's mysterious identity, Australasian Journal of Combinatorics, Volume 43 (2009), 307-316.
• Paul Drube, Generating Functions for Inverted Semistandard Young Tableaux and Generalized Ballot Numbers, arXiv:1606.04869 [math.CO], 2016.
• Claudio Fontanari, Guido Castelnuovo and his heritage: geometry, combinatorics, teaching, arXiv:2206.06709 [math.HO], 2022. See pp. 2-3.
• J. S. Frame, G. de B. Robinson and R. M. Thrall, The hook graphs of a symmetric group, Canad. J. Math. 6 (1954), pp. 316-324.
• Alexander Garver and Thomas McConville, Chapoton triangles for nonkissing complexes, Algebraic Combinatorics, 3 (2020), pp. 1331-1363.
• Katarzyna Górska and Karol A. Penson, Multidimensional Catalan and related numbers as Hausdorff moments, arXiv preprint arXiv:1304.6008 [math.CO], 2013.
• Owen John Levens, Joel Brewster Lewis, and Bridget Eileen Tenner, Global patterns in signed permutations, arXiv:2504.13108 [math.CO], 2025. See p. 18.
• Dimana Miroslavova Pramatarova, Investigating the Periodicity of Weighted Catalan Numbers and Generalizing Them to Higher Dimensions, MIT Res. Sci. Instit. (2025). See p. 5.
• Francisco Santos, Christian Stump, and Volkmar Welker, Noncrossing sets and a Graßmannian associahedron, in FPSAC 2014, Chicago, USA; Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, 2014, 609-620.
• Wikipedia, Hook length formula

Crossrefs

Rows give A000108 (Catalan numbers), A005789, A005790, A005791, A321975, A321976, A321977, A321978.

Diagonals give A039622, A060855, A060856.

Cf. A227578. - Alois P. Heinz, Jul 18 2013

Cf. A321716.

Programs

Maple

T:= (m, n)-> (m*n)! * mul(i!/(m+i)!, i=0..n-1):
seq(seq(T(n, 1+d-n), n=1..d), d=1..10);

Mathematica

maxm = 10; t[m_, n_] := Product[k!, {k, 0, n - 1}]*(m*n)! / Product[k!, {k, m, m + n - 1}]; Flatten[ Table[t[m + 1 - n, n], {m, 1, maxm}, {n, 1, m}]] (* Jean-François Alcover, Sep 21 2011 *)
Table[ BarnesG[n+1]*(n*(m-n+1))!*BarnesG[m-n+2] / BarnesG[m+2], {m, 1, 10}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jan 30 2016 *)

PARI

{A(i, j) = if( i<0 || j<0, 0, (i*j)! / prod(k=1, i+j-1, k^vecmin([k, i, j, i+j-k])))}; /* Michael Somos, Jan 28 2004 */

Formula

T(m, n) = 0!*1!*..*(n-1)! *(m*n)! / ( m!*(m+1)!*..*(m+n-1)! ).

T(m, n) = A000142(m*n)*A000178(m-1)*A000178(n-1)/A000178(m+n-1) = A000142(A004247(m, n)) * A007318(m+n, n)/A009963(m+n, n). - Henry Bottomley, May 22 2002

Extensions

More terms from Frank Ellermann, May 21 2001