Let $n, m, k $ be three natural numbers, ${n \brack k}$ and ${n \brace k}$ the Stirling numbers of first and second kind respectively.
We have:
$$ \tag{*} {n-1 \choose m}{n-m \brack k}= \sum_i (-1)^{i-m}{k-1+i
\choose k-1}{i \brace m}{n \brack i+k} $$
where the bounds for $i$ in the sum on the rhs don't need to be specified as there is only a finite number of values of $i$ whose corresponding summand is non-zero and the sum is understood over all such $i$.
This identity can be verified numerically and can be derived from another three parameters identity involving the second kind of Stirling numbers only- namely Eq. (6.28) in Concrete Mathematics Second Edition, R. L. Graham, D. E. Knuth, O. Patashnik)
$$ \tag{**} {\ell+m \choose \ell}{n \brace \ell+m}= \sum_k {k\brace \ell}{n-k \brace m}{n \choose k} $$
which is obtained rather easily via the exponential generating functions of ${n \brace l+m}$, ${n \brace m}$ and ${n \brace l}$ .
Indeed, if we replace $m$ by $-m$ and $n$ by $-n$ in (**), taking into account that ${-a \brace -b}$ = ${b \brack a}$ and ${-n \choose k}=(-1)^k{n+k-1\choose k}$, we obtain
\begin{align*} {\ell-m \choose \ell}{-n \brace \ell-m}&= \sum_k {k\brace \ell}{-n-k \brace -m}{-n \choose k} \\
(-1)^\ell{m-1 \choose \ell}{m- \ell \brack n}&= \sum_k {k\brace \ell}{m \brack n+k}(-1)^k{n+k-1 \choose k}\end{align*}
which is (*) after the appropriate change of notation.
But in Concrete Mathematics, the identity (**) is given under the condition $\ell,m,n \ge 0$, so I am note sure whether it is licit to do such negation of the indices.
Then my question is: how can we derive (*) directly, without resorting to (**). Maybe with generating functions, coefficient extractors or things like that?
Best Answer
We seek to verify that
$$\sum_{q=m}^{n-k} (-1)^{q-m} {k-1+q\choose k-1} {q\brace m} {n\brack q+k} = {n-1\choose m} {n-m\brack k}.$$
Using the standard EGFs the LHS becomes
$$\sum_{q=m}^{n-k} (-1)^{q-m} {k-1+q\choose k-1} q! [z^q] \frac{(\exp(z)-1)^m}{m!} n! [w^n] \frac{1}{(q+k)!} \left(\log\frac{1}{1-w}\right)^{q+k} \\ = \frac{n!}{(k-1)! \times m!} [w^n] \sum_{q=m}^{n-k} (-1)^{q-m} [z^q] (\exp(z)-1)^m \frac{1}{q+k} \left(\log\frac{1}{1-w}\right)^{q+k} \\ = \frac{(n-1)!}{(k-1)! \times m!} [w^{n-1}] \sum_{q=m}^{n-k} (-1)^{q-m} [z^q] (\exp(z)-1)^m \left(\log\frac{1}{1-w}\right)^{q+k-1} \frac{1}{1-w} \\ = \frac{(n-1)!}{(k-1)! \times m!} [w^{n-1}] \frac{1}{1-w} \\ \times \sum_{q=m}^{n-k} (-1)^{q-m} [z^{q+k-1}] z^{k-1} (\exp(z)-1)^m \left(\log\frac{1}{1-w}\right)^{q+k-1} \\ = \frac{(n-1)!}{(k-1)! \times m!} [w^{n-1}] \frac{1}{1-w} \\ \times \sum_{q=m+k-1}^{n-1} (-1)^{q-(k-1)-m} [z^{q}] z^{k-1} (\exp(z)-1)^m \left(\log\frac{1}{1-w}\right)^{q}.$$
Now as $\log\frac{1}{1-w} = w + \cdots$ when $q\gt n-1$ there is no contribution from the logarithmic power term due to the coefficient extractor $[w^{n-1}]$ so we find
$$(-1)^{m+(k-1)} \frac{(n-1)!}{(k-1)! \times m!} [w^{n-1}] \frac{1}{1-w} \\ \times \sum_{q\ge m+k-1} (-1)^{q} \left(\log\frac{1}{1-w}\right)^{q} [z^{q}] z^{k-1} (\exp(z)-1)^m.$$
Note that $z^{k-1} (\exp(z)-1)^m = z^{m+k-1} + \cdots$ which means that the remaining sum / coefficient etractor pair covers the entire series and we get
$$(-1)^{m+(k-1)} \frac{(n-1)!}{(k-1)! \times m!} [w^{n-1}] \frac{1}{1-w} \\ \times (-1)^{k-1} \left(\log\frac{1}{1-w}\right)^{k-1} \left(\exp\left(-\log\frac{1}{1-w}\right)-1\right)^m \\ = (-1)^{m+(k-1)} \frac{(n-1)!}{(k-1)! \times m!} [w^{n-1}] \frac{1}{1-w} \\ \times (-1)^{k-1} \left(\log\frac{1}{1-w}\right)^{k-1} (-w)^m \\ = \frac{(n-1)!}{(k-1)! \times m!} [w^{n-1-m}] \frac{1}{1-w} \left(\log\frac{1}{1-w}\right)^{k-1} \\ = \frac{(n-1)!}{m!} [w^{n-1-m}] \frac{1}{1-w} \frac{1}{(k-1)!} \left(\log\frac{1}{1-w}\right)^{k-1} \\ = \frac{(n-1)!}{m!} (n-m) [w^{n-m}] \frac{1}{k!} \left(\log\frac{1}{1-w}\right)^{k} \\ = \frac{(n-1)!}{m! \times (n-1-m)!} (n-m)! [w^{n-m}] \frac{1}{k!} \left(\log\frac{1}{1-w}\right)^{k} \\ = {n-1\choose m} {n-m\brack k}.$$
This is the claim.