Permutacja, rozkład na iloczyn cykli rozłącznych
-
- Użytkownik
- Posty: 11
- Rejestracja: 21 lis 2010, o 15:29
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
Permutacja, rozkład na iloczyn cykli rozłącznych
Witam, mam permutację
\(\displaystyle{ {1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \choose 5 \ 2 \ 4 \ 7 \ 8 \ 1 \ 3 \ 9 \ 6}}\)
i mam ją przedstawić jako iloczyn cykli rozłącznych. Oraz przedstawić jako iloczyn transpozycji.
Czy mógłby ktoś w miarę step-by-step opisać jakiś algorytm najwygodniejszy do rozwiązania kolejno pkt'u a i b ? thx
\(\displaystyle{ {1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \choose 5 \ 2 \ 4 \ 7 \ 8 \ 1 \ 3 \ 9 \ 6}}\)
i mam ją przedstawić jako iloczyn cykli rozłącznych. Oraz przedstawić jako iloczyn transpozycji.
Czy mógłby ktoś w miarę step-by-step opisać jakiś algorytm najwygodniejszy do rozwiązania kolejno pkt'u a i b ? thx
Ostatnio zmieniony 25 cze 2011, o 18:48 przez ares41, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .
-
- Użytkownik
- Posty: 692
- Rejestracja: 19 cze 2011, o 23:29
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 107 razy
Permutacja, rozkład na iloczyn cykli rozłącznych
cykle rozłączne (patrzysz co na co przechodzi - jak się zapętla, to bierzesz następny wyraz, który jeszcze nie wystąpił):
\(\displaystyle{ (1 5 8 9 6) (3 4 7)}\)
\(\displaystyle{ (1 5 8 9 6) (3 4 7)}\)
- ares41
- Użytkownik
- Posty: 6499
- Rejestracja: 19 sie 2010, o 08:07
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 142 razy
- Pomógł: 922 razy
Permutacja, rozkład na iloczyn cykli rozłącznych
Bierzesz pierwszą liczbę. Jest nią \(\displaystyle{ 1}\).
Patrzysz w co ona przechodzi (w piątkę) i zapisujesz:
\(\displaystyle{ \left(1, \ 5,.....}\)
Teraz szukasz piątki i patrzysz w co ona przechodzi.
\(\displaystyle{ \left(1, \ 5, \ 8,.....}\)
Postępujesz tak dalej aż w końcu dochodzisz do:
\(\displaystyle{ \left(1, \ 5, \ 8, \ 9, \ 6 \right)}\)
i tutaj domykasz nawias i zaczynasz nowy cykl.:
Kolejną liczbą jest dwójka, która przechodzi sama w siebie więc ją pomijasz.
Następna liczba to trójka:
Masz więc:
\(\displaystyle{ \left(1, \ 5, \ 8, \ 9, \ 6 \right) \circ \left(3, \ 4 , \ 7\right)}\)
Patrzysz w co ona przechodzi (w piątkę) i zapisujesz:
\(\displaystyle{ \left(1, \ 5,.....}\)
Teraz szukasz piątki i patrzysz w co ona przechodzi.
\(\displaystyle{ \left(1, \ 5, \ 8,.....}\)
Postępujesz tak dalej aż w końcu dochodzisz do:
\(\displaystyle{ \left(1, \ 5, \ 8, \ 9, \ 6 \right)}\)
i tutaj domykasz nawias i zaczynasz nowy cykl.:
Kolejną liczbą jest dwójka, która przechodzi sama w siebie więc ją pomijasz.
Następna liczba to trójka:
Masz więc:
\(\displaystyle{ \left(1, \ 5, \ 8, \ 9, \ 6 \right) \circ \left(3, \ 4 , \ 7\right)}\)
-
- Użytkownik
- Posty: 11
- Rejestracja: 21 lis 2010, o 15:29
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
Permutacja, rozkład na iloczyn cykli rozłącznych
Understood. Dziękuję.
jeżeli chodzi zaś o część
b) przedstawienie jako iloczyn transpozycji to jeśli dobrze rozumiem robimy to tak:
dzielimy permutację na iloczyn cykli, sprawdzamy ktore sa transponowane i je zapisujemy jako iloczyn?
czyli:
\(\displaystyle{ \left( 1,6\right)\left( 3,7\right)\left( 4,3\right)\left( 5,1\right)\left( 6,9\right)\left( 7,4\right)\left( 8,5\right)\left( 9,8\right)}\)
mamy tutaj 5 transpozycji:
\(\displaystyle{ \left( 4,3\right),\left( 5,1\right),\left( 7,4\right),\left( 8,5\right),\left( 9,5\right)}\)
no i teraz jako iloczyn:
\(\displaystyle{ \left( 4,3\right) \cdot \left( 5,1\right) \cdot \left( 7,4\right) \cdot \left( 8,5\right) \cdot \left( 9,5\right)}\)
Parzystość: liczba transpozycji to 5, więc sgn(PERM)=(-1) czyli nieparzysta
Dobrze rozumiem?, poprawcie jeśli gdzieś jest błąd.
jeżeli chodzi zaś o część
b) przedstawienie jako iloczyn transpozycji to jeśli dobrze rozumiem robimy to tak:
dzielimy permutację na iloczyn cykli, sprawdzamy ktore sa transponowane i je zapisujemy jako iloczyn?
czyli:
\(\displaystyle{ \left( 1,6\right)\left( 3,7\right)\left( 4,3\right)\left( 5,1\right)\left( 6,9\right)\left( 7,4\right)\left( 8,5\right)\left( 9,8\right)}\)
mamy tutaj 5 transpozycji:
\(\displaystyle{ \left( 4,3\right),\left( 5,1\right),\left( 7,4\right),\left( 8,5\right),\left( 9,5\right)}\)
no i teraz jako iloczyn:
\(\displaystyle{ \left( 4,3\right) \cdot \left( 5,1\right) \cdot \left( 7,4\right) \cdot \left( 8,5\right) \cdot \left( 9,5\right)}\)
Parzystość: liczba transpozycji to 5, więc sgn(PERM)=(-1) czyli nieparzysta
Dobrze rozumiem?, poprawcie jeśli gdzieś jest błąd.
- ares41
- Użytkownik
- Posty: 6499
- Rejestracja: 19 sie 2010, o 08:07
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 142 razy
- Pomógł: 922 razy
Permutacja, rozkład na iloczyn cykli rozłącznych
Nie bardzo wiem, co chciałeś tutaj zrobić.
Wystarczy po prostu skorzystać, ze wzoru:
\(\displaystyle{ (i_1,\ i_2, \ ,...., \ i_{k-1}, \ i_k)=(i_1, \ i_k) \circ (i_1, \ i_{k-1}) \circ ....\circ (i_1, \ i_2)}\)
Wystarczy po prostu skorzystać, ze wzoru:
\(\displaystyle{ (i_1,\ i_2, \ ,...., \ i_{k-1}, \ i_k)=(i_1, \ i_k) \circ (i_1, \ i_{k-1}) \circ ....\circ (i_1, \ i_2)}\)
-
- Użytkownik
- Posty: 11
- Rejestracja: 21 lis 2010, o 15:29
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
Permutacja, rozkład na iloczyn cykli rozłącznych
Więc uzyskam:
\(\displaystyle{ \left( 1,6\right)\left( 1,9\right)\left( 1,8\right)\left( 1,5\right)\left( 3,7\right)\left( 3,4\right)}\)
i jest to już iloczyn transpozycji ?.
Jest tego sztuk 6 => permutacja parzysta ?
[czy źle Ciebie zrozumiałem]
\(\displaystyle{ \left( 1,6\right)\left( 1,9\right)\left( 1,8\right)\left( 1,5\right)\left( 3,7\right)\left( 3,4\right)}\)
i jest to już iloczyn transpozycji ?.
Jest tego sztuk 6 => permutacja parzysta ?
[czy źle Ciebie zrozumiałem]
- ares41
- Użytkownik
- Posty: 6499
- Rejestracja: 19 sie 2010, o 08:07
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 142 razy
- Pomógł: 922 razy
Permutacja, rozkład na iloczyn cykli rozłącznych
Tak. Możesz to sprawdzić wykonując te transpozycje ( od prawej) dla wyjściowego układu liczb.PowerMan pisze:i jest to już iloczyn transpozycji ?.
Tak.PowerMan pisze:Jest tego sztuk 6 => permutacja parzysta ?
-
- Użytkownik
- Posty: 11
- Rejestracja: 21 lis 2010, o 15:29
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
Permutacja, rozkład na iloczyn cykli rozłącznych
Trochę odchodzi od tematu, ale nie będę tworzył nowego.
Wydaje mi się że tak, lecz nie mam pewności:
rząd permutacji \(\displaystyle{ f}\) w grupie \(\displaystyle{ S_{9}}\) to \(\displaystyle{ NWW}\) długości jej cykli rozłącznych , czyli rzędem tej permutacji jest:
\(\displaystyle{ NWW(5,3)=15}\)
czyli
\(\displaystyle{ rz(P)=15.}\)
?
--Tu były głupoty--
Wydaje mi się że tak, lecz nie mam pewności:
rząd permutacji \(\displaystyle{ f}\) w grupie \(\displaystyle{ S_{9}}\) to \(\displaystyle{ NWW}\) długości jej cykli rozłącznych , czyli rzędem tej permutacji jest:
\(\displaystyle{ NWW(5,3)=15}\)
czyli
\(\displaystyle{ rz(P)=15.}\)
?
--Tu były głupoty--
Ostatnio zmieniony 25 cze 2011, o 21:00 przez PowerMan, łącznie zmieniany 2 razy.
- ares41
- Użytkownik
- Posty: 6499
- Rejestracja: 19 sie 2010, o 08:07
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 142 razy
- Pomógł: 922 razy
Permutacja, rozkład na iloczyn cykli rozłącznych
Ogólnie:
Rzędem cyklu jest jego długość. Jeśli permutacja jest iloczynem cykli rozłącznych to jej rzędem jest najmniejsza wspólna wielokrotność długości cykli wchodzących w jej skład.
Rzędem cyklu jest jego długość. Jeśli permutacja jest iloczynem cykli rozłącznych to jej rzędem jest najmniejsza wspólna wielokrotność długości cykli wchodzących w jej skład.
Jeżeli u Ciebie \(\displaystyle{ 5}\) i \(\displaystyle{ 3}\) są długościami cykli rozłącznych, których iloczynem jest permutacja \(\displaystyle{ f}\) to to co napisałeś jest dobrze.PowerMan pisze: \(\displaystyle{ NWW(5,3)=15}\)
czyli
\(\displaystyle{ rz(P)=15}\).