Positivity problems in enumerative and algebraic combinatorics

Theme 1.7: Permutation patterns and Stieltjes moment sequences, coefficientwise Hankel total positivity

← Back to Theme 1: Stieltjes Moment Sequences

Open

P1.7.1 The permutation patterns conjecture

Let \(\sigma,\pi\) be two permutations. \(\sigma\) is said to contain pattern \(\pi\) if there is a subsequence of \(\sigma\) that has the same relative order as \(\pi\). Let \({\rm Av}_n(\pi)\) denote the set of all permutations in \(\mathfrak{S}_n\) avoiding the pattern \(\pi\). See Wikipedia page.

Conjecture: For any permutation \(\pi\), the sequence \(\left({\rm Av}_n(\pi)\right)_{n\geq 0}\) is a Stieltjes moment sequence.

Origin: Posed by Natasha Blitvić, Slim Kammoun, Einar Stiengrı́msson, Alin Bostan, Andrew Elvey Price, Tony Guttmann, Jean-Marie Maillard, Nathan Clisby, Andrew Conway, Yuma Inoue

Before stating the next two conjectures we introduce some notation. In [Claesson (2001), Proposition 1] and [Claesson and Mansour (2002), Proposition 2] it was shown that with respect to being equidistributed, the twelve vincular patterns of the form \(a-bc\) or \(bc-a\) fall into the three classes \[\{1-23, 3-21, 12-3, 32-1\}\] \[\{1-32, 3-12, 21-3, 23-1\}\] \[\{2-13, 2-31, 13-2, 31-2\}\] Claesson and Mansour refer to these classes as Class 1, 2 and 3, respectively. We follow them and let \(P_n^{(1)}(x), P_n^{(2)}(x), P_n^{(3)}(x)\) denote the generating polynomials of these three classes, respectively.

Open

P1.7.2 Distribution of vincular patterns: Stieltjes moment sequences

(P1.7.2a) Conjecture: For all \(x\geq 0\), the sequence of polynomials \(\left(P_n^{(1)}(x)\right)_{n\geq 0}\) is a Stieltjes moment sequence.
See FindStat St000357, OEIS A260665.

(P1.7.2b) Conjecture: For all \(x\geq 0\), the sequence of polynomials \(\left(P_n^{(2)}(x)\right)_{n\geq 0}\) is a Stieltjes moment sequence.
See FindStat St000359, OEIS A260670.

Origin: Posed by Bishal Deb in [Deb (2025), Conjecture A.2]

Open

P1.7.3 Distribution of vincular patterns: coefficientwise Hankel total positivity

(P1.7.3a) Conjecture: The sequence of polynomials \(\left(P_n^{(1)}(x+1)\right)_{n\geq 0}\) is coefficientwise Hankel totally positive with respect to the variable \(x\).

(P1.7.3b) Conjecture: The sequence of polynomials \(\left(P_n^{(2)}(x+1)\right)_{n\geq 0}\) is coefficientwise Hankel totally positive with respect to the variable \(x\).

Origin: Posed by Bishal Deb in [Deb (2025), Conjecture A.3]

Open

P1.7.4 Consecutive patterns with overlaps

Fix a consecutive permutation pattern \(\pi\) of length \(k\). Let \(a_n^{(\pi,m)}\) be the number of permutations of length \(k + n(k - m)\) covered by \(\pi\) with overlaps \(m\) (\(m \leq k\)).

Conjecture: The sequence \(\left(a_n^{(\pi,m)}\right)_{n\geq 0}\) is a Hamburger moment sequence.

Origin: Posed by Natasha Blitvić, Slim Kammoun, Einar Stiengrı́msson in [Blitvić, Kammoun, Stiengrı́msson, Conjecture 1]

Open

P1.7.5 Baxter permutations

A permutation \( \pi \in \mathfrak{S}_n \) is a Baxter permutation if it avoids the vincular patterns \(2-41-3\) and \(3-14-2\).

The number of Baxter permutations of length \( n\), denoted \( B_n \), is given by the Baxter number \(B_0 =1\) and for \(n\geq 1\) \[ B_n = \sum_{k=1}^{n} \dfrac{\binom{n+1}{k-1}\binom{n+1}{k}\binom{n+1}{k+1}}{\binom{n+2}{1}\binom{n+2}{2}}. \]

(P.1.7.5e) Conjecture: The even subsequence \((B_{2n})_{n\geq 0}\) of the Baxter numbers forms a Stieltjes moment sequence.

(P.1.7.5o) Conjecture: The odd subsequence \((B_{2n+1})_{n\geq 0}\) of the Baxter numbers forms a Stieltjes moment sequence.

Origin: Posed by Stoyan Dimitrov, Bishal Deb, Alan Sokal

Remark:

For both sequences \((B_{2n})_{n\geq 0}\) and \((B_{2n+1})_{n\geq 0}\), we computed the first 150 terms of their S-fractions and we notice that these are non-negative.

📩 Contribute to a problem? Found a partial result, a counterexample, or a new reference? Email the maintainer