Explicit formula for the shuffle-lattice interval polynomial $G_{n-1,1}(x,y)$

The interval polynomial of the one-letter shuffle lattice

Let $A=\{a_1,\ldots,a_{n-1}\}$ and $B=\{b\}$. A word in $\mathsf{Shuf}(n-1,1)$ is a shuffle of a subword of $a_1\cdots a_{n-1}$ with either the empty word or $b$. The order is generated by deleting letters of $A$ and inserting the letter $b$.

For comparable words $u\preceq v$, define

$$\begin{aligned} &G_{n-1,1}(x,y)\\ &=\sum_{u\preceq v}x^{\operatorname{rk}(u)} y^{n-\operatorname{rk}(v)}. \end{aligned}$$

We prove the conjectured identity

$$\begin{aligned} &G_{n-1,1}(x,y)\\ &=(x+y+1)^{n-2}\bigl(x^2+y^2+1\\ &\qquad\quad+(n+1)(xy+x+y)\bigr) \end{aligned}$$

for every $n>0$.

For $n=1$, the shuffle lattice is the two-element chain $\varnothing\prec b$. Its three intervals give

$$G_{0,1}(x,y)=x+y+1,$$

which is also the value of the displayed expression, since its parenthesized factor is $(x+y+1)^2$.

Now suppose $n\geq2$, put $m=n-1$, and write

$$z=x+y+1.$$

If a shuffle word contains a subset $S\subseteq A$ and contains $b$ with indicator $\epsilon\in\{0,1\}$, then the source rank formula is

$$\operatorname{rk}(u)=m-|S|+\epsilon.$$

We partition all intervals according to the occurrence of $b$ at their two endpoints.

First suppose neither endpoint contains $b$. If the lower word uses $S\subseteq A$, then the upper word uses an arbitrary subset $T\subseteq S$. Their total contribution is

$$\begin{aligned} &\sum_{S\subseteq A}x^{m-|S|} \sum_{T\subseteq S}y^{1+|T|}\\ &=y\sum_{s=0}^{m}\binom{m}{s}x^{m-s}(1+y)^s\\ &=yz^m. \end{aligned}$$

Next suppose the lower endpoint does not contain $b$, while the upper endpoint does. If the upper word uses a fixed $t$-element subset $T$, then $b$ has $t+1$ possible positions, and the lower subset may be any $S\supseteq T$. Since the upper corank is $t$, this contribution is

$$\begin{aligned} &\sum_{t=0}^{m}\binom{m}{t}(t+1)y^t(x+1)^{m-t}\\ &=z^m+my z^{m-1}\\ &=z^{m-1}(z+my). \end{aligned}$$

Finally suppose both endpoints contain $b$. A lower word using an $s$-element subset $S$ has $s+1$ possible positions for $b$. Once such a word is fixed, every subset $T\subseteq S$ gives exactly one upper word: delete the letters of $S\setminus T$ and retain $b$ in its induced position relative to the surviving letters. The contribution is therefore

$$\begin{aligned} &\sum_{s=0}^{m}\binom{m}{s}(s+1) x^{m-s+1}(1+y)^s\\ &=xz^m+mx(1+y)z^{m-1}\\ &=xz^{m-1}\bigl(z+m(1+y)\bigr). \end{aligned}$$

Adding the three disjoint cases gives

$$\begin{aligned} &G_{n-1,1}(x,y)\\ &=z^{m-1}\bigl(yz+z+my\\ &\qquad+xz+mx(1+y)\bigr)\\ &=z^{m-1}\left(z^2+m(x+y+xy)\right)\\ &=z^{n-2}\bigl(x^2+y^2+1\\ &\qquad+(n+1)(xy+x+y)\bigr), \end{aligned}$$

because $m=n-1$. This proves the conjecture in its full stated range.