Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ ¹ ² ³ °
 

You are not logged in. #1 20090413 07:19:13
PermutationsA permutation is a bijection from the set to itself. The set of all permutations forms a group of order under composition of mappings, called the symmetric group of degree and denoted . Permutations may be odd or even. Here is the most intuitive definition I can come up with for odd and even permutations. It is not the definition given in John F. Humphreys’s book A Course in Group Theory, but it will do. Given , let Then we say that is even if the number of elements in is even, and odd if is odd. Last edited by JaneFairfax (20090415 03:13:43) #2 20090413 07:42:27
Re: PermutationsNote that Hence the identity is always an even permutation. Also A transposition (where ) is a permutation which maps to and vice versa, leaving all other numbers fixed. Consider the ordered pairs Under the transposition , the image of the first component of each ordered pair is , which is greater than the second component of each ordered pair (which is fixed in the transposition) Hence . Similarly, the ordered pairs are in , since the transposition maps the second component to while fixing the first component. The only other ordered pair that can belong to is . , which is odd. #3 20090413 07:58:59
Re: PermutationsThis definition of odd/even permutations is at least intuitive. Unfortunately it is also mathematically unwieldy. Try proving, using this definition, that the composition of two even permutations is an even permutation, for instance. #4 20090413 08:20:36#5 20101130 01:13:44
Re: PermutationsOkay, here is another definition of even and odd permutations. Let’s look at the expression on the righthand side. The denominator is a product of factors, and so is the numerator. Let be a factor in the denominator. Either or . In the former case is a factor in the numberator, while in the latter case is a factor in the numerator. Conversely, if is a factor in the numerator, then (as ) either is a factor in the denominator (if ) or is a factor in the denominator (if ). So we see that if is a factor in the denominator then either or is a factor in the numerator and conversely if is a factor in the numerator then either or is a factor in the denominator. It follows that is always either +1 or −1. We define to be even if is and odd if . Last edited by JaneFairfax (20101201 04:50:12) #6 20101201 04:25:23
Re: Permutationsso we need to show that . We first rewrite some of the factors in this product: Note that this is equivalent to multiplying by which means that it leaves the value of the product unchanged. Doing this for all i, j, we can ensure that all the factors in the denominator are of the form for , with the corresponding factors in the numerator the same way round. Hence as required. Last edited by JaneFairfax (20101201 04:26:35) #7 20101207 06:55:05
Re: Permutations
#8 20110716 18:45:34
Re: PermutationsThe feeling of stability that you get with a tripod is present with an even permutation but not with an odd one (and this does not depend upon any significant subtleties of your arithmetic or settheoretic foundations) so the trick to getting a student to intuitively understand the difference between odd and evenness is to lead them somehow to this feeling, and the path is potentially different for every student since no two people start from the same point of view. 