1
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.