Let $n>1$ be an integer and $S_n$ the set of all permutations $\pi : \{1,2,\cdots,n \} \to \{1,2,\cdots,n \}$ where $\pi$ is bijective function. For every permutation $\pi \in S_n$ we define: \[ F(\pi)= \sum_{k=1}^n |k-\pi(k)| \ \ \text{and} \ \ M_{n}=\frac{1}{n!}\sum_{\pi \in S_n} F(\pi) \] where $M_n$ is taken with all permutations $\pi \in S_n$. Calculate the sum $M_n$.
Problem
Source:
Tags: combinatorics proposed, combinatorics
13.03.2011 20:05
Obel1x wrote: Let $n>1$ be an integer and $S_n$ the set of all permutations $\pi : \{1,2,\cdots,n \} \to \{1,2,\cdots,n \}$ where $\pi$ is bijective function. For every permutation $\pi \in S_n$ we define: \[ F(\pi)= \sum_{k=1}^n |k-\pi(k)| \ \ \text{and} \ \ M_{n}=\frac{1}{n!}\sum_{\pi \in S_n} F(\pi) \] where $M_n$ is taken with all permutations $\pi \in S_n$. Calculate the sum $M_n$. For a given $k$, all values of $\pi(k)$ occur with the same frequency when running over $\pi\in S_n$. So $M_n$ is just the average \[\frac 1n \sum_{k=1}^n\sum_{j=1}^n |k-j|=\frac 1n \sum_{k=1}^n\left[\binom k2+\binom{n-k+1}2\right]=\frac 2n \binom{n+1}3=\frac {n^2-1}3.\]
01.01.2020 23:36
Obel1x wrote: Let $n>1$ be an integer and $S_n$ the set of all permutations $\pi : \{1,2,\cdots,n \} \to \{1,2,\cdots,n \}$ where $\pi$ is bijective function. For every permutation $\pi \in S_n$ we define: \[ F(\pi)= \sum_{k=1}^n |k-\pi(k)| \ \ \text{and} \ \ M_{n}=\frac{1}{n!}\sum_{\pi \in S_n} F(\pi) \]where $M_n$ is taken with all permutations $\pi \in S_n$. Calculate the sum $M_n$. Is this really a 9th grade problem. https://artofproblemsolving.com/community/c6h396494