# Order polynomial

The order polynomial is a polynomial studied in mathematics, in particular in algebraic graph theory and algebraic combinatorics. The order polynomial counts the number of order-preserving maps from a poset to a chain of length $n$. These order-preserving maps were first introduced by Richard P. Stanley while studying ordered structures and partitions as a Ph.D. student at Harvard University in 1971 under the guidance of Gian-Carlo Rota.

## Definition

Let $P$ be a finite poset with $p$ elements denoted $x,y\in P$, and let $[n]=\{1<2<\ldots <n\}$ be a chain $n$ elements. A map $\phi :P\to [n]$ is order-preserving if $x\leq y$ implies $\phi (x)\leq \phi (y)$. The number of such maps grows polynomially with $n$, and the function that counts their number is the order polynomial $\Omega (n)=\Omega (P,n)$.
Similarly, we can define an order polynomial that counts the number of strictly order-preserving maps $\phi :P\to [n]$, meaning $x<y$ implies $\phi (x)<\phi (y)$. The number of such maps is the strict order polynomial $\Omega ^{\circ }\!(n)=\Omega ^{\circ }\!(P,n)$.
Both $\Omega (n)$ and $\Omega ^{\circ }\!(n)$ have degree $p$. The order-preserving maps generalize the linear extensions of $P$, the order-preserving bijections $\phi :P{\stackrel {\sim }{\longrightarrow }}[p]$. In fact, the leading coefficient of $\Omega (n)$ and $\Omega ^{\circ }\!(n)$ is the number of linear extensions divided by $p!$.

## Examples

Letting $P$ be a chain of $p$ elements, we have
   $\Omega (n)={\binom {n+p-1}{p}}=\left(\!\left({n \atop p}\right)\!\right)$ and $\Omega ^{\circ }(n)={\binom {n}{p}}.$
There is only one linear extension (the identity mapping), and both polynomials have leading term ${\tfrac {1}{p!}}n^{p}$.
Letting $P$ be an antichain of $p$ incomparable elements, we have $\Omega (n)=\Omega ^{\circ }(n)=n^{p}$. Since any bijection $\phi :P{\stackrel {\sim }{\longrightarrow }}[p]$ is (strictly) order-preserving, there are $p!$ linear extensions, and both polynomials reduce to the leading term ${\tfrac {p!}{p!}}n^{p}=n^{p}$.

## Reciprocity theorem

There is a relation between strictly order-preserving maps and order-preserving maps:
    $\Omega ^{\circ }(n)=(-1)^{|P|}\Omega (-n).$
In the case that $P$ is a chain, this recovers the negative binomial identity. There are similar results for the chromatic polynomial and Ehrhart polynomial (see below), all special cases of Stanley's general Reciprocity Theorem.

## Connections with other counting polynomials
### Chromatic polynomial

The chromatic polynomial $P(G,n)$counts the number of proper colorings of a finite graph $G$ with $n$ available colors. For an acyclic orientation $\sigma$ of the edges of $G$, there is a natural "downstream" partial order on the vertices $V(G)$ implied by the basic relations $u>v$ whenever $u\rightarrow v$ is a directed edge of $\sigma$. (Thus, the Hasse diagram of the poset is a subgraph of the oriented graph $\sigma$.) We say $\phi :V(G)\rightarrow [n]$ is compatible with $\sigma$ if $\phi$ is order-preserving. Then we have
    $P(G,n)\ =\ \sum _{\sigma }\Omega ^{\circ }\!(\sigma ,n),$
where $\sigma$ runs over all acyclic orientations of G, considered as poset structures.

### Order polytope and Ehrhart polynomial

The order polytope associates a polytope with a partial order. For a poset $P$ with $p$ elements, the order polytope $O(P)$ is the set of order-preserving maps $f:P\to [0,1]$, where $[0,1]=\{t\in \mathbb {R} \mid 0\leq t\leq 1\}$ is the ordered unit interval, a continuous chain poset. More geometrically, we may list the elements $P=\{x_{1},\ldots ,x_{p}\}$, and identify any mapping $f:P\to \mathbb {R}$ with the point $(f(x_{1}),\ldots ,f(x_{p}))\in \mathbb {R} ^{p}$; then the order polytope is the set of points $(t_{1},\ldots ,t_{p})\in [0,1]^{p}$ with $t_{i}\leq t_{j}$ if $x_{i}\leq x_{j}$.
The Ehrhart polynomial counts the number of integer lattice points inside the dilations of a polytope. Specifically, consider the lattice $L=\mathbb {Z} ^{n}$ and a $d$-dimensional polytope $K\subset \mathbb {R} ^{d}$ with vertices in $L$; then we define
    $L(K,n)=\#(nK\cap L),$
the number of lattice points in $nK$, the dilation of $K$ by a positive integer scalar $n$. Ehrhart showed that this is a rational polynomial of degree $d$ in the variable $n$, provided $K$ has vertices in the lattice.
In fact, the Ehrhart polynomial of an order polytope is equal to the order polynomial of the original poset (with a shifted argument):
   $L(O(P),n)\ =\ \Omega (P,n{+}1).$
This is an immediate consequence of the definitions, considering the embedding of the $(n{+}1)$-chain poset $[n{+}1]=\{0<1<\cdots <n\}\subset \mathbb {R}$.