Register to reply

Number of permutations to obtain identity

Share this thread:
lizarton
#1
Nov17-11, 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!(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!
Phys.Org News Partner Science news on Phys.org
Wildfires and other burns play bigger role in climate change, professor finds
SR Labs research to expose BadUSB next week in Vegas
New study advances 'DNA revolution,' tells butterflies' evolutionary history
Deveno
#2
Nov18-11, 10:36 AM
Sci Advisor
P: 906
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.


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