Home > Algebra, Combinatorics, IMO, Olympiad > Romanian TST 2011 Problem 4

Romanian TST 2011 Problem 4


Suppose n \geq 2 and denote S_n the permutations of the set \{1,2,..,n\}. For \sigma \in S_n denote by \ell(\sigma) the number of cycles in the disjoint cycle decomposition of the permutation \sigma. Calculate the sum \displaystyle \sum_{\sigma \in S_n} \text{sgn}(\sigma) n^{\ell(\sigma)}.

Official Solution: Denote by f_n(x)=\displaystyle \sum_{\sigma \in S_n} \text{sgn}(\sigma) x^{\ell(\sigma)},\ \forall n \geq 2, and try to find a recurrence relation for f_n.

To do this, consider \sigma \in S_n and \sigma_1 \in S_{n-1} obtained by deleting n from \sigma. If \sigma has n as a fixed point, then \text{sgn}\sigma=\text{sgn}\sigma_1 and \ell(\sigma_1)=\ell(\sigma)-1. If \sigma_1 \in S_{n-1} then we can obtain exactly one permutation which fixes n in S_n by inserting n, and exactly n-1 permutations which do not fix n. Therefore f_n(x)=xf_{n-1}(x)-(n-1)f_{n-1}(x)=(x-n+1)f_{n-1}(x)=...=(x-(n-1))(x-(n-2))...(x-1)x.

For x=n we get f_n(n)= n! which is the requested answer.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: