A078920 Upper triangle of Catalan Number Wall.

1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 14, 14, 4, 1, 1, 42, 84, 30, 5, 1, 1, 132, 594, 330, 55, 6, 1, 1, 429, 4719, 4719, 1001, 91, 7, 1, 1, 1430, 40898, 81796, 26026, 2548, 140, 8, 1, 1, 4862, 379236, 1643356, 884884, 111384, 5712, 204, 9, 1, 1, 16796, 3711916, 37119160, 37119160, 6852768, 395352, 11628, 285, 10, 1

Offset: 0

Author

Michael Somos, Dec 15 2002

Keywords

• easy
• nonn
• tabl

Comments

As square array: number of certain symmetric plane partitions, see Forrester/Gamburd paper.

Formatted as a square array, the column k gives the Hankel transform of the Catalan numbers (A000108) beginning at A000108(k); example: Hankel transform of [42, 132, 429, 1430, 4862, ...] is [42, 594, 4719, 26026, 111384, ...] (see A091962). - Philippe Deléham, Apr 12 2007

As square array T(n,k): number of all k-watermelons with a wall of length n. - Ralf Stephan, May 09 2007

Consider "Young tableaux with entries from the set {1,...,n}, strictly increasing in rows and not decreasing in columns. Note that usually the reverse convention between rows and columns is used." de Sainte-Catherine and Viennot (1986) proved that "the number b_{n,k} of such Young tableaux having only columns with an even number of elements and bounded by height p = 2*k" is given by b_{n,k} = Product_{1 <= i <= j <= n} (2*k + i + j)/(i + j)." It turns out that for the current array, T(n,k) = b(n-k,k) for n >= 0 and 0 <= k <= n. - Petros Hadjicostas, Sep 04 2019

As square array, b(k, n) = T(n+k-1, n) for k >= 1 and n >= 1 is the number of n-tuples P = (p_1, p_2, ..., p_n) of non-intersecting lattice paths that lie below the diagonal, such that each p_i starts at (i, i) and ends at (2n+k-i, 2n+k-i). (This is just a different way of looking at n-watermelons with a wall of length k since many of the steps of these paths are going to be fixed while the rest form an n-watermelon. See the Krattenthaler et al. paper.) Equivalently b(k, n) is the number of n-tuples (p_1, p_2, ..., p_n) of Dyck paths, each with 2k steps such that for every i (1 <= i <= n-1), p_i is included in p_{i+1}. A Dyck path p is said to be included in a Dyck path q if the height of path p after j steps is at most the height of path q after j steps, for all j (1 <= j <= 2k). - Farzan Byramji, Jun 17 2021

Examples

			Triangle T(n,k) (with rows n >= 0 and columns k >= 0) starts as follows:
  1;
  1,    1;
  1,    2,      1;
  1,    5,      3,       1;
  1,   14,     14,       4,      1;
  1,   42,     84,      30,      5,      1;
  1,  132,    594,     330,     55,      6,    1;
  1,  429,   4719,    4719,   1001,     91,    7,   1;
  1, 1430,  40898,   81796,  26026,   2548,  140,   8, 1;
  1, 4862, 379236, 1643356, 884884, 111384, 5712, 204, 9, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..100, flattened
• R. Bacher, Matrices related to the Pascal triangle, arXiv:math/0109013 [math.CO], 2001.
• Paul Barry, Notes on the Hankel transform of linear combinations of consecutive pairs of Catalan numbers, arXiv:2011.10827 [math.CO], 2020.
• M. de Sainte-Catherine and G. Viennot, Enumeration of certain Young tableaux with bounded height, in: G. Labelle and P. Leroux (eds), Combinatoire énumérative, Lecture Notes in Mathematics, vol. 1234, Springer, Berlin, Heidelberg, 1986, pp. 58-67.
• P. J. Forrester and A. Gamburd, Counting formulas associated with some random matrix averages, arXiv:math/0503002 [math.CO], 2005.
• P. J. Forrester and A. Gamburd, Counting formulas associated with some random matrix averages, J. Combin. Theory Ser. A 113(6) (2006), 934-951.
• M. Fulmek, Asymptotics of the average height of 2-watermelons with a wall, arXiv:math/0607163 [math.CO], 2006.
• M. Fulmek, Asymptotics of the average height of 2-watermelons with a wall, Electron. J. Combin. 14 (2007), R64.
• C. Krattenthaler, A. J. Guttmann and X. G. Viennot, Vicious walkers, friendly walkers and Young tableaux: II. With a wall, J. Phys. A: Math. Gen. 33 (2000), 8835-8866.
• Vincent Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, arXiv:1505.07665 [math.CO], 2015.
• Vincent Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, J. Combin. Theory Ser. A 155 (2018), 418-457.
• Michael Somos, Number Walls in Combinatorics.

Crossrefs

Columns are A000012, A000108, A005700, A006149, A006150, A006151.

Diagonals are A000027, A000330, A006858.

T(2n,n) gives A358597.

Cf. A123352.

Programs

Maple

T:= (n, k)-> mul(mul((i+j+2*k)/(i+j), j=i..n-k), i=1..n-k):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Sep 04 2019

Mathematica

T[n_, k_] := Product[(2*i+1)!*(2*n-2*i)!/(n-i)!/(n+i+1)!, {i, 0, k-1}]; Table[T[n, k], {n, 1, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 28 2015, adapted from PARI *)

PARI

T(n,k)=if(k<0 || k>n,0,prod(i=0,k-1,(2*i+1)!*(2*n-2*i)!/(n-i)!/(n+i+1)!))

PARI

{C(n)=if(n<0,0,(2*n)!/n!/(n+1)!)}; T(n,k)=if(k<0 || k>n,0,matdet(matrix(k,k,i,j,C(i+j-1+n-k))))

Sage

def A078920(n,k): return product( binomial(2*n-2*j, n-j)/binomial(n+j+1, n-j) for j in (0..k-1) )
flattened([[A078920(n,k) for k in (0..n)] for n in (0..10)]) # G. C. Greubel, Dec 17 2021

Formula

T(n,k) = Product_{i=1..n-k} Product_{j=i..n-k} (i+j+2*k)/(i+j). [corrected by Petros Hadjicostas, Jul 24 2019]

From G. C. Greubel, Dec 17 2021: (Start)

T(n, k) = Product_{j=0..k-1} binomial(2*n-2*j, n-j)/binomial(n+j+1, n-j).

T(n, k) = ((n+1)!/(n-k+1)!)*Product_{j=0..k-1} Catalan(n-j)/binomial(n+j+1, n-j). (End)

Extensions

T(0,0) = 1 prepended by Petros Hadjicostas, Jul 24 2019