# Sum of order polynomials of a set of posets

Let $$n\in \mathbb{Z}_{>0}$$. For every subset $$S\subseteq \left[ n-1\right]$$ we define a poset $$P_S=\left([n],\le_{P_S}\right)$$ given by the covering relation $$\lessdot$$ which is defined as \begin{align*} &\forall i\in S & i+1&\lessdot i \\ &\forall i\in\left[n-1\right]\setminus S & i&\lessdot i+1\\ \end{align*}

For instance if $$n=3$$ we have the posets

## Useful Definitions

• A function $$f\colon P_S\to [m]$$ is called order-preserving for $$P_S$$, if for any $$x,y\in P_S$$ $$x<_{P_S}y\implies f(x)\le f(y),$$ where $$m\in\mathbb{Z_{>0}}$$.
• We denote with $$\Omega(P_S,m)$$ the order polynomial of $$P_S$$ for $$m$$, i.e. $$\Omega(P_S,m)=\#\left\{ f\colon P_S\to [m]\,\mid f\;\; \text{is order-preserving}\right\}$$
• We call an order-preserving bijection $$\omega\colon P_S\to[n]$$ natural labeling of $$P_S$$.
• For any permutation $$w\in\mathcal{S}_n$$ we denote with $$\mathsf{Des}(w)$$ the descent set of $$w$$, i.e. $$\mathsf{Des}(w)=\left\{ i\in\left[n\right]\mid w\left(i\right)>w\left(i+1\right)\right\}$$
• We denote with $$A_S$$ the set of permutations that corresponds to the natural labelings of $$P_S$$, i.e. $$A_{S}=\left\{ w\in\mathcal{S}_{n}\mid w=\left(\omega\left(1\right),\omega\left(2\right),\dots,\omega\left(n\right)\right)\text{ for some natural labeling }\omega\text{ of }P_{S}\right\}$$

## The question

We want to calculate, for any given $$m\in\mathbb{Z}_{>0}$$ the sum of the order polynomials on the subsets $$S\subseteq[n-1]$$, i.e. $$\sum_{S\subseteq[n-1]}\Omega\left(P_{S},m\right).$$

## My progress

It seems that the requested sum is equal to

$$m(1+m)^{n-1},$$

but I did not manage to show it.

It is not hard to show that the set of all the natural labelings for a given subset $$S$$ has the same cardinality as the set of all permutations of $$[n]$$ with descent set equal to $$S$$, i.e. $$\#A_S=\#\left\{ \omega\colon P_{S}\to[n]\mid\omega\;\text{natural labeling}\right\} =\#\left\{ w\in\mathcal{S}_{n}\mid\mathsf{Des}\left(w\right)=S\right\} .$$

It is well known that $$\Omega\left(P_{S},m\right)=\sum_{w\in A_{S}}\binom{m+n-\mathsf{des}\left(w\right)-1}{n}.$$

I tried to use these facts in order to calculate the requested sum but I failed...

(P.S. I posted this question on Math Stack Exchange some days ago, without getting an answer. If this question does not fit here, I will agreeable delete it.)

• It should probably follow from the fact that every permutation of $[n]$ is a linear extension of a unique one of your $P_S$'s. Ah, well, this is basically what you wrote with $A_S$ being the set of permutations with descent set $S$. – Sam Hopkins Jan 26 at 23:40
• I deleted an answer which maybe had some ideas that could be made to work to explain your formula but wasn't right- Richard's answer is much better and very nice! – Sam Hopkins Jan 27 at 3:07
• @SamHopkins Thank you very much for the effort. Your ideas were also very useful! Of course Richard Stanley’s solution is very elegant! – asknohope Jan 27 at 12:41

The key result is equation (1) of the paper here, which expresses the chromatic polynomial $$\chi(G,m)$$ of a graph $$G$$ as a sum of strict order polynomials $$\overline{\Omega}(\overline{\mathcal{O}},m)$$ of the transitive (and reflexive) closures $$\overline{\mathcal{O}}$$ of the acyclic orientations $$\mathcal{O}$$ of $$G$$. If we take $$G$$ to be an $$n$$-vertex path, then we get $$\chi(G,m) = \sum_{S\subseteq[n-1]}\overline{\Omega}(P_S,m).$$ Now $$\chi(G,m)=m(m-1)^{n-1}$$. Moreover, by the reciprocity theorem for order polynomials, $$\overline{\Omega}(P_S,m) = (-1)^n\Omega(P_S,-m),$$ and the result follows.