Combinatorial proof for Stirling number of 1st kind's generating function

Question

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?

Answer 1

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:

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

2. 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.

3. 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 $k=9$ and $n=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.