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
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
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