Zakres zagadnień
Algebra
Permutacje
1 Odwzorowania wzajemnie jednoznaczne zbioru na siebie
Adam Dąbrowski 2 Grupy odwzorowań
Politechnika Poznańska
3 Grupy permutacji
Wydział Informatyki i Zarządzania
Katedra Sterowania i Inżynierii Systemów
Pracownia Układów Elektronicznych i Przetwarzania Sygnałów
4 Działania na permutacjach
31 stycznia 2009
5 Transpozycje i permutacje cykliczne
6 Permutacje parzyste i nieparzyste
7 Studenckie Koło Naukowe Decybel
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 1 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 2 / 126
Pojęcie permutacji Wzajemnie jednoznaczne odwzorowanie zbioru na siebie
Definicja
Relację R określoną na zbiorze A nazywa się odwzorowaniem
(przekształceniem, transformacją) Ć : A A , zbioru A w siebie, jeśli
"a"A"b"AaRb oraz "a"A"b,c"AaRb i aRc Ò! b = c .
co zapisuje się jako b = Ć(a). Jeśli
"b"A"a"A Ć(a) =b
to odwzorowanie h : A A przekształca zbiór A na siebie. Jeśli istnieje
Definicja
jeden i tylko jeden taki element a, to odwzorowanie nazywamy wzajemnie
Permutatio po Å‚acinie oznacza wymianÄ™, przestawienie, podstawienie,
jednoznacznym (jedno-jednoznacznym, różnowartościowym lub
alegoriÄ™.
odwracalnym). Wówczas istnieje odwzorowanie odwrotne Ć-1 : A A
Permutacja w algebrze to wzajemnie jednoznaczne przekształcenie
zbioru A na siebie takie, że
pewnego zbioru na siebie. Najczęściej ten termin jest używany
w odniesieniu do zbiorów skończonych.
"b"A"a"A a = Ć-1(b)
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 3 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 4 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A
A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 5 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 6 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 7 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 8 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 9 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 10 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 11 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 12 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 13 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 14 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 15 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 16 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 17 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 18 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 19 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 20 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 21 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 22 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 23 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 24 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 25 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 26 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 27 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 28 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 29 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 30 / 126
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A = p(A)
A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 31 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 32 / 126
Czy wiedza na temat permutacji może przynieść sławę? Składanie odwzorowań
Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru
TAK!
A na siebie:
Ć : a " A Ć(a) " A i È : b " A È(b) " A .
Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie,
przy czym
(È · Ć)(·) =È(Ć(·)) .
A
Zdjęcie przedstawia pomnik
Mariana Adama Rejewskiego w Bydgoszczy
kryptologa, który dzięki wiedzy dotyczącej teorii permutacji złamał
kody hitlerowskiej maszyny o nazwie Enigma, szyfrujÄ…cej teksty.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 33 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 34 / 126
Składanie odwzorowań Składanie odwzorowań
Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru
A na siebie: A na siebie:
Ć : a " A Ć(a) " A i È : b " A È(b) " A . Ć : a " A Ć(a) " A i È : b " A È(b) " A .
Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie, Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie,
przy czym przy czym
(È · Ć)(·) =È(Ć(·)) . (È · Ć)(·) =È(Ć(·)) .
A A
A
A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 35 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 36 / 126
Składanie odwzorowań Składanie odwzorowań
Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru
A na siebie: A na siebie:
Ć : a " A Ć(a) " A i È : b " A È(b) " A . Ć : a " A Ć(a) " A i È : b " A È(b) " A .
Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie, Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie,
przy czym przy czym
(È · Ć)(·) =È(Ć(·)) . (È · Ć)(·) =È(Ć(·)) .
A A A AA A
A A A A
A
A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 37 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 38 / 126
Składanie odwzorowań Grupy odwzorowań
Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru
A na siebie:
Składanie odwzorowań jako mnożenie
Ć : a " A Ć(a) " A i È : b " A È(b) " A .
W zbiorze wszystkich wzajemnie jednoznacznych odwzorowań dowolnego
Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie,
zbioru A na siebie, Ć : a " A Ć(a) " A, skÅ‚adanie odwzorowaÅ„ È(Ć(a))
przy czym
można traktować jako działanie o cechach mnożenia, przy czym
(È · Ć)(·) =È(Ć(·)) .
(È · Ć)(·) =È(Ć(·)):
A AA A
dziaÅ‚anie È · Ć jest Å‚Ä…czne,
istnieje element neutralny, którym jest odwzorowanie
A
A
identycznościowe (neutralne),
dla każdego wzajemnie jednoznacznego odwzorowania istnieje
odwzorowanie odwrotne, w którym po prostu zmieniono kierunek
przyporządkowania elementów.
A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 39 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 40 / 126
Odwzorowanie odwrotne Odwzorowanie odwrotne
Odwzorowanie odwrotne do wzajemnie jednoznacznego odwzorowania Ć(·) Odwzorowanie odwrotne do wzajemnie jednoznacznego odwzorowania Ć(·)
dowolnego zbioru A na siebie dowolnego zbioru A na siebie
Ć : a " A Ć(a) " A Ć : a " A Ć(a) " A
to odwzorowanie È(·) to odwzorowanie È(·)
È = Ć-1 : b = Ć(a) " A È(b) =a " A È = Ć-1 : b = Ć(a) " A È(b) =a " A
Odwzorowanie odwrotne polega na zmianie kierunku przyporzÄ…dkowania Odwzorowanie odwrotne polega na zmianie kierunku przyporzÄ…dkowania
elementów. elementów.
A A
A A
A A
A A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 41 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 42 / 126
Grupy symetryczne Grupy permutacji
Definicja
Wzajemnie jednoznaczne odwzorowanie zbioru A = {a1, a2, . . . , an} na
Twierdzenie
siebie, p : A A, nazywa siÄ™ permutacjÄ… p tego zbioru.
Zbiór wszystkich wzajemnie jednoznacznych odwzorowań dowolnego zbioru
A na siebie jest grupą ze względu na składanie (mnożenie) odwzorowań.
Notacja
PermutacjÄ™ przyporzÄ…dkowujÄ…cÄ… elementowi ak, k = 1, 2, . . . , n, element
Definicja
aik , ik = 1, 2, . . . , n, co zapisujemy aik = p(ak), oznaczamy symbolicznie:

Grupę wzajemnie jednoznacznych odwzorowań dowolnego zbioru A na a1 a2 . . . an
siebie nazywa siÄ™ grupÄ… symetrycznÄ… zbioru A i oznacza siÄ™ symbolem SA. a ai2 . . . ain
i1
1 2 . . . n
lub prościej
i1 i2 . . . in
a nawet po prostu (i1 i2 . . . in)
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 43 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 44 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 2 4 3 1 3 1 4 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 45 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 46 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 2 4 3 1 3 1 4 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 47 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 48 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 2 4 3 1 3 1 4 2 3
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 49 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 50 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 4 3 1 3 1 4 2 3
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 51 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 52 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 4 3 1 3 1 4 2 3
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 53 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 54 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 2 4 3 1 3 1 4 2 3 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 55 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 56 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 2 4 3 1 3 1 4 2 3 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 57 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 58 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 2 4 3 1 3 1 4 2 3 2 1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 59 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 60 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 2 4 3 1 3 1 4 2 3 2 1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 61 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 62 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 2 4 3 1 3 1 4 2 3 2 1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 63 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 64 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Obliczmy iloczyn następujących permutacji
Przykład

1 2 3 4 1 2 3 4 1 2 3 4
Obliczmy iloczyn następujących permutacji
· =
2 4 3 1 3 1 4 2 3 2 1 4

1 2 3 4 1 2 3 4 1 2 3 4
· =
Zmieniając porządek czynników otrzymujemy
2 4 3 1 3 1 4 2 3 2 1 4

1 2 3 4 1 2 3 4 1 2 3 4
· =
3 1 4 2 2 4 3 1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 65 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 66 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 3 1 4 2 2 4 3 1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 67 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 68 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 3 1 4 2 2 4 3 1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 69 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 70 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 3 1 4 2 2 4 3 1 1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 71 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 72 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 3 1 4 2 2 4 3 1 1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 73 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 74 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 3 1 4 2 2 4 3 1 1 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 75 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 76 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 3 1 4 2 2 4 3 1 1 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 77 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 78 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 3 1 4 2 2 4 3 1 1 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 79 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 80 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 4 3 1 4 2 2 4 3 1 1 2 4
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 81 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 82 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 4 3 1 4 2 2 4 3 1 1 2 4
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 83 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 84 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 4 3 1 4 2 2 4 3 1 1 2 4 3
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 85 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 86 / 126
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Obliczmy iloczyn następujących permutacji
Przykłady

1 2 3 4 1 2 3 4 1 2 3 4
Obliczmy iloczyn następujących permutacji
· =
2 4 3 1 3 1 4 2 3 2 1 4

1 2 3 4 1 2 3 4 1 2 3 4
· =
Zmieniając porządek czynników otrzymujemy
2 4 3 1 3 1 4 2 3 2 1 4

1 2 3 4 1 2 3 4 1 2 3 4
Zmieniając porządek czynników otrzymujemy
· =
3 1 4 2 2 4 3 1 1 2 4 3

1 2 3 4 1 2 3 4 1 2 3 4
· =
Mnożenie przez permutację neutralną
3 1 4 2 2 4 3 1 1 2 4 3

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
1 2 3 4 3 1 4 2 3 1 4 2 1 2 3 4 3 1 4 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 87 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 88 / 126
Ilustracja notacji uproszczonej Działania na permutacjach  zapis uproszczony
Mnożenie
Przykłady
zauważmy, że
PermutacjÄ™ (2 4 3 1) · (3 1 4 2) =(3 2 1 4)

1 2 3 4
natomiast
2 4 3 1
(3 1 4 2) · (2 4 3 1) =(1 2 4 3)
w uproszczeniu zapisujemy jako
Mnożenie permutacji w ogólności nie jest przemienne!
(2 4 3 1)
Odwracanie permutacji
a permutacjÄ™

ZamieniajÄ…c rolami liczbÄ™ z jej pozycjÄ… otrzymuje siÄ™ permutacjÄ™
1 2 3 4
odwrotnÄ…, np.
3 1 4 2
(3 1 4 2)-1 =(2 4 1 3)
zapisujemy w uproszczeniu jako
Permutacja identycznościowa (neutralna)  element jednostkowy
(3 1 4 2)
p · (1 2 . . . n) =(1 2 . . . n) · p = p
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 89 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 90 / 126
Transpozycje Permutacje cykliczne
Definicja
Permutację p " Sn nazywamy cykliczną, jeśli dla pewnych różnych
Definicja
elementów permutacji neutralnej k1, k2, . . . , km, m n zachodzi:
PermutacjÄ™
p : k1 k2 , p : k2 k3 , . . . , p : km-1 km , p : km k1
(1 . . . i - 1 j i + 1 . . . j - 1 i j + 1 . . . n) ,
a pozostałe elementy nie zmieniają swoich pozycji. Liczbę m nazywamy
przy czym n 2, nazywamy transpozycją i oznaczamy w skrócie
rzędem permutacji cyklicznej p.
(i j) lub (j i)
Uwaga
Uwaga Permutację cykliczną p oznaczamy w skrócie jako (k1 k2 . . . km) lub
równoważnie (k2 k3 . . . km, k1) lub . . . lub (km k1 k2 . . . km-1)
Zauważmy, że
(i j)-1 =(i j)
Przykład
(2 4 3 1 5 6 7 8 9) =(1 2 4) =(2 4 1) =(4 1 2).
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 91 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 92 / 126
Wnioski dotyczÄ…ce permutacji cyklicznych Enigma  hitlerowska maszyna szyfrujÄ…ca za pomocÄ…
permutacji cyklicznych
Przykład
Skrócone oznaczenie permutacji cyklicznych jest wygodne lecz może
niekiedy być z
ródłem nieporozumień, np. (1 3 2) może oznaczać
permutację trójelementową lub permutację cykliczną o większej
liczbie elementów, w której 1 zmienia się w 3, 3 zmienia się w 2, a 2
zmienia siÄ™ w 1.
Jednoelementowa permutacja cykliczna jest permutacjÄ… jednostkowÄ…
(identycznościową), np. (1 2 3 4) =(1) =(2) =(3) =(4) .
Transpozycja jest dwuelementowÄ… permutacjÄ… cyklicznÄ….
Permutacje cykliczne, które nie mają elementów wspólnych są
nazywane permutacjami rozłącznymi lub niezależnymi.
Iloczyn permutacji rozłącznych jest przemienny, np.
(2 1 4 3) =(1 2) · (3 4) =(3 4) · (1 2)
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 93 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 94 / 126
Marian Adam Rejewski Permutacje cykliczne do szyfrowania tekstu
Polski matematyk i kryptolog Marian Adam Rejewski (który urodził się 16.
sierpnia 1905 r. w Bydgoszczy, studia wyższe z zakresu filozofii ukończył
na Uniwersytecie Poznańskim w 1929 r., zmarł 13. lutego 1980 r. w
Warszawie) po raz pierwszy złamał kod Enigmy już w 1932 r. Dzięki temu
sukcesowi i dalszym wieloletnim pracom wspólnie z Henrykiem Zygalskim
i Jerzym Różyckim nad łamaniem kodów ciągle ulepszanych wersji Enigmy Przykład permutacji cyklcznej wykorzystywanej do szyfrowania tekstu
wywiad brytyjski był w stanie odczytywać zaszyfrowaną korespondencję za pomocą maszyny Enigma
niemiecką. To w istotny sposób przyczyniło się do wygrania II wojny
światowej przez aliantów.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 95 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 96 / 126
Potęgowanie permutacji cyklicznych Dekompozycja permutacji cyklicznych
Twierdzenie
Uwaga
Każdą permutację cykliczną p rzędu m można przedstawić w postaci
Niech p będzie permutacją cykliczną rzedu m. Zauważmy, że:
iloczynu m - 1 transpozycji.
p2 : k1 k3 , p : k2 k4 , . . . , p : km-1 k1 , p : km k2
p3 : k1 k4 , p : k2 k5 , . . . , p : km-1 k2 , p : km k3
Dowód
.
.
Niech permutacja p ma postać (k1 k2 . . . km). Wówczas
.
pm-1 : k1 km, p : k2 k1, . . . , p : km-1 km-2, p : km km-1
p =(k1km) · (k1km-1) · . . . · (k1k3) · (k1k2) .
pm : k1 k1, p : k2 k2, . . . , p : km-1 km-1, p : km km
Istotnie, permutacja (k1k2) ustawia docelowo element k2 na pozycji k1, a
jednocześnie chwilowo  element k1 na pozycji k2. Na pozycji k2
Wnioski
powinien znalez
ć się jednak element k3. Dokonuje się to właśnie poprzez
pm jest permutacją identycznościową
pomnożenie przez permutację (k1k3), która wstawia element k3 wmiejsce,
pm-1 = p-1
gdzie był do tej pory element k1. Dalsze kroki są analogiczne.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 97 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 98 / 126
Przykład dekompozycji permutacji cyklicznej Dekompozycja permutacji na permutacje cykliczne
Twierdzenie
Dowolna permutacja p jest cykliczna lub można ją rozłożyć na iloczyn
Przykład
niezależnych (rozłącznych) permutacji cyklicznych. Iloczyn permutacji
Zauważmy, że
rozłącznych jest przemienny.
(2 3 1 4) =(1 2 3)
Dowód
oraz
Wybierzmy najmniejszą spośród liczb, które przy permutacji p nie
(1 2) =(2 1 3 4)
przechodzÄ… w siebie. Ta liczba przechodzi w innÄ…, a ta w jeszcze innÄ…. W
i
końcu cykl się zamyka, tworząc permutację cykliczną p1, bo permutacja p
(1 3) =(3 2 1 4)
ma skończoną liczbę elementów. Jeśli w permutacji p wszystkie liczby nie
wzięte w ten sposób pod uwagę przechodzą w siebie, to p = p1. Jeśli nie,
zatem
to bierzemy najmniejszą spośród nich i kontynuujemy ten proces, tworząc
permutacje cykliczne p2, p3 itd. Proces ten kończy się na permutacji
(1 3) · (1 2) =(3 2 1 4) · (2 1 3 4) =(2 3 1 4) =(1 2 3)
cyklicznej pl, bo permutacja p ma skończoną liczbę elementów. Zatem
p = p1 · p2 · . . . · pl. Permutacje p1, p2, . . . , pl sÄ… rozÅ‚Ä…czne, bo nie majÄ…
elementów wspólnych i dlatego ich iloczyn jest przemienny.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 99 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 100 / 126
Dekompozycja permutacji na permutacje cykliczne Dekompozycja permutacji na transpozycje
Wniosek
Przykład
Każdą permutację można przedstawić w postaci iloczynu transpozycji.
(2 4 3 1 7 8 5 9 6) =
Przykład
=(1 2 4) · (5 7) · (6 8 9)
(2 4 3 1 7 8 5 9 6) =(1 2 4) · (5 7) · (6 8 9)
=(5 7) · (6 8 9) · (1 2 4)
ale
=(6 8 9) · (1 2 4) · (5 7)
(1 2 4) =(1 4) · (1 2)
=(1 2 4) · (6 8 9) · (5 7)
oraz
=(6 8 9) · (5 7) · (1 2 4)
(6 8 9) =(6 9) · (6 8)
=(5 7) · (1 2 4) · (6 8 9)
zatem
(2 4 3 1 7 8 5 9 6) =(1 4) · (1 2) · (5 7) · (6 9) · (6 8)
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 101 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 102 / 126
Permutacje parzyste i nieparzyste Permutacje parzyste i nieparzyste
Permutacje parzyste
Wnioski
Permutację nazywa się parzystą, jeśli jest ona iloczynem parzystej liczby
Transpozycje sÄ… permutacjami nieparzystymi.
transpozycji.
m elementowa permutacja cykliczna jest nieparzysta, gdy liczba m
jest parzysta i odwrotnie.
Permutacje nieparzyste
n elementów tworzy n! permutacji, w tym dla n 2 jest (1/2) · n!
W przeciwnym przypadku permutacjÄ™ nazywa siÄ™ nieparzystÄ….
permutacji parzystych i tyle samo nieparzystych.
Wyznacznik liczbowej macierzy kwadratowej jest sumÄ… wszystkich
Przykład
możliwych iloczynów elementów tej macierzy po jednym z każdego
Daną permutację można rozłożyć na transpozycje na różne sposoby, np.
wiersza i po jednym z każdej kolumny, przy czym jeśli np. wiersze
uporządkuje się po kolei, to kolumny występują w kolejnościach
(2 1 4 3) =(1 2) · (3 4) =(1 3) · (1 2) · (2 4) · (2 3)
tworzących wszystkie możliwe permutacje; iloczyny odpowiadające
permutacjom parzystym występują ze znakiem  + , a odpowiadające
lecz zawsze liczba tych transpozycji jest dla danej permutacji parzysta
permutacjom nieparzystym sÄ… brane ze znakiem  - .
bÄ…dz
nieparzysta. Powyższa, przykładowa permutacja jest zatem parzysta.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 103 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 104 / 126
Wyznacznik Zabawa w permutacje
Definicja wyznacznika


a11 a12 · · · a1n


a21 a22 · · · a2n


= (-1)ka1p(1) · a2p(2) · . . . · anp(n)
.

.
.

p"SA


an1 an2 · · · ann
SA jest zbiorem wszystkich n elementowych permutacji p, zaÅ› k jest liczbÄ…
transpozycji składających się na permutację p.
Przykład


a11 a12 a13

+a11 · a22 · a33 + a13 · a21 · a32 + a12 · a23 · a31

Ucząc się o permutacjach, można zagrać w bierki!
a21 a22 a23 =

-a13 · a22 · a31 - a11 · a23 · a32 - a12 · a21 · a33
Trzeba znalez
ć taką kolejność wyjmowania bierek,

a31 a32 a33
aby nie poruszyć tych, które jeszcze pozostały w stosie.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 105 / 126 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 106 / 126
Studenckie Koło Naukowe Decybel  ZAPRASZAMY!
www.decybel.put.poznan.pl
PrzewodniczÄ…cy:
Przemysław Spychała
[e-mail]
Opiekun:
Profesor Adam DÄ…browski
Sekcja Teleinformatyki,
Technik Internetowych
i Mikroprocesorów
Sekcja Telewizji i Systemów
Wizyjnych Robotów
Sekcja Biometrii i Interfejsów
Człowiek-Komputer
Sekcja Akustyki Technicznej
i Psychoakustyki
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 107 / 126