Combinatorial Reciprocity for Monotone Triangles

Fischer, Ilse ; Riegler, Lukas

Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) (2012).

Résumé

The number of Monotone Triangles with bottom row $k_1 < k_2 < ⋯< k_n$ is given by a polynomial $\alpha (n; k_1,\ldots,k_n)$ in $n$ variables. The evaluation of this polynomial at weakly decreasing sequences $k_1 ≥k_2 ≥⋯≥k_n $turns out to be interpretable as signed enumeration of new combinatorial objects called Decreasing Monotone Triangles. There exist surprising connections between the two classes of objects – in particular it is shown that $\alpha (n;1,2,\ldots,n) = \alpha (2n; n,n,n-1,n-1,\ldots,1,1)$. In perfect analogy to the correspondence between Monotone Triangles and Alternating Sign Matrices, the set of Decreasing Monotone Triangles with bottom row $(n,n,n-1,n-1,\ldots,1,1)$ is in one-to-one correspondence with a certain set of ASM-like matrices, which also play an important role in proving the claimed identity algebraically. Finding a bijective proof remains an open problem.

Détail

DOI : 10.46298/dmtcs.3042