Stirling numbers of the first kind - identity from wikipedia. How can we prove that:
$\sum_{p=k}^n \left[\begin{array}{ccc} n \\ p \end{array}\right] {p \choose k} = \left[\begin{array}{ccc} n+1 \\ k+1 \end{array}\right]$?
where $\left[\begin{array}{ccc}n \\ p \end{array}\right]$ denotes stirling number of the first kind.
 A: Here is a proof in two parts, the first algebraic and the second combinatorial.
First step. Recall that the bivariate generating function of the Stirling Numbers of the first kind represents the species $$\mathfrak{P}(\mathfrak{C}(\mathcal{Z}))$$ and is given by
$$\exp\left(u\log\frac{1}{1-z}\right).$$
It follows that the sum that we want to evaluate is given by
$$n! [z^n] \sum_{p=k}^n {p\choose k} [u^p] \exp\left(u\log\frac{1}{1-z}\right)
= n! [z^n] \sum_{p=k}^n {p\choose k} \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^p.$$
As we are extracting the coefficient of $z^n$ and the logarithmic term starts at $z$ we may extend the sum to infinity, getting
$$n! [z^n] \sum_{p=k}^\infty {p\choose k} \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^p.$$
This turns into
$$n![z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k
\sum_{p=k}^\infty {p\choose k} \frac{k!}{p!} \left(\log\frac{1}{1-z}\right)^{p-k}$$
which becomes
$$n![z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k
\sum_{p=k}^\infty \frac{1}{(p-k)!}  \left(\log\frac{1}{1-z}\right)^{p-k}$$
or
$$n![z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k
\exp\log\frac{1}{1-z}$$
which is finally equal to
$$n![z^n] \frac{1}{1-z}\times\frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$
Second step. The key observation is that we can recognize the univariate exponential generating function from the previous step. It represents the species
$$\mathfrak{E}(\mathcal{Z})\times\mathfrak{P}_k(\mathfrak{C}(\mathcal{Z}))$$
which consists of a set of $k$ cycles paired with a permutation. But there is a bijection between this species (on $n$ nodes) and the species
$$\mathfrak{P}_{k+1}(\mathfrak{C}(\mathcal{Z}))$$
(on $n+1$ nodes), which is obtained straightforwardly by removing the element $n+1$ from the cycle it is on, which leaves $k$ cycles and a permutation. Now the count of the second species is $$\left[ n+1 \atop k+1 \right]$$ and we are done.
