The denominator conjecture for pop-stacked permutation generating functions

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.