1. Permutations or: group theory in 15 minutesMATH 47A FALL 2008INTRO TO MATH RESEARCHKIYOSHI IGUSAContents1. Permutations or: group theory in 15 minutes 1Date: September 3, 2008.0MATH 47A FALL 2008 INTRO TO MATH RESEARCH 11. Permutations or: group theory in 15 minutesFor those of you who already took a course in group theory, youprobably learned about “abstract groups” which are sets with binaryoperations satisfying a list of conditions. I want to talk about permu-tations. Those who already know group theory can think about thequestion:Why is every group isomorphic to a permutation group?Definition 1.1. A permutation on a set X is a bijection f : X → X.Recall that a bijection is a mapping which is(1) 1-1 (injective) and(2) onto (surjective).If X = {1, 2, · · · , n}, a permutation of X is called a permutation on nletters. The set of permutations of X will be denoted by P erm(X).I discussed three notations for permutations:(1) σ =1 2 3 43 4 2 1means σ(1) = 3, σ(2) = 4, σ(3) = 2, σ(4) =1 or σ(x) = y where x is given in the first row and y is given inthe second row.(2) (cycle form) σ = (1324). This means σ sends 1 to 3, 3 to 2, 2to 4 and 4 to 1: 1 → 3 → 2 → 4 → 1.(3) (graphic notation). Here you put the numbers x = 1, · · · , nvertically on the right, put y = 1, · · · , n vertically on the leftand connect each x to each y = f (x). For example, if f =(1423), you connect 1 on the right to f (1) = 4 on the left witha straight line, etc. In cycle notation, f = (1423).yxfx1 3 1}}zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz2 4 2tthhhhhhhhhhhhhhhhhhhhhhhhhh3 2 3ffMMMMMMMMMMMMMMMMMMMMMMMMMMMMM4 1 4ffMMMMMMMMMMMMMMMMMMMMMMMMMMMMM2 NOTESDefinition 1.2. If f, g ∈ P erm(X), fg = f ◦ g is the composition off and g. This is the permutation defined byfg(x) = f (g(x))It means you do g first and then f.Question: If g = (34) what is gf ? Write the answer in all three nota-tions and demonstrate the composition in the notation.(1) Stack up f, g, putting the first operation f on top and thesecond g underneath. Then cross out the second line:1 2 3 44 3 1 23 4 1 2=1 2 3 43 4 1 2(2) Write the cycles next to each other and compute the image ofeach x by applying the cycles one at a time going from right toleft:gf = (34)(1423) = (13)(24)for example:gf(1) =3(34)4(1423)1= 3(3) Draw the diagrams next to each other, putting the first permu-tation f on the right:y gfx1 3 3oo1}}zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz2 4 4oo2tthhhhhhhhhhhhhhhhhhhhhhhhhh3 1 2wwpppppppppppppp3ffMMMMMMMMMMMMMMMMMMMMMMMMMMMMM4 2 1ggNNNNNNNNNNNNNN4ffMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNote that g = (34) switches the “letters” in locations 3 and 4. Wediscussed the fact that two of the crossings cancel when we redraw thepicture:MATH 47A FALL 2008 INTRO TO MATH RESEARCH 3ygfx1 3 1uukkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk2 4 2uukkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk3 1 3iiSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS4 2 4iiSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSThen we discussed the number of