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 ${\displaystyle 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.

Let ${\displaystyle P}$ be a finite poset with ${\displaystyle p}$ elements denoted ${\displaystyle x,y\in P}$, and let ${\displaystyle [n]=\{1<2<\ldots <n\}}$ be a chain with ${\displaystyle n}$ elements. A map ${\displaystyle \phi :P\to [n]}$ is order-preserving if ${\displaystyle x\leq y}$ implies ${\displaystyle \phi (x)\leq \phi (y)}$. The number of such maps grows polynomially with ${\displaystyle n}$, and the function that counts their number is the order polynomial ${\displaystyle \Omega (n)=\Omega (P,n)}$.

Similarly, we can define an order polynomial that counts the number of strictly order-preserving maps ${\displaystyle \phi :P\to [n]}$, meaning ${\displaystyle x<y}$ implies ${\displaystyle \phi (x)<\phi (y)}$. The number of such maps is the strict order polynomial ${\displaystyle \Omega ^{\circ }\!(n)=\Omega ^{\circ }\!(P,n)}$.

Both ${\displaystyle \Omega (n)}$ and ${\displaystyle \Omega ^{\circ }\!(n)}$ have degree ${\displaystyle p}$. The order-preserving maps generalize the linear extensions of ${\displaystyle P}$, the order-preserving bijections ${\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}$. In fact, the leading coefficient of ${\displaystyle \Omega (n)}$ and ${\displaystyle \Omega ^{\circ }\!(n)}$ is the number of linear extensions divided by ${\displaystyle p!}$.

Letting ${\displaystyle P}$ be a chain of ${\displaystyle p}$ elements, we have

${\displaystyle \Omega (n)={\binom {n+p-1}{p}}=\left(\!\left({n \atop p}\right)\!\right)}$ and ${\displaystyle \Omega ^{\circ }(n)={\binom {n}{p}}.}$

There is only one linear extension (the identity mapping), and both polynomials have leading term ${\displaystyle {\tfrac {1}{p!}}n^{p}}$.

Letting ${\displaystyle P}$ be an antichain of ${\displaystyle p}$ incomparable elements, we have ${\displaystyle \Omega (n)=\Omega ^{\circ }(n)=n^{p}}$. Since any bijection ${\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}$ is (strictly) order-preserving, there are ${\displaystyle p!}$ linear extensions, and both polynomials reduce to the leading term ${\displaystyle {\tfrac {p!}{p!}}n^{p}=n^{p}}$.