login
Triangle read by rows: Table III.5 of Myriam de Sainte-Catherine's 1983 thesis.
6

%I #77 Sep 19 2024 16:10:18

%S 1,0,1,1,0,1,0,2,0,1,1,0,5,0,1,0,3,0,14,0,1,1,0,14,0,42,0,1,0,4,0,84,

%T 0,132,0,1,1,0,30,0,594,0,429,0,1,0,5,0,330,0,4719,0,1430,0,1,1,0,55,

%U 0,4719,0,40898,0,4862,0,1,0,6,0,1001,0,81796,0,379236,0,16796,0,1,1,0,91,0,26026,0,1643356,0,3711916,0,58786,0,1

%N Triangle read by rows: Table III.5 of Myriam de Sainte-Catherine's 1983 thesis.

%C I have a photocopy of certain pages of the thesis, but unfortunately not enough to find the definition of this table. I have written to the author.

%C (Added later) However, _Alois P. Heinz_ found a formula involving Catalan numbers which matches all the data and is surely correct, so the triangle is no longer a mystery.

%C Reading upwards along antidiagonals gives A123352.

%C From _Petros Hadjicostas_, Sep 04 2019: (Start)

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

%C 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)." In Section 6 of their paper, they give an interpretation of this formula in terms of Pfaffians and perfect matchings.

%C It turns out that for the current array, T(n,k) = b_{k, (n-k)/2} if n-k is even, and 0 otherwise (for n >= 0 and 0 <= k <= n). It is unknown, however, what kind of interpretation Myriam de Sainte-Catherine gave to the number T(n,k) three years earlier in her 1983 Ph.D. dissertation. It may be distantly related to the numbers b_{n,k} that are found in her 1986 paper with G. Viennot.

%C (End)

%C The T(n, k) for n and k same parity are the numbers in the upper triangle of the Catalan Number Wall in "Number Walls in Combinatorics". Thus 0 = T(n-1, k+1)*T(n+1, k-1) - T(n-1, k-1)*T(n+1, k+1) + T(n, k)^2 for all n, k. - _Michael Somos_, Aug 15 2023

%D Myriam de Sainte-Catherine, Couplages et Pfaffiens en Combinatoire, Physique et Informatique. Ph.D. Dissertation, Université Bordeaux I, 1983.

%H Alois P. Heinz, <a href="/A185249/b185249.txt">Rows n = 0..100, flattened</a>

%H M. de Sainte-Catherine and G. Viennot, <a href="https://doi.org/10.1007/BFb0072509">Enumeration of certain Young tableaux with bounded height</a>, in: G. Labelle and P. Leroux (eds), <a href="https://doi.org/10.1007/BFb0072503">Combinatoire énumérative</a>, Lecture Notes in Mathematics, vol. 1234, Springer, Berlin, Heidelberg, 1986, pp. 58-67.

%H M. Somos, <a href="https://grail.eecs.csuohio.edu/~somos/nwic.html">Number Walls in Combinatorics</a>, 2000.

%F T(n,k) = Product_{1 <= i <= j <= k} (n-k + i + j)/(i + j) if n - k is even, and = 0 otherwise (for n >= 0 and 0 <= k <= n). - _Petros Hadjicostas_, Sep 04 2019

%e Triangle begins:

%e 1

%e 0 1

%e 1 0 1

%e 0 2 0 1

%e 1 0 5 0 1

%e 0 3 0 14 0 1

%e 1 0 14 0 42 0 1

%e 0 4 0 84 0 132 0 1

%e 1 0 30 0 594 0 429 0 1

%e 0 5 0 330 0 4719 0 1430 0 1

%e 1 0 55 0 4719 0 40898 0 4862 0 1

%e 0 6 0 1001 0 81796 0 379236 0 16796 0 1

%e 1 0 91 0 26026 0 1643356 0 3711916 0 58786 0 1

%e ...

%p with(LinearAlgebra):

%p ctln:= proc(n) option remember; binomial(2*n, n)/(n+1) end:

%p T := proc(n, k)

%p if n=k then 1

%p elif irem(n+k, 2)=1 then 0

%p else Determinant(Matrix((n-k)/2, (i, j)-> ctln(i+j-1+k)))

%p fi

%p end:

%p seq(seq(T(n,k), k=0..n), n=0..12); # _Alois P. Heinz_, Feb 15 2011

%t t[n_, n_] = 1; t[n_, k_] /; Mod[n+k, 2] == 1 = 0; t[n_, k_] := Array[CatalanNumber[#1 + #2 - 1 + k]&, {(n-k)/2, (n-k)/2}] // Det; Table[t[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jan 14 2014, after _Alois P. Heinz_ *)

%o (PARI) {T(n, k) = if((n-k)%2||k<0||k>n, 0, prod(i=1, k, prod(j=i, k, (n-k+i+j)/(i+j))))}; /* _Michael Somos_, Aug 15 2023 */

%Y Diagonals give A000108, A005700, A006149, A006150, A006151, A000330, A006858, A091962.

%Y Row sums give A186232. Nonzero diagonals give columns in A078920.

%Y Cf. A179898.

%K tabl,nonn

%O 0,8

%A _N. J. A. Sloane_, Feb 15 2011

%E Typo in data corrected by _Alois P. Heinz_, Feb 15 2011