# 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

• You can get displayed equations by using double dollar signs instead of single dollar signs. – joriki Apr 11 '16 at 9:25

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.