Combinatorial investigation of q-analogs of two recursions for Catalan numbers with alternating signs
Theoretical Computer Science
Final Report Abstract
Zeilberger conjectured that if the integers {An}n≥1 are inductively defined via a recursion of Catalan numbers Cn with alternating signs, then the integers {An}n≥2 are increasing and positive. Motivated by his conjecture and Andrews’s open questions on the Koshy identity, we are primarily concerned with q-analogs of these two recursions of Catalan numbers with alternating signs. Here, the q-analog of a sequence of numbers or an identity is an extension of those by parameter q that naturally reduces to the original in the limit q → 1. First we have successively proved two q-analogs of Koshy identity in a combinatorial way and we answered two open questions from Andrews. We summarize the other two unsolved questions from Andrews as a stronger conjecture, which is, Conjecture. If n is odd, then for m ≥ n ≥ 1, the polynomial (1 + q^n) [m/n−1]q is unimodal. If n is n even, for any even j <> 0 and m ≥ n ≥ 1, the polynomial (1 + q^n) [j] q [m/n−1]q is unimodal. Second, it was shown that the number An counts the pairs (σn , rn ) where σn is a connected matching on [2n], and rn is an acyclic orientation of line graph L(σn ) that has a unique root labeled with (1, i) if (1, i) ∈ σn . We hoped that the q-analog An (q) of the number An would be a refined enumeration of such oriented graphs. However, it turns out that the q-analog An (q) of the number An has no statistic connection to the pairs (σn , rn), though An (q) is a monic unimodal palindromic polynomial; see [16] where Tevlin also independently considered such an extension. Third, if we replace the Catalan numbers Cn and the numbers An from the recursion by the central binomial coefficients Wn and the numbers Bn , we obtain an analogous recursion with alternating signs that was considered by Lassalle. He was motivated by the generalized Narayana polynomials, which were introduced in the context of the non-crossing partition lattice for the reflection group associated with a root system. We consider the numbers bn , which are bn = Bn /Wn and we have achieved our goal to connect the numbers bn with the numbers of pyramids via Cartier-Foata identity from the monoid theory, and by constructing a bijection between such pyramids and complete non-ambiguous trees, we have explained the ‘coincidence’ discovered by Aval-Boussicault-Bouvel-Silimbani on their way to count non-ambiguous trees. We further generalize the numbers bn as the Möbius functions on the interval [0,1] of the posets in an exponential structure. It comes as a surprise that the Euler numbers E2n−1 and the numbers bn respectively count the numbers of pyramids associated to two different exponential structures, one consists of the posets of set partitions of [2n] whose block sizes are even, while the other one consists of the posets of 2-partitions of [n]. Last but not least, motivated by the interesting connection between Euler numbers and zig-zag shape tableaux, we generalize Hamel and Goulden’s theorem on the outside decompositions, which greatly simplified the Schur function determinants and the enumeration of m-strip tableaux due to Baryshnikov and Romik.
Publications
- Equality of Shapley Value and Fair Proportion Index in Phylogenetic Trees, Journal of Mathematical Biology, 71(5), 1133-1147, 2015
Michael Fuchs and Emma Yu Jin
(See online at https://doi.org/10.1007/s00285-014-0853-0) - New proofs of two q-analogues of Koshy’s formula, Proceeding of the American Mathematical Society, 143(12), 5027-5042, 2015
Emma Yu Jin and Markus E. Nebel
(See online at https://doi.org/10.1090/proc/12627) - An asymptotic analysis of labeled and unlabeled k-trees, Algorithmica, 75(4), 579-605, 2016
Michael Drmota and Emma Yu Jin
(See online at https://doi.org/10.1007/s00453-015-0039-1) - Graph limits of random graphs from a subset of connected k-trees. Short version in: Analco 16
Michael Drmota, Emma Yu Jin and Benedikt Stufler
- Heaps and two exponential structures, European Journal of Combinatorics, 54, 87-102, 2016
Emma Yu Jin
(See online at https://doi.org/10.1016/j.ejc.2015.12.007) - Outside nested decompositions of skew diagrams and Schur function determinants
Emma Yu Jin
