[proofplan] We first handle the empty poset, then assume $P$ has $n\ge 1$ elements. Choose a natural labeling of $P$ using a linear extension, and break ties in every order-preserving map by this labeling. This partitions all order-preserving maps $P\to\{1,\dots,m\}$ into finitely many classes indexed by linear extensions, and each class is counted by a stars-and-bars [binomial coefficient](/page/Binomial%20Coefficient). Summing these binomial coefficients gives a polynomial in $m$, and the positive leading coefficient shows that its degree is exactly $n=|P|$. [/proofplan] [step:Handle the empty poset] If $P=\varnothing$, then for every positive integer $m$ there is exactly one function \begin{align*} \varnothing \to \{1,\dots,m\}, \end{align*} and it is order-preserving. Hence $\Omega_P(m)=1$ for every positive integer $m$. The polynomial $Q_P(t)=1$ has degree $0=|P|$ under the stated convention. [/step] [step:Choose a natural labeling from a linear extension] Assume now that $P$ is nonempty, and set $n:=|P|$. Since $P$ is finite, [citetheorem:8086] applies and gives a linear extension of $P$. Choose one and write it as \begin{align*} p_1,p_2,\dots,p_n. \end{align*} Define the labeling $\lambda:P\to \{1,\dots,n\}$ by $\lambda(p_i)=i$ for $1\le i\le n$. Because $p_1,\dots,p_n$ is a linear extension, whenever $x<y$ in $P$ one has \begin{align*} \lambda(x)<\lambda(y). \end{align*} We call such a labeling natural. Let $\mathcal{L}(P)$ denote the finite set of all linear extensions of $P$, written as ordered lists \begin{align*} \pi=(q_1,\dots,q_n) \end{align*} of the elements of $P$. [/step] [step:Partition order-preserving maps by tie-broken linear extensions] For a positive integer $m$, let $\mathcal{O}_m(P)$ denote the set of order-preserving maps \begin{align*} f:P\to \{1,\dots,m\}. \end{align*} For $f\in \mathcal{O}_m(P)$, define a total order $<_f$ on $P$ by declaring \begin{align*} x<_f y \end{align*} if either $f(x)<f(y)$, or $f(x)=f(y)$ and $\lambda(x)<\lambda(y)$. This total order is a linear extension of $P$. Indeed, if $x<y$ in $P$, then order-preservation gives $f(x)\le f(y)$. If $f(x)<f(y)$, then $x<_f y$. If $f(x)=f(y)$, then naturality of $\lambda$ gives $\lambda(x)<\lambda(y)$, so again $x<_f y$. For $\pi=(q_1,\dots,q_n)\in \mathcal{L}(P)$, define \begin{align*} \mathcal{O}_m(P,\pi)=\{f\in \mathcal{O}_m(P): q_1<_f q_2<_f \cdots <_f q_n\}. \end{align*} The construction above assigns each $f\in\mathcal{O}_m(P)$ to exactly one linear extension, so \begin{align*} \mathcal{O}_m(P)=\bigsqcup_{\pi\in \mathcal{L}(P)} \mathcal{O}_m(P,\pi). \end{align*} [guided] The main bookkeeping issue is that an order-preserving map may assign the same value to several elements of $P$. To make a unique linear order from such a map, we need a deterministic tie-breaker. The natural labeling $\lambda:P\to\{1,\dots,n\}$ supplies exactly that. Fix a positive integer $m$ and an order-preserving map \begin{align*} f:P\to \{1,\dots,m\}. \end{align*} We define $x<_f y$ when $f(x)$ is smaller than $f(y)$, and if the two values are equal, when the label of $x$ is smaller than the label of $y$. This produces a total order because any two distinct elements of $P$ have either different $f$-values or different labels. We must check that this total order respects the original partial order on $P$. Suppose $x<y$ in $P$. Since $f$ is order-preserving, \begin{align*} f(x)\le f(y). \end{align*} If $f(x)<f(y)$, the definition gives $x<_f y$. If $f(x)=f(y)$, then the natural labeling satisfies \begin{align*} \lambda(x)<\lambda(y), \end{align*} so the tie-breaking rule again gives $x<_f y$. Thus $<_f$ is a linear extension of $P$. Now define $\mathcal{O}_m(P,\pi)$ to be the set of maps whose tie-broken order is the particular linear extension $\pi$. Because every map has exactly one tie-broken total order, the sets $\mathcal{O}_m(P,\pi)$ are disjoint and their union is all of $\mathcal{O}_m(P)$. Hence counting order-preserving maps reduces to counting each fiber of this partition. [/guided] [/step] [step:Count one fiber by strict rises at descents] Fix a linear extension $\pi=(q_1,\dots,q_n)\in \mathcal{L}(P)$. Define its descent set with respect to $\lambda$ by $\operatorname{Des}(\pi)=\{i\in\{1,\dots,n-1\}:\lambda(q_i)>\lambda(q_{i+1})\}$, and set $d(\pi):=|\operatorname{Des}(\pi)|$. A map $f\in\mathcal{O}_m(P,\pi)$ is equivalent to a sequence $1\le a_1\le a_2\le \cdots \le a_n\le m$ with $a_i<a_{i+1}\quad\text{for every }i\in\operatorname{Des}(\pi)$, by setting $a_i=f(q_i)$. The weak inequalities come from the fact that $\pi$ is the order determined by increasing $f$-values. At a descent $i$, equality would force the tie-breaker to place $q_{i+1}$ before $q_i$, because $\lambda(q_{i+1})<\lambda(q_i)$; hence strict inequality is necessary. Conversely, these inequalities ensure that the tie-broken order associated to $f(q_i)=a_i$ is exactly $\pi$. Define $D_i:=|\{j\in\operatorname{Des}(\pi):j<i\}|$ for $1\le i\le n$, and define $c_i:=a_i-D_i$. If $i\in\operatorname{Des}(\pi)$, then $a_{i+1}\ge a_i+1$ and $D_{i+1}=D_i+1$, so $c_{i+1}\ge c_i$. If $i\notin\operatorname{Des}(\pi)$, then $a_{i+1}\ge a_i$ and $D_{i+1}=D_i$, so again $c_{i+1}\ge c_i$. Also $1\le c_1$ and $c_n\le M$, where $M:=m-d(\pi)$. Thus the map $(a_1,\dots,a_n)\mapsto(c_1,\dots,c_n)$ sends the required sequences bijectively to weakly increasing sequences \begin{align*} 1\le c_1\le c_2\le \cdots \le c_n\le M. \end{align*} The inverse map is $a_i=c_i+D_i$, and it restores a strict rise exactly at each descent because $D_{i+1}=D_i+1$ precisely when $i\in\operatorname{Des}(\pi)$. If $M<1$, then there are no such sequences, and the binomial coefficient $\binom{M+n-1}{n}$ is $0$ because its upper entry is less than $n$. If $M\ge 1$, the standard stars-and-bars count for weakly increasing sequences of length $n$ with values in $\{1,\dots,M\}$ gives $\binom{M+n-1}{n}=\binom{m+n-1-d(\pi)}{n}$. Therefore $|\mathcal{O}_m(P,\pi)|=\binom{m+n-1-d(\pi)}{n}$. [guided] The delicate point is that prescribed strict inequalities should be removed, not converted into ordinary strict increase everywhere. For each $1\le i\le n$, let $D_i:=|\{j\in\operatorname{Des}(\pi):j<i\}|$ count how many forced strict rises occur before position $i$, and define $c_i:=a_i-D_i$. If $i\in\operatorname{Des}(\pi)$, then the condition on the sequence gives $a_{i+1}\ge a_i+1$, while $D_{i+1}=D_i+1$. Subtracting these two equal increments gives $c_{i+1}\ge c_i$. If $i\notin\operatorname{Des}(\pi)$, then $a_{i+1}\ge a_i$ and $D_{i+1}=D_i$, so again $c_{i+1}\ge c_i$. Hence every admissible sequence $(a_1,\dots,a_n)$ gives a weakly increasing sequence \begin{align*} 1\le c_1\le c_2\le \cdots \le c_n\le m-d(\pi). \end{align*} The upper bound follows because $D_n=d(\pi)$. Conversely, start with any weakly increasing sequence $(c_1,\dots,c_n)$ satisfying $1\le c_1\le \cdots\le c_n\le m-d(\pi)$ and set $a_i:=c_i+D_i$. Then $1\le a_1$ and $a_n\le m$. If $i\notin\operatorname{Des}(\pi)$, then $D_{i+1}=D_i$, so $a_{i+1}\ge a_i$. If $i\in\operatorname{Des}(\pi)$, then $D_{i+1}=D_i+1$, so $a_{i+1}\ge a_i+1$ and therefore $a_i<a_{i+1}$. Thus the two constructions are inverse bijections. If $M:=m-d(\pi)<1$, then there are no such sequences, and $\binom{M+n-1}{n}=0$ because its upper entry is less than $n$. If $M\ge 1$, stars and bars identifies such sequences with multisets of size $n$ drawn from an $M$-element set, so their number is $\binom{M+n-1}{n}=\binom{m+n-1-d(\pi)}{n}$. Therefore the fiber has cardinality $|\mathcal{O}_m(P,\pi)|=\binom{m+n-1-d(\pi)}{n}$. [/guided] [/step] [step:Sum the polynomial counts and identify the degree] Using the disjoint partition, \begin{align*} \Omega_P(m)=|\mathcal{O}_m(P)|=\sum_{\pi\in\mathcal{L}(P)}|\mathcal{O}_m(P,\pi)|. \end{align*} Thus, for every positive integer $m$, \begin{align*} \Omega_P(m)=\sum_{\pi\in\mathcal{L}(P)} \binom{m+n-1-d(\pi)}{n}. \end{align*} For each fixed integer $c$, the function \begin{align*} t\mapsto \binom{t+c}{n} \end{align*} is the polynomial \begin{align*} \frac{(t+c)(t+c-1)\cdots(t+c-n+1)}{n!} \end{align*} in $\mathbb{Q}[t]$, of degree $n$ and leading coefficient $1/n!$. Hence \begin{align*} Q_P(t):=\sum_{\pi\in\mathcal{L}(P)} \binom{t+n-1-d(\pi)}{n} \end{align*} is a polynomial in $\mathbb{Q}[t]$ satisfying $Q_P(m)=\Omega_P(m)$ for every positive integer $m$. Since $P$ is nonempty, $\mathcal{L}(P)$ is nonempty by [citetheorem:8086]. The leading coefficient of $Q_P$ is therefore \begin{align*} \frac{|\mathcal{L}(P)|}{n!}>0. \end{align*} Thus $Q_P$ has degree exactly $n=|P|$. Together with the empty-poset case, this proves the theorem. [/step]