[proofplan] We compare order-preserving maps with pairs consisting of a linear extension and a monotone sequence of values. Strictly increasing value sequences give a lower bound, while weakly increasing value sequences give an upper bound. Both bounding functions are $e(P)$ times a [binomial coefficient](/page/Binomial%20Coefficient) whose leading coefficient is $1/n!$, so the order polynomial is squeezed to have leading coefficient $e(P)/n!$. [/proofplan] [step:Dispose of the empty poset] If $P=\varnothing$, then $n=0$ and there is exactly one map from $P$ to $\{1,\dots,m\}$ for every positive integer $m$. Hence $\Omega_P(t)=1$. Also $P$ has exactly one linear extension, namely the empty total order, so $e(P)=1$. Therefore the coefficient of $t^0$ is \begin{align*} 1=\frac{e(P)}{0!}. \end{align*} Thus the theorem holds when $n=0$. For the rest of the proof, assume $n\ge 1$. [/step] [step:Record the set of linear extensions] Let $\mathcal L(P)$ denote the set of linear extensions of $P$, written as bijections \begin{align*} \lambda:\{1,\dots,n\}\to P \end{align*} such that, whenever $\lambda(i)\le_P \lambda(j)$, one has $i\le j$. Then \begin{align*} |\mathcal L(P)|=e(P). \end{align*} [/step] [step:Bound $\Omega_P(m)$ above by weakly increasing sequences along linear extensions] Fix a positive integer $m$. For each order-preserving map \begin{align*} f:P\to\{1,\dots,m\}, \end{align*} define a relation $\preceq_f$ on $P$ by declaring that $x\preceq_f y$ if and only if either $f(x)<f(y)$, or $f(x)=f(y)$ and $x\le_P y$. The relation $\preceq_f$ is a partial order on the finite set $P$. Reflexivity follows from $f(x)=f(x)$ and $x\le_P x$. If $x\preceq_f y$ and $y\preceq_f x$, then $f(x)=f(y)$, since strict inequalities in opposite directions are impossible; then $x\le_P y$ and $y\le_P x$, so antisymmetry of $\le_P$ gives $x=y$. For transitivity, suppose $x\preceq_f y$ and $y\preceq_f z$. If at least one of $f(x)<f(y)$ or $f(y)<f(z)$ holds, then $f(x)<f(z)$, so $x\preceq_f z$. If neither strict inequality holds, then $f(x)=f(y)=f(z)$ and $x\le_P y\le_P z$, so transitivity of $\le_P$ gives $x\le_P z$ and hence $x\preceq_f z$. By [citetheorem:8086] applied to the finite poset $(P,\preceq_f)$, choose a linear extension \begin{align*} \lambda_f:\{1,\dots,n\}\to P \end{align*} of $(P,\preceq_f)$. Since $x\le_P y$ implies $x\preceq_f y$ whenever $f(x)=f(y)$, and implies $f(x)\le f(y)$ by order-preservation, every comparison $x\le_P y$ is respected by $\lambda_f$. Thus $\lambda_f\in\mathcal L(P)$. Moreover, if $i\le j$, then the linear extension property for $\preceq_f$ prevents $f(\lambda_f(j))<f(\lambda_f(i))$, because that strict inequality would imply $\lambda_f(j)\preceq_f \lambda_f(i)$ and hence $j\le i$. Therefore the sequence \begin{align*} f(\lambda_f(1))\le \cdots \le f(\lambda_f(n)) \end{align*} is weakly increasing. Therefore the pair \begin{align*} \left(\lambda_f,\bigl(f(\lambda_f(1)),\dots,f(\lambda_f(n))\bigr)\right) \end{align*} belongs to the set of pairs consisting of a linear extension $\lambda\in\mathcal L(P)$ and a weakly increasing sequence \begin{align*} 1\le a_1\le \cdots \le a_n\le m. \end{align*} Since $f$ is recovered from this pair by the rule $f(\lambda(i))=a_i$, the assignment is injective. Hence \begin{align*} \Omega_P(m)\le e(P)\binom{m+n-1}{n}, \end{align*} because the number of weakly increasing sequences $1\le a_1\le\cdots\le a_n\le m$ is $\binom{m+n-1}{n}$. [guided] We want an upper bound that records each order-preserving map by a linear extension and a weakly increasing list of values. The delicate point is tie-breaking: arbitrary tie-breaking among equal values can destroy the linear-extension property. Instead, we build a new partial order that remembers both the original order and the value order. Fix an order-preserving map \begin{align*} f:P\to\{1,\dots,m\}. \end{align*} Define a relation $\preceq_f$ on $P$ as follows: for $x,y\in P$, declare $x\preceq_f y$ if and only if either $f(x)<f(y)$, or $f(x)=f(y)$ and $x\le_P y$. This relation says that smaller $f$-values must come first, while ties are ordered only when the original poset already forces an order. We verify that $\preceq_f$ is a partial order. It is reflexive because $f(x)=f(x)$ and $x\le_P x$, so $x\preceq_f x$. For antisymmetry, assume $x\preceq_f y$ and $y\preceq_f x$. The alternatives $f(x)<f(y)$ and $f(y)<f(x)$ cannot both occur, so the two comparisons force $f(x)=f(y)$. Then the definition of $\preceq_f$ gives $x\le_P y$ and $y\le_P x$, and antisymmetry of the original partial order $\le_P$ gives $x=y$. For transitivity, assume $x\preceq_f y$ and $y\preceq_f z$. If either comparison is strict at the level of $f$-values, then $f(x)<f(z)$, and hence $x\preceq_f z$. If neither comparison is strict, then $f(x)=f(y)=f(z)$ and $x\le_P y\le_P z$; transitivity of $\le_P$ gives $x\le_P z$, so again $x\preceq_f z$. Now $(P,\preceq_f)$ is a finite poset, so [citetheorem:8086] applies and gives a linear extension \begin{align*} \lambda_f:\{1,\dots,n\}\to P \end{align*} of $(P,\preceq_f)$. This chosen extension is also a linear extension of the original poset $(P,\le_P)$. Indeed, if $x\le_P y$, then order-preservation gives $f(x)\le f(y)$. If $f(x)<f(y)$, then $x\preceq_f y$ by definition; if $f(x)=f(y)$, then $x\preceq_f y$ because $x\le_P y$. Thus every original comparison is also a $\preceq_f$-comparison, so $\lambda_f\in\mathcal L(P)$. The same construction forces the values along $\lambda_f$ to be weakly increasing. If $i\le j$ and $f(\lambda_f(j))<f(\lambda_f(i))$, then the definition of $\preceq_f$ gives $\lambda_f(j)\preceq_f \lambda_f(i)$. Since $\lambda_f$ is a linear extension of $\preceq_f$, this would imply $j\le i$. Hence for $i<j$ the strict reverse inequality is impossible, and therefore \begin{align*} f(\lambda_f(1))\le f(\lambda_f(2))\le \cdots \le f(\lambda_f(n)). \end{align*} Thus each order-preserving map $f$ determines a pair \begin{align*} \left(\lambda_f,\bigl(f(\lambda_f(1)),\dots,f(\lambda_f(n))\bigr)\right), \end{align*} where $\lambda_f\in\mathcal L(P)$ and the second component is a weakly increasing sequence in $\{1,\dots,m\}$. The map $f$ is recovered uniquely from such a recorded pair by setting $f(\lambda(i))=a_i$ for every $i\in\{1,\dots,n\}$. Therefore this recording is injective. For each fixed linear extension $\lambda$, the number of weakly increasing sequences \begin{align*} 1\le a_1\le \cdots \le a_n\le m \end{align*} is the stars-and-bars number \begin{align*} \binom{m+n-1}{n}. \end{align*} There are $e(P)$ possible linear extensions. Since every order-preserving map injects into this set of recorded pairs, we obtain \begin{align*} \Omega_P(m)\le e(P)\binom{m+n-1}{n}. \end{align*} [/guided] [/step] [step:Bound $\Omega_P(m)$ below by strictly increasing sequences along linear extensions] For each linear extension $\lambda\in\mathcal L(P)$ and each strictly increasing sequence \begin{align*} 1\le a_1<\cdots<a_n\le m, \end{align*} define a map \begin{align*} f_{\lambda,a}:P\to\{1,\dots,m\} \end{align*} by \begin{align*} f_{\lambda,a}(\lambda(i))=a_i \end{align*} for every $i\in\{1,\dots,n\}$. If $x\le_P y$ and $x\neq y$, then the defining property of a linear extension gives indices $i<j$ such that $x=\lambda(i)$ and $y=\lambda(j)$, so \begin{align*} f_{\lambda,a}(x)=a_i<a_j=f_{\lambda,a}(y). \end{align*} Thus $f_{\lambda,a}$ is order-preserving. Distinct pairs $(\lambda,a)$ give distinct maps, because the values $a_1,\dots,a_n$ are all distinct, so the increasing order of the values recovers $\lambda$. Therefore \begin{align*} \Omega_P(m)\ge e(P)\binom{m}{n}, \end{align*} where $\binom{m}{n}=0$ when $m<n$ and otherwise counts strictly increasing sequences of length $n$ in $\{1,\dots,m\}$. [/step] [step:Compare leading coefficients in the polynomial inequalities] By [citetheorem:8134], there is a polynomial $\Omega_P(t)\in\mathbb Q[t]$ of degree $n$ such that $\Omega_P(m)$ is the number of order-preserving maps $P\to\{1,\dots,m\}$ for every positive integer $m$. From the previous two steps, for every positive integer $m$, \begin{align*} e(P)\binom{m}{n}\le \Omega_P(m)\le e(P)\binom{m+n-1}{n}. \end{align*} As polynomials in $t$, both binomial coefficient polynomials \begin{align*} \binom{t}{n} \end{align*} and \begin{align*} \binom{t+n-1}{n} \end{align*} have leading coefficient $1/n!$, since each is a product of $n$ linear factors with leading coefficient $1$, divided by $n!$. Let $c$ be the coefficient of $t^n$ in $\Omega_P(t)$. Since $\Omega_P(t)$ has degree at most $n$, the quotient $\Omega_P(m)/m^n$ tends to $c$ as $m\to\infty$. Likewise, each of the two binomial coefficient polynomials has degree $n$ and leading coefficient $1/n!$, so dividing the inequality by $m^n$ and letting $m\to\infty$ gives \begin{align*} \frac{e(P)}{n!}\le c\le \frac{e(P)}{n!}. \end{align*} Hence \begin{align*} c=\frac{e(P)}{n!}. \end{align*} This is exactly the claimed leading coefficient. [/step]