Combinatorial proof of a nice expression for Stirling numbers of second kind While answering a question I came across the following nice identity:
$$
\sum_{1\le k_1\le k_2\le\dots\le k_n\le m}\prod_{1\le i \le n}k_i={n+m \brace m},
$$
where ${n+m \brace m}$ refers to the Stirling number of second kind. The equation can be readily proved by using generating functions but I strongly suspect that there should be a simple combinatorial explanation of the expression.
Any hint is appreciated.
 A: Hint:  Consider the following algorithm:
You have a list of the $n+m$ numbers and you start with $\{1\}$ as the partition, you start also with a pointer starting at $2$ that is going to increase $n$ times and in each number you have the following decision to make: If the number of blocks is exactly $m,$ you have $m$ options per number. If not, you can decide if you want to append the number to a block or create a new block where the number is going to be the smallest element of the block. When this happens the number of blocks will increase.  
As an example and for simplicity, assume $m=2$ and take $n=3.$ We start with $1$ and we place it in a block so $\{1\}$ is what we have. Then $2,$ if we decide to place $2$ in the other block, then we will end up having $2^3$ options for the rest of numbers. If we decide to place $3$ as the smallest element of the new block, we will have $2^2$ options and so on. So we will have
$$\sum _{i=0}^{3}2^i=2^4-1=LHS,$$
but of course every partition can be created in this way. There you can check that this is the correspondence
$$\underbrace{1^3}_{\{1,2,3,4\},\{5\}}+\underbrace{1^2\cdot 2}_{\{1,2,3,\cdots \},\{4,\cdots \}}+\underbrace{1^1\cdot 2^2}_{\{1,2,\cdots \},\{3,\cdots \}}+\underbrace{ 2^3}_{\{1,\cdots \},\{2,\cdots \}}$$
So, to generalize, consider where do the numbers change, so I would suggest you write the LHS as
$$\sum_{d_1+d_2+\cdots +d_m=n}1^{d_1}2^{d_2}\cdots m^{d_m}.$$
Here the $d_i$ represent the frequency of $i$ in the sequence $k$ i.e., $$d_i = |\{j:k_j=i\}|.$$
A way to understand this algorithm is to think about it backwards. Suppose I give you a partition $\pi \vdash [n+m]$ with $m$ blocks. Suppose the blocks are labelled $\pi =\{B_1,\cdots , B_m\}$ where
the blocks are ordered by their minimal elements $b_i\in B_i: 1=b_1<b_2<\cdots<b_m\le n+m$. Consider further the consecutive differences of these numbers $d_i=b_{i+1}-b_{i}-1\ (0<i<m)$, $d_m=n+m-b_m.$ Notice that $d_i\ge0$ and $d_1+d_2+\cdots +d_m=n+m-(m-1)-b_1=n$. Notice further that $d_i$ is essentially the number of elements which can be placed arbitrarily in any of the first $i$ blocks, so that there are $i^{d_i}$ ways to perform this.
