1
$\begingroup$

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}$?

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Where does the π factor into this? In place of k, do i just put π? Also, since the questions asks for formula not involving sum, the answer will just be (n+1)!. $\endgroup$ – hilh Nov 18 '19 at 7:36
  • $\begingroup$ @hilh Yes, the answer is $(n+1)!$, the sum is just the way to find this formula. Note that the sum runs on the number of cycles, and $|s(n,k)|$ is the number of permutations of $\{1...n\}$ with $k$ cycles. There is no $\pi$ involved. Anyway, you can't have $\pi$ in the closed-form formula: it's not a known constant of the problem, it would be, at best, an arbitrary permutation (possibly a sum index, but here it's not how it's computed). $\endgroup$ – Jean-Claude Arbaut Nov 18 '19 at 8:01
  • $\begingroup$ Could you explain how you get (n+1)! again? $\endgroup$ – hilh Nov 28 '19 at 6:43

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.