Bijective proof for Stirling numbers of the first kind

26 Views Asked by At

Setting. Let s(n,k) be the Stirling number of the first kind counting the number of permutations on a $n$-set with exactly $k$ cycles. For all non-negative integers $m,n$ there is the identity $$\sum_{k=0}^n s(n,k) m^k = m^{\overline{n}}$$ where $m^{\overline{n}} = m (m+1) \cdots (m+n-1)$ denotes the rising factorial. It is not hard to show the identity by induction using the recurrence formula $s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)$.

Question. Is there a nice combinatorial proof for this identity?

Motivation. For the Stirling numbers of the second kind, there is the somewhat similar identity $$\sum_{k=0}^n S(n,k) m^{\underline{k}} = m^n$$ involving the falling factorial. The common combinatorial proof is to identify both sides as the number of maps $f : N \to M$ (with $\#N = n$ and $\#M = m$), on the left hand side sorted wrt to the size $k = \#f(N)$ of the image.