## Romanian TST 2011 Problem 4

Suppose and denote the permutations of the set . For denote by the number of cycles in the disjoint cycle decomposition of the permutation . Calculate the sum .

**Official Solution:** Denote by , and try to find a recurrence relation for .

To do this, consider and obtained by deleting from . If has as a fixed point, then and . If then we can obtain exactly one permutation which fixes in by inserting , and exactly permutations which do not fix . Therefore .

For we get which is the requested answer.

Advertisements

Categories: Algebra, Combinatorics, IMO, Olympiad
Combinatorics, IMO, TST

Comments (0)
Trackbacks (0)
Leave a comment
Trackback