Let F_k(x) denote the generating function for pop-stacked permutations with precisely k ascending runs. For each positive integer k, define the product D_k(x)=∏_i=1^k(1-ix)^k-i+1. Denominator conjecture. For all k, the rational generating function F_k(x) can be written as F_k(x)=fracN_k(x)D_k(x)=N_k(x)Big/∏_i=1^k(1-ix)^k-i+1, where N_k(x) is a polynomial of degree k(k+1)/2, equal to the degree of the denominator D_k(x).

The denominator conjecture for pop-stacked permutation generating functions

Claesson’s denominator conjecture asserts that the generating function for pop-stacked permutations with exactly $k$ ascending runs has denominator $\prod_{i=1}^k(1-ix)^{k-i+1}$ and a numerator of degree $k(k+1)/2$ . It remains stated as a conjecture in the available literature.

Known results

For each fixed $k$ , the generating function is rational, via a finite-automaton argument.
Rational fits were computed from the first $300$ terms for every $k\le 24$ .
Those fits were verified exactly for $k\le 6$ .
Explicit generating functions and the conjectured pattern are known in small cases.

Current status (as of August 2026): Rationality for each fixed $k$ and exact verification through $k\le 6$ are known, but the stated denominator formula and numerator-degree claim remain unproved, with no reported counterexample or verification.

Let F_k(x) enumerate pop-stacked permutations with exactly k ascending runs, and put D_k(x)=∏{i=1}^k(1−ix)^{k−i+1}, K=k(k+1)/2. We prove that F_k=N_k/D_k with deg N_k=K and, more strongly, lim{x→∞}F_k(x)=−1, [x^K]N_k(x)=(−1)^{K+1}∏_{j=1}^k j!.

By the source's overlapping-ballot characterization, such a permutation is equivalent to a surjective word w∈[k]^n in which the occurrence intervals of every adjacent pair of letters i,i+1 overlap. Failure of overlap has two disjoint orientations: every i precedes every i+1, or the converse. For a subset S of the k−1 adjacent edges and a choice ε of their orientations, let P(S,ε) be the resulting poset. Every such orientation is acyclic because the edge graph is a path. Inclusion–exclusion gives F_k(x)=Σ_{S⊆[k−1]}(−1)^{|S|} Σ_{ε∈{+,-}^S}G_{P(S,ε)}(x), where G_P enumerates surjective words respecting the precedence relations of P.

For any poset P on k elements, classify a compatible word by the order σ=(σ₁,…,σ_k) in which its distinct letters first occur. This order is a linear extension. Put I_j={σ₁,…,σ_j} and m_j=|Max_P(I_j)|. Between the first appearances of σ_j and σ_{j+1}, the permissible repeated letters are exactly Max_P(I_j); the same holds after the last first appearance. Therefore G_P(x)=x^k Σ_{σ∈Lin(P)} ∏_{j=1}^k(1−m_jx)^{-1}. Because 1≤m_j≤j, a factor 1−ix appears at most k−i+1 times in each denominator. Thus every denominator divides D_k, proving N_k=D_kF_k∈Z[x] and deg N_k≤K.

Furthermore, lim_{x→∞}G_P(x)=(−1)^k Σ_{σ∈Lin(P)}∏{j=1}^k1/|Max_P(I_j)|=(−1)^k. Indeed, delete a uniformly chosen maximal element at each step from P: the product is exactly the probability of the corresponding reverse linear extension, and these probabilities sum to one. Consequently lim{x→∞}F_k(x) =(−1)^k Σ_{S⊆[k−1]}(−1)^{|S|}2^{|S|} =(−1)^k(1−2)^{k−1} =−1. The numerator therefore has degree exactly K. Since the leading coefficient of D_k is (−1)^K∏{i=1}^k i^{k−i+1}=(−1)^K∏{j=1}^k j!, the stated numerator leading coefficient follows. This proves the complete conjecture for every k≥1.

A further conjectured numerator invariant also follows exactly. For k≥2, N_k(1)=2(−1)^{K−1}∏{j=1}^{k−1}j!. Indeed, a summand G_P has a pole of order k at x=1 precisely when m_j=|Max_P(I_j)|=1 for every j. Then every prefix ideal has a unique maximal element, which forces P to be a total chain. Among the oriented subforests of the path on [k], exactly two posets are total chains: the full path oriented consistently in either direction. Each has one linear extension and inclusion–exclusion sign (−1)^{k−1}. Consequently N_k(1)=2(−1)^{k−1}∏{i=2}^k(1−i)^{k−i+1} =2(−1)^{K−1}∏_{j=1}^{k−1}j!. For k=1, separately, N_1(1)=1. Thus the same argument proves the full denominator conjecture together with the exact numerator degree, leading coefficient, and coefficient sum.

The denominator conjecture for pop-stacked permutation generating functions

Progress summary

Primary source

Solutions 1