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 formula_1. 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 formula_2 be a finite poset with formula_3 elements denoted formula_4, and let formula_5 be a chain formula_1 elements. A map formula_7 is order-preserving if formula_8 implies formula_9. The number of such maps grows polynomially with formula_1, and the function that counts their number is the "order polynomial" formula_11. 
Similarly, we can define an order polynomial that counts the number of strictly order-preserving maps formula_12, meaning formula_13 implies formula_14. The number of such maps is the "strict order polynomial" formula_15.
Both formula_16 and formula_17 have degree formula_3. The order-preserving maps generalize the linear extensions of formula_2, the order-preserving bijections formula_20. In fact, the leading coefficient of formula_16 and formula_17 is the number of linear extensions divided by formula_23.
Examples.
Letting formula_24 be a chain of formula_3 elements, we have formula_26 and formula_27 There is only one linear extension (the identity mapping), and both polynomials have leading term formula_28.
Letting formula_24 be an antichain of formula_3 incomparable elements, we have formula_31. Since any bijection formula_20 is (strictly) order-preserving, there are formula_23 linear extensions, and both polynomials reduce to the leading term formula_34.
Reciprocity theorem.
There is a relation between strictly order-preserving maps and order-preserving maps:
In the case that formula_2 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 formula_37counts the number of proper colorings of a finite graph formula_38 with formula_1 available colors. For an acyclic orientation formula_40 of the edges of formula_38, there is a natural "downstream" partial order on the vertices formula_42 implied by the basic relations formula_43 whenever formula_44 is a directed edge of formula_40. (Thus, the Hasse diagram of the poset is a subgraph of the oriented graph formula_40.) We say formula_47 is compatible with formula_40 if formula_49 is order-preserving. Then we have 
where formula_40 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 formula_2 with formula_3 elements, the order polytope formula_54 is the set of order-preserving maps formula_55, where formula_56 is the ordered unit interval, a continuous chain poset. More geometrically, we may list the elements formula_57, and identify any mapping formula_58 with the point formula_59; then the order polytope is the set of points formula_60 with formula_61 if formula_62. 
The Ehrhart polynomial counts the number of integer lattice points inside the dilations of a polytope. Specifically, consider the lattice formula_63 and a formula_64-dimensional polytope formula_65 with vertices in formula_66; then we define
the number of lattice points in formula_68, the dilation of formula_69 by a positive integer scalar formula_1. Ehrhart showed that this is a rational polynomial of degree formula_64 in the variable formula_1, provided formula_69 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):formula_74This is an immediate consequence of the definitions, considering the embedding of the formula_75-chain poset formula_76.