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

enter image description here

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


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.)

  • 1
    $\begingroup$ 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$. $\endgroup$ – Sam Hopkins Jan 26 at 23:40
  • 1
    $\begingroup$ 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! $\endgroup$ – Sam Hopkins Jan 27 at 3:07
  • $\begingroup$ @SamHopkins Thank you very much for the effort. Your ideas were also very useful! Of course Richard Stanley’s solution is very elegant! $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.