The in-degree enumeration formula for $(m,n)$-word lattices

For integers $m\geq0$ and $n\geq1$, let $\mathsf W(m,n)$ be the set of words $w=w_1\cdots w_n$ on $\{0,1,\ldots,m+1\}$ satisfying

$$\begin{gathered} w_1\neq m+1,\\ w_i=s\in\{1,\ldots,m\}\\ \Longrightarrow\quad w_j\geq s\quad(j<i). \end{gathered}$$

Order these words componentwise, and let $\operatorname{in}(w)$ be the number of words covered by $w$. Write $I_{m,n}(a)$ for the number of words with $\operatorname{in}(w)=a$. Then, for $0\leq a\leq n$,

$$\begin{aligned} I_{m,n}(a) &=\binom{m+a}{a}\binom na\\ &\quad-\binom{m+a-1}{m}\binom{n-1}{a-1}. \end{aligned}$$

At $a=0$, the second term is interpreted as zero. This proves Mühle's Conjecture 21, numbered Conjecture 5.6 in the preprint.

We use the usual convention that $\binom ur=0$ when $u\geq0$ and either $r<0$ or $r>u$.

The known counting sum

We recall the lower-cover description and counting argument of Mühle's Lemma 18 and Corollaries 19–20. Let $t(w)$ count the letters equal to $m+1$, and let $B(w)$ be the set of distinct letters of $w$ belonging to $\{1,\ldots,m\}$. Then

$$\operatorname{in}(w)=t(w)+|B(w)|.$$

Indeed, a letter $m+1$ at position $i$ can be lowered to the smallest earlier letter different from $m+1$; this earlier letter exists because $i>1$. Each such change gives a lower cover. For every $s\in B(w)$, lowering the last occurrence of $s$ to $s-1$ also gives a lower cover.

These are all the lower covers. To see this, take any $u<w$ and let $i$ be the greatest index with $u_i<w_i$. If $w_i=m+1$, validity of $u$ forces $u_i$ to be at most the smallest earlier non-$(m+1)$ letter of $w$. Thus $u$ lies below the corresponding listed cover. Otherwise $w_i=s\in\{1,\ldots,m\}$. There cannot be a later occurrence of $s$ in $w$, since it would be unchanged in $u$ and would violate the defining condition at that later position. Hence $i$ is the last occurrence of $s$, and $u$ again lies below a listed cover.

Fix $\operatorname{in}(w)=a$ and $|B(w)|=b$. There are $\binom mb$ choices for $B(w)$, and exactly $a-b$ letters are $m+1$. Their positions can be chosen in $\binom{n-1}{a-b}$ ways, since position $1$ is excluded. After these letters are removed, the remaining word is weakly decreasing, has length $n-a+b$, uses every member of $B(w)$, and may end in zeroes. Its multiplicities can be chosen in $\binom{n-a+b}{b}$ ways by stars and bars. If the remaining length is zero, the excluded-first-position condition makes the contribution zero.

Consequently, the published counting sum is

$$\begin{aligned} &I_{m,n}(a)\\ &=\sum_{b=0}^{a} \binom mb\binom{n-a+b}{b}\binom{n-1}{a-b}. \end{aligned} \tag{1}$$

Evaluation of the sum

Assume $1\leq a\leq n$. For $0\leq b\leq a$, the elementary identity

$$\begin{aligned} &\binom{n-a+b}{b}\binom{n-1}{a-b}\\ &\quad=\binom{n-1}{a}\binom ab\\ &\qquad+\binom{n-1}{a-1}\binom{a-1}{b-1} \end{aligned} \tag{2}$$

holds also at the endpoints. Away from $n=a,\ b=0$, both sides equal

$$\frac{(n-a+b)(n-1)!}{b!(a-b)!(n-a)!}.$$

The two terms on the right of (2) correspond to the two summands in $n-a+b=(n-a)+b$. At $n=a,\ b=0$, both sides of (2) are zero.

Two applications of Vandermonde's identity give

$$\begin{aligned} \sum_{b=0}^{a}\binom mb\binom ab &=\binom{m+a}{a},\\ \sum_{b=0}^{a}\binom mb\binom{a-1}{b-1} &=\binom{m+a-1}{a}. \end{aligned}$$

For example, these follow by taking the coefficient of $x^a$ in $(1+x)^m(1+x)^a$ and $(1+x)^m(1+x)^{a-1}$, respectively.

Substitution into (1) yields the positive form

$$\begin{aligned} I_{m,n}(a) &=\binom{n-1}{a}\binom{m+a}{a}\\ &\quad+\binom{n-1}{a-1}\binom{m+a-1}{a}. \end{aligned} \tag{3}$$

Using Pascal's identity on both factors involving adjacent upper indices transforms (3) into

$$\begin{aligned} I_{m,n}(a) &=\binom na\binom{m+a}{a}\\ &\quad-\binom{n-1}{a-1}\binom{m+a-1}{a-1}. \end{aligned}$$

Since $\binom{m+a-1}{a-1}=\binom{m+a-1}{m}$, this is the desired formula.

Finally, $a=0$ counts only the all-zero word, so its value is $1$, as asserted. The argument includes $m=0$, $n=1$, and $a=n$, without division by $m$ or $n-a$. If $n=0$, there is only the empty word, of in-degree zero; its counting polynomial is $1$. Thus the empty-word boundary is covered separately as well.