Stieltjes moment sequences for pattern-avoiding permutations (Q2209890)

The paper starts with a detailed introduction and historical account on Stieltjes moment sequences. A sequence \((a_n)_{n\in\mathbb{N}}\) is called a Stieltjes moment sequence if \(a_n=\int_{\Gamma} x^n \, d\rho(x)\) for some \(\Gamma\subseteq[0,\infty)\) and for \(\rho(x)\) being a nonnegative measure on~\(\Gamma\). Equivalently, such sequences can be characterized by the total nonnegativity of their associated Hankel matrix (i.e., all of its minors have to be \(\geq0\)), or in terms of the continued fraction of their generating function. Certain sequences that arise in enumerative combinatorics are Stieltjes moment sequences, the most prominent example being the Catalan numbers. The authors use this instructive example to demonstrate the main techniques that will be employed in the paper, such as the Stieltjes inversion formula, manipulations of D-finite functions, etc. In the main part of the paper, the authors study sequences that count permutations avoiding certain patterns and find that many of them are Stieltjes moment sequences. Permutations avoiding the pattern \((123\ldots k)\) for specific integers~\(k\) are investigated in detail. They correspond to permutations whose longest increasing subsequence has length at most~\(k-1\). It is well-known that the case \(k=3\) corresponds to the previously discussed sequence of Catalan numbers. The authors continue to deal with the cases \(4\leq k\leq 8\) and derive D-finite differential equations satisfied by their generating functions, as well as expressions for their density functions. The differential operators annihilating the generating functions are analyzed in detail and striking connections with classical modular forms are revealed. Also it is found that the density functions are related to the expected distance of a random walk in the plane with \(k-1\) unit steps in random directions. Then the authors turn to a notoriously difficult example of a pattern avoiding sequence, namely the set of permutations avoiding the pattern \((1324)\). Currently only \(50\) terms of this sequence are known, its growth constant is not known exactly and it is even not known whether the generating function is D-finite or not (the latter case is commonly believed to be true). The authors apply their techniques to this sequence, in a non-rigorous and numerical way. Under the reasonable assumption that it is a Stieltjes moment sequence, they obtain better bounds on the growth constant and a quite accurate conjecture for its actual value. For this purpose they employ the fact that Stieltjes moment sequences are log-convex and therefore a lower bound on the growth rate can be given by \(a_n/a_{n-1}\).