# Number of permutations to obtain identity

 P: 14 1. The problem statement, all variables and given/known data Let $s*(f)$ be the minimum number of transpositions of adjacent elements needed to transform the permutation $f$ to the identity permutation. Prove that the maximum value of $s*(f)$ over permutations of $[n]$ is ${n \choose 2}$. Explain how to determine $s*(f)$ by examining $f$. 2. Relevant equations ${n \choose 2} = \frac{n!}{k!(n-k)!}$ Perhaps... Definition: The identity permutation of [n] is the identity function from [n] to [n]; its word form is 1 2 ... n. A transposition of two elements in a permutation switches their positions in the word form. A permutation f of [n] is even when P(f) is positive, and it is odd when P(f) is negative. When n = 1, there is one even permutation of [n] and no odd permutation. For n >= 2, there are n!/2 even permuatations and n!/2 odd permutations. My book solves a problem that counts the number of exchanges of entries needed to sort the numbers into the order 1,2,...,n (given a list of n numbers 1 through n). The solution defines the nth iterate of f: A --> A. Definition: The nth iterate of f: A --> A is the function $f^{n}$ obtained by composing n successive applications of f. Consequence: Since composition of functions is associative, we also have $f^{k} o f^{n-k}$ whenever 0 <= k <= n. 3. The attempt at a solution The number of subsets of length 2 of a permutation of length n is n choose 2. I can see that from the definition, but how does one formulate a formal proof from just the definition? I can guess that the scenario requiring the most trials is when f is the permutation n...2 1. Any help would be greatly appreciated!