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
Wolstenholme
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)!} $
62861
27.08.2016 02:34
A funny solution, which also allows you to derive the generating function in post #2:
Consider the number of ways to color each of $n$ (indistinguishable) symbols with one of $n$ colors. By stars and bars, this is $\binom{2n - 1}{n - 1} = \frac{(2n - 1)!}{n! (n - 1)!}$.
However, we can also count the number of indistinguishable colorings with Burnside's lemma. Consider a permutation $\sigma \in S_n$; it fixes $n^{c(\sigma)}$ colorings (the colorings where each cycle is monochromatic), where $c(\sigma)$ is the number of cycles of $\sigma$. Thus, by Burnside's, the number of indistinguishable colorings is
\[\frac{1}{n!} \sum_{\sigma \in S_n} n^{c(\sigma)} = \frac{(2n - 1)!}{n! (n - 1)!},\]i.e.
\[a_n n^n + a_{n - 1} n^{n - 1} + \cdots + a_1 n = \frac{(2n - 1)!}{(n - 1)!}.\]
AlirezaOpmc
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?
Pathological
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$