Number of permutations to obtain identity

In summary, the problem asks to prove that the maximum value of the minimum number of adjacent transpositions needed to transform a permutation of [n] to the identity permutation is {n choose 2}. This can be determined by examining the permutation and finding the maximum value of k, where k is the number of adjacent transpositions used to transform the permutation to a product that takes 1 to 1. By using a well-known formula, the sum of the number of adjacent transpositions can be determined.
  • #1
lizarton
14
0

Homework Statement



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].

Homework 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.

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:
Physics news on Phys.org
  • #2
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.
 

What is the meaning of "Number of permutations to obtain identity"?

The number of permutations to obtain identity refers to the number of ways in which a set of elements can be rearranged or ordered such that it returns to its original form or identity.

Why is the number of permutations to obtain identity important?

This number is important in various mathematical and scientific fields, including statistics, combinatorics, and group theory. It can help solve problems related to counting and analyzing different arrangements of objects or elements.

How is the number of permutations to obtain identity calculated?

The number of permutations to obtain identity is calculated using the factorial function. For a set of n elements, the number of permutations is n! (n factorial). For example, if there are 4 elements, the number of permutations would be 4! = 4 x 3 x 2 x 1 = 24.

What is the difference between permutations and combinations?

Permutations refer to the different ways in which a set of elements can be arranged or ordered. Combinations, on the other hand, refer to the different ways in which a subset of elements can be selected from a larger set without regard to order.

Can the number of permutations to obtain identity be applied in real-life situations?

Yes, the concept of permutations is applicable in various real-life situations, such as in probability calculations, arranging objects or elements in a specific order, and in solving puzzles or games involving rearranging objects.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
579
  • Calculus and Beyond Homework Help
Replies
1
Views
486
  • Calculus and Beyond Homework Help
Replies
3
Views
534
  • Calculus and Beyond Homework Help
Replies
5
Views
596
  • Calculus and Beyond Homework Help
Replies
3
Views
393
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Linear and Abstract Algebra
Replies
7
Views
511
  • Calculus and Beyond Homework Help
Replies
2
Views
216
Back
Top