Combinatorial interpretation of a sum with Stirling numbers

Question

$$\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.

Answer 1

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)!$$

Answer 2

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.