Ramsey-ed!!

Level pending

Let S={1,2,3.....6} i is said to be a fixed point of a permutation p or S if p(i)=i,where i belongs to S.Let p n ( k ) p_{n} (k) be the number of permutations of S which have k fixed points. Find ∑ k = 0 n k p n ( k ) / n \sum_{k=0}^n k p_{n}(k)/n ?


The answer is 120.

Priyatam Roy by Priyatam Roy , 24, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Patrick Corn
Feb 22, 2016

For a permutation σ ∈ S n \sigma \in S_n , let f ( σ ) f(\sigma) be the number of fixed points of σ \sigma . The sum is ∑ σ ∈ S n f ( σ ) n = 1 n ∑ σ ∈ S n f ( σ ) \sum_{\sigma \in S_n} \frac{f(\sigma)}{n} = \frac1{n} \sum_{\sigma\in S_n} f(\sigma) Any particular element of { 1 , 2 , … , n } \{ 1, 2, \ldots, n \} is fixed by ( n − 1 ) ! (n-1)! permutations, so the total number of fixed points of all the permutations is ( n − 1 ) ! n = n ! (n-1)!n = n! . (So the average number of fixed points of a permutation in S n S_n is exactly equal to 1.)

So the sum becomes 1 n ⋅ n ! = ( n − 1 ) ! \frac1{n} \cdot n! = (n-1)! . For n = 5 n = 5 this is 120 \fbox{120} .

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...