Proving combinatorial identity with the product of Stirling numbers of the first and second kinds

Question

$$ \sum_{k} \left[\begin{array}{c} n\\k \end{array}\right] \left\{\begin{array}{c} k\\m \end{array}\right\} = {n \choose m} \frac{\left( n-1\right)!}{\left(m-1 \right)!}, \quad \text{for } n,m > 0 $$

$ \left[\begin{array}{c} n\\k \end{array}\right] $ is Stirling number of the first kind

$ \left\{\begin{array}{c} k\\m \end{array}\right\} $ Stirling number of the second kind

I don't know how to aproach this. I tried think of combinatorial interpretation and mathematical induction, but I got stuck a the beginning.

Answer 1

Recall the species of permutations marked by cycle count which is $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{\ge 1}(\mathcal{Z}))$$

so that it has the generating function $$\exp\left(u \log\frac{1}{1-z}\right)$$

and in particular $$\sum_{n\ge q} \left[n\atop q\right] \frac{w^n}{n!} = \frac{1}{q!} \left(\log\frac{1}{1-w}\right)^q.$$

Continuing, recall the species of set partitions marked by the number of sets which is $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$

so that it has the generating function $$\exp\left(u (\exp(z)-1)\right)$$ and in particular $$\sum_{n\ge q} {n\brace q} \frac{w^n}{n!} = \frac{1}{q!} \left(\exp(w)-1\right)^q.$$

Introduce the EGF $$Q(z) = \sum_{n\ge 1} \frac{z^n}{n!} \sum_{k=1}^n \left[n\atop k\right] {k\brace m}.$$

Interchange the order of summation to get $$\sum_{k\ge 1} {k\brace m} \sum_{n\ge k} \left[n\atop k\right] \frac{z^n}{n!}.$$

Now we recognize the inner generating function from the introduction (partitions into $k$ cycles) so $Q(z)$ simplifies to

$$\sum_{k\ge 1} {k\brace m} \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

This too is a familiar generating function (partitions into $m$ sets) applied to the logarithmic term so we get $$Q(z) = \frac{1}{m!} \left(\exp\log\frac{1}{1-z} - 1 \right)^m = \frac{1}{m!} \left(\frac{z}{1-z}\right)^m.$$

Finally perform coefficient extraction to obtain $$n! [z^n] Q(z) = \frac{n!}{m!} [z^{n-m}] \left(\frac{1}{1-z}\right)^m = \frac{n!}{m!} {n-m+m-1\choose m-1} \\= \frac{n!}{m!} {n-1\choose m-1} = \frac{(n-1)!}{(m-1)!} {n\choose m}.$$

Answer 2

Here is a combinatorial proof. Count tuples $(\sigma_1,\ldots,\sigma_m)$ of permutations such that the domain of each $\sigma_i$ is a subset $A_i$ of $[n](=\{1,\ldots,n\})$ with $(A_1,\ldots,A_m)$ an ordered partition of $[n]$ in two different ways.

Each such tuple induces a unique permutation $\sigma$ on $[n]$, namely the permutation $\sigma$ for which the restriction of $\sigma$ to $A_i$ is precisely $\sigma_i(1\leq i\leq m).$ The number of tuples that induce a permutation with $k$ cycles is equal to the number of ordered partitions of a $k$-element set into $m$ subsets, i.e., ${k \brace m}m!$. Therefore, the total number of tuples must be $$ \sum_k {n \brack k}{k \brace m}m!. $$

We may also count such tuples $(\sigma_1,\ldots,\sigma_m)$ by viewing them as words. Arrange the elements of $[n]$ into a word in $n!$ ways and select $m-1$ of the $n-1$ gaps between letters to split the word into $m$ permutations. The number of ways to do this is $$ n!{n-1 \choose m-1}. $$ Therefore, we must have $$ \sum_k {n \brack k}{k \brace m}m!=n!{n-1 \choose m-1}, $$ which is equivalent to your identity.