Combinatorial proof for Stirling number of 1st kind's generating function So I see this identity a lot but I can't find a detailed combinatorial proof for it. 
$$n(n+1)...(n+k-1)=\sum_{j=0}^k \begin{bmatrix}k \\j \end{bmatrix}n^j$$
Can someone please help? 
 A: Both sides are counted by the number of ways to place $k$ distinct flags on $n$ distinct flagpoles, where the order in which several flags are stacked matters.
Left Hand Side
The first flag can be placed on any of $n$ poles. The second can be placed on the bottom of any pole, or on top of the first, for $n+1$ options. Continuing, the $i^{th}$ flag can be placed in any of $n+i-1$ places, either on the bottom of any pole, or just above any of the $i-1$ previously placed flags. Therefore, the number of possibilities is $\prod_{i=1}^n(n+i-1)$.
Right Hand Side
This is the trickier construction. Assume the $k$ flags are numbered $1$ to $k$. Here is a procedure for choosing a flag placement, which I claim uniquely represents every placement:

*

*Choose an integer $j$ between $0$ and $k$.


*Choose a permutation of the flags with exactly $j$ cycles. Write this permutation in cycle notation so that each cycle has its smallest element first, and so the initial elements of the cycles decrease from left to right.


*Proceeding from left to right, choose a pole for each cycle, and place the flags in that cycle on the pole, preserving their order as written.
For example, say $n=9$ and $k=3$. We choose $j=4$, and choose the permutation
$$\pi=(5\,9)(3\, 4)(2)(1\, 8\, 6\, 7).$$
We then choose to put the (5 9) on the left pole, (3 4) on the right pole, (2) on the right pole, and (1 8 6 7) on the right pole, resulting in
|   |   7
|   |   6
|   |   8
|   |   1
|   |   2
9   |   4
5   |   3

The reason the cycles can be uniquely recovered is because each one begins with a number that is smaller than all numbers below it. For example, the 2 is smaller than 4 and 3, so it must begin a cycle.
