Write $\mathbf{n}:=\{0<1<\ldots<n\}$. Let $1_{\mathbf{n}}\ne f:\mathbf{n}\rightarrow\mathbf{m}$ be an order-preserving injection. Set $\mathbf{m}-f(\mathbf{n}):=\{i_k<\ldots<i_1\}$. Then $$f=\delta^{i_1}\circ\ldots\delta^{i_k},$$ where $\delta^j(0\rightarrow1\rightarrow\ldots\rightarrow n):=(0\rightarrow 1\rightarrow\ldots\rightarrow j-1\rightarrow j+1\rightarrow\ldots\rightarrow n)$.
I have tried to prove this by induction on $k$. I have succeeded for $k=1$. Suppose it holds for $k$ and let us show it for $k+1$. Define $g:\mathbf{n}\rightarrow\mathbf{m-1}$ as follows: $g(j):=f(j)$ if $f(j)<i_1$ and $g(j):=f(j)-1$ if $i_1<f(j)$. Then $f=\delta^{i_1}\circ g$. Writing $\mathbf{m-1}-g(\mathbf{n}):=\{\ell_s<\ldots<\ell_1\}$, it follows from the induction hypothesis that $$g=\delta^{\ell_1}\circ\ldots\circ\delta^{\ell_s}.$$ All that is left is to show that $\{i_{k+1}<i_k<\ldots<i_2\}=\{\ell_s<\ldots<\ell_1\}$. I have already shown that $i_r\in\{\ell_s<\ldots<\ell_1\}$ for all $2\leq r\leq k+1$. How can I prove the other direction?
In particular, let $1\leq r\leq s$. We want to show that $\ell_r\in\mathbf{m}-f(\mathbf{n})$. For the sake of contradiction, suppose there exists $0\leq j\leq n$ such that $\ell_r=f(j)$. Clearly $i_1<f(j)$, otherwise $\ell_r=f(j)=g(j)$. I am not sure where to go from here. Any suggestions?