Find a simple formula for f(n)

Question

Let $f_n$ be the number of ways to choose a permutation π of [n] and then a subset of the cycles of π. For instance, f(2) = 6 (check!). Find a simple formula for f(n)(not involving any sums!).

Would this be ${n \choose π} * {π \choose k}$?

Answer 1

For a permutation with $k$ cycles, the number of subsets is $2^k$.

The number of ways to choose a permutation and then a subset of its cycles is thus:

$$\sum_{k=0}^n |s(n,k)|2^k=(n+1)!$$

Where $s(n,k)$ are Stirling numbers of the first kind: $|s(n,k)|$ is the number of permutations of $\{1,\dots,n\}$ with $k$ cycles.

---

The preceding formula is a special case of:

$$x(x+1)\cdots(x+n-1)=\sum_{k=0}^n |s(n,k)|x^k$$

It's often used as a definition of (unsigned) Stirling numbers of the first kind. It can then be used to prove the recurrence relation on Stirling numbers, which in turn, is used to prove the relation with permutation cycles. See here (I'll add a summary later to the answer).