Combinatorial interpretation of the sum $\sum s1(n, i+j) \cdot {i + j \choose i} $ I'm trying to figure out a combinatorial interpretation of the following sum:
$\sum\limits_{i,j} s1(n, i+j) \cdot {i + j \choose i} $
and then a compact formula. The $ s1 $ function denotes the Stirling numbers of the first kind (i.e. number of $ n$-permutations with $i+j$ cycles).
For fixed $ i $, it looks like choosing a permutation with at least $ i $ cycles and choosing $ i $ out of them, but I can' see a closed formula from this

\begin{align}
\sum_{i,j}s_1(n,i+j)\binom{i+j}i
&=
\sum_ks_1(n,k)\sum_{i=0}^k\binom ki=\sum_ks_1(n,k)2^k=(-1)^n(-2)_n=(n+1)!\;,
\end{align}
where $(x)_n$ is the falling factorial $x(x-1)\cdots(x-n+1)$.
So the number of subsets of cycles taken from permutations of $n$ elements is the number of permutations of $n+1$ elements. I don't see a bijective proof of that, but I'll think about it.
