How do I show the following identify where c(n , k) represent unsigned stirling numbers of the first kind?

Question

I need to show the following identity but I don't know where to start. $ c(n+1, m+1) = \sum_{k=0}^{n} c(n, k) \binom{k}{m} $

Answer 1

Hint: the Stirling numbers $c(n,k)$ are the coefficients of the rising factorial:

$$(x)^{(n)} = x(x+1)\dots (x+n-1) = \sum_{k=0}^n c(n,k)x^k.$$

Use this identity, and the fact that

$$x \times (x+1)^{(n)} = (x)^{(n+1)},$$

then compare coefficients after applying the binomial theorem to expand each term in the sum $$(x+1)^{(n)} = \sum_{k=0}^n c(n,k)(x+1)^k.$$

Answer 2

Another kind of hint:

Combinatorially, the Stirling numbers of the first kind(c(n,k)) count the number of permutations in $\mathcal{S}_n$ with k cycles. So, in the left side of the equation you have the number of permutations in $\mathcal{S}_{n+1}$ with m+1 cycles. In the right side is the fun side because with $c(n,k)$ you are counting the number of permutations in $\mathcal{S}_{n}$ with k cycles and, by multiplying by $\binom{k}{m}$ you are choosing k-m cycles that you would collapse in one big cycle(to get m+1 cycles) and then you want to put the (n+1)-th element in that collapsed cycle(n+1 elements).