Number of permutations to obtain identity

[lizarton]

Homework Statement

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.

Homework 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.

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!

 

[Deveno]

note that n choose 2 is (n-1)n/2.

imagine that f takes 1→k.

then (k-1 k)f takes 1→k-1.

similarly (k-2 k-1)(k-1 k)f takes 1→k-2

after applying at most k-1 such adjacent transpostions, we arrive a product:

(1 2)(2 3)...(k-1 k)f which takes 1→1.

ask yourself: what the maximum value of k?

now we have a permutation g that takes 1→1.

suppose g takes 2→m, and repeat.

won't you eventually wind up with the identity?

now sum the number of adjacent transpositions used, and use

a well-known formula for this sum.