Combinatorial interpretation of a sum with Stirling numbers $$\sum_{i,j}{n\brack i+j}\binom{i+j}i$$
Does this have a combinatorial interpretation? I don't see how to use Stirling numbers of the first kind in interpretations. I know that the answer is $(n+1)!$ , but the original question didn't provide it.
 A: I'm not sure about a direct combinatorial proof, but the solution can be easily obtained by taking $k=i+j$ and using the known formula $\sum_{k} \genfrac[]{0pt}{}{n}{k} x^k = x^{\overline{n}}$, where $x^{\overline{n}}$ denotes the rising factorial.
$$\sum_{i,j} \genfrac[]{0pt}{}{n}{i+j} \binom{i+j}{i} = \sum_{k} \genfrac[]{0pt}{}{n}{k} \sum_{i} \binom{k}{i} = \sum_{k} \genfrac[]{0pt}{}{n}{k} 2^k = 2^{\overline{n}} = (n+1)!$$
A: Here's a combinatorial proof.  Both sides count the number of ways to partition $n$ numbers into two ordered lists, a first list and a second list.
For the left side, $\genfrac[]{0pt}{}{n}{i+j}$ partitions the $n$ numbers into $i+j$ disjoint cycles.  Then $\binom{i+j}{i}$ chooses $i$ of these cycles.  Since a permutation can be uniquely expressed as a set of disjoint cycles, this creates the first ordered list from the numbers in the $i$ cycles chosen.  Similarly, the leftover $j$ cycles form the second ordered list from the rest of the $n$ numbers.  Summing over all possible values of $i$ and $j$ gives the number of ways to partition the $n$ numbers into a first ordered list and a second ordered list.
For the right side, add a new symbol the the $n$ numbers, like *.  Then create a permutation on these $n+1$ symbols.  This can be done in $(n+1)!$ ways.  The * symbol separates the first ordered list from the second ordered list.
