Order polynomial

Remarks

Such a polynomial exists, and it has degree $p$ with leading coefficient $e(P)/p!$, where $e(P)$ is the number of linear extensions of $P$.

Example: for the chain $x_1 < x_2 < \cdots < x_p$, $\Omega(P, m) = \binom{m + p - 1}{p}$. Check: an order-preserving map is a weakly increasing sequence $f(x_1) \le \cdots \le f(x_p)$ in $[m]$, that is, a multiset of size $p$ from $m$ values; the leading coefficient is $1/p!$, and $e(P) = 1$.

Non-example: the count $m^p$ of all maps $P \to [m]$ is not the order polynomial of the chain when $p \ge 2$. It also counts maps that break the order, such as $f(x_1) = 2$, $f(x_2) = 1$.

The strict order polynomial $\Omega^\circ(P, m)$ counts the maps with $x < y \Rightarrow f(x) < f(y)$. Stanley's reciprocity theorem says $\Omega^\circ(P, t) = (-1)^p \, \Omega(P, -t)$.