(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Let [itex]s*(f)[/itex] be the minimum number of transpositions of adjacent elements needed to transform the permutation [itex]f[/itex] to the identity permutation. Prove that the maximum value of [itex]s*(f)[/itex] over permutations of [itex][n][/itex] is [itex]{n \choose 2}[/itex]. Explain how to determine [itex]s*(f)[/itex] by examining [itex]f[/itex].

2. Relevant equations

[itex]{n \choose 2} = \frac{n!}{k!(n-k)!}[/itex]

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 [itex]f^{n}[/itex] obtained by composing n successive applications of f.

Consequence: Since composition of functions is associative, we also have [itex]f^{k} o f^{n-k}[/itex] 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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Number of permutations to obtain identity

**Physics Forums | Science Articles, Homework Help, Discussion**