Number of permutations to obtain identityby lizarton Tags: combinatorics, identity, permutation, transposition 

#1
Nov1711, 11:00 PM

P: 14

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!(nk)!}[/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^{nk}[/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! 



#2
Nov1811, 10:36 AM

Sci Advisor
P: 906

note that n choose 2 is (n1)n/2.
imagine that f takes 1→k. then (k1 k)f takes 1→k1. similarly (k2 k1)(k1 k)f takes 1→k2 after applying at most k1 such adjacent transpostions, we arrive a product: (1 2)(2 3).....(k1 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 wellknown formula for this sum. 


Register to reply 
Related Discussions  
Number of permutations  General Math  0  
Number of Possible Arrangements (Permutations?)  Calculus & Beyond Homework  5  
GM tube question to obtain number of disintegrations per second  Introductory Physics Homework  0  
Number of all permutations  Calculus & Beyond Homework  7 