1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
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

  1. Nov 17, 2011 #1
    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]

    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!
    Last edited: Nov 17, 2011
  2. jcsd
  3. Nov 18, 2011 #2


    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook