Let $n$ be a positive integer. For any $k$, denote by $a_k$ the number of permutations of $\{1,2,\dots,n\}$ with exactly $k$ disjoint cycles. (For example, if $n=3$ then $a_2=3$ since $(1)(23)$, $(2)(31)$, $(3)(12)$ are the only such permutations.) Evaluate \[ a_n n^n + a_{n-1} n^{n-1} + \dots + a_1 n. \]Proposed by Sammy Luo
Problem
Source: ELMO 2014 Shortlist C5, by Sammy Luo
Tags: function, combinatorics proposed, combinatorics
25.07.2014 05:57
These $ a_k $ are called Stirling numbers of the first kind. It is not hard to check that they satisfy the following generating function: \[ \sum_{k = 1}^{n}a_{k}x^k = x(x + 1)(x + 2) \dots (x + n - 1) \] Letting $ x = n $ in the expression we immediately find that the desired sum is $ \frac{(2n - 1)!}{(n - 1)!} $
27.08.2016 02:34
A funny solution, which also allows you to derive the generating function in post #2:
12.03.2018 12:28
Wolstenholme wrote: These $ a_k $ are called Stirling numbers of the first kind. It is not hard to check that they satisfy the following generating function: \[ \sum_{k = 1}^{n}a_{k}x^k = x(x + 1)(x + 2) \dots (x + n - 1) \] Letting $ x = n $ in the expression we immediately find that the desired sum is $ \frac{(2n - 1)!}{(n - 1)!} $ Would please explain more about that how did u get that the generating functiong of stirling numbers is like that?
24.10.2019 02:43
We claim that the answer is $\binom{2n-1}{n-1} n! .$ Our strategy will to first find a quantity which the sum in question is enumerating, and then to biject that quantity to other easy-to-evaluate quantities. First of all, notice that the quantity in question is equivalent to the number of ways to first select a permutation of $[n]$, and then assign a number in $\{1, 2, \cdots, n\}$ to each cycle of the permutation. Equivalently, we can select a permutation of $[n]$ and then assign a number in $\{1, 2, \cdots, n\}$ to each number such that each cycle is assigned the same number. Switching the order of these operations, we can first assign a number to each of the numbers, and then select a permutation so that $a \rightarrow b$ only if $a, b$ are assigned the same number. This last quantity is easy to enumerate. Indeed, select some integers so that $a_0 + a_1 + \cdots + a_{n-1} = n.$ First label some $a_i$ numbers with $i$, for each $0 \le i \le n-1.$ There are $\frac{n!}{a_0! a_1! \cdots a_{n-1}!}$ ways to do this. Now there are $a_0! a_1! \cdots a_{n-1}!$ ways to select a permutation satisfying the constraing. By the Multiplication Principle, there are $n!$ total permutations and labellings corresponding to the $n-$tuple $(a_0, a_1, \cdots, a_{n-1})$. As there are $\binom{2n-1}{n-1}$ $n-$tuples in total, by the Multiplication Principle again, the answer is $\boxed{\binom{2n-1}{n-1} n!}.$ $\square$