Rozkład permutacji na cykle rozłączne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Wasilewski
Użytkownik
Użytkownik
Posty: 3921
Rejestracja: 10 gru 2007, o 20:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 36 razy
Pomógł: 1194 razy

Rozkład permutacji na cykle rozłączne

Post autor: Wasilewski »

Zadanie 1.
Dowieść, że rozkład permutacji na cykle rozłączne jest jednoznaczny (z dokładnością do kolejności).
Nie obraziłbym się za jakąś wskazówkę.
Zadanie 2.
Podać rozkład poniższych permutacji na cykle rozłączne, nie wypisując ich w postaci dwuwierszowej:
\(\displaystyle{ (1,2)(3,4,5)(1,2,3)(5,1,2), \\
(3,1,4,5)(1,2,3,4)(3,1,4,2)(1,2,3)}\)

W tym przypadku ciekawi mnie metoda, bo polecenie sugeruje, że można to zrobić w sprytny sposób, na który ja oczywiście nie wpadłem. A tradycyjną metodą wyszły mi takie rozkłady (mam nadzieję, że się nie pomyliłem):
\(\displaystyle{ (1,3,4)(2,5), \\
(1,4,5,3)}\)
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Rozkład permutacji na cykle rozłączne

Post autor: Zordon »

1. Weźmy permutację \(\displaystyle{ \tau}\) i załóżmy, że mamy dwa, istotnie różne rozkłady na cykle rozłączne tej permutacji (będę pisał nieformalnie, żeby się za bardzo nie namęczyć ). Tzn. istnieją \(\displaystyle{ a_1,a_2}\) takie, że w pierwszym rozkładzie występują w jednym cyklu, a w drugim w różnych (lub istnieją \(\displaystyle{ a_1,a_2}\) takie, że w drugim rozkładzie występują w jednym cyklu, a w pierwszym w różnych). Pamiętając o tym, że \(\displaystyle{ a,b}\) należą do jednego cyklu wtw. gdy istnieje n, że \(\displaystyle{ \tau^n(a)=b}\) i że każda permutacja jest bijekcją, można z tego wycisnąć sprzeczność

Edit: dlaczego istnieją takie \(\displaystyle{ a_1,a_2}\)? Bo gdyby nie istniały, to rozkłady byłyby identyczne.
Wasilewski
Użytkownik
Użytkownik
Posty: 3921
Rejestracja: 10 gru 2007, o 20:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 36 razy
Pomógł: 1194 razy

Rozkład permutacji na cykle rozłączne

Post autor: Wasilewski »

Dzięki, to jest dla mnie jasne. Mamy rozkład, sprawdzamy, ile razy trzeba złożyć ze sobą permutację, by zachodziła zapisana przez Ciebie równość (oznaczamy jako n). Jeśli mamy inny rozkład, to składamy permutację n razy i okazuje się, że ta równość zachodzi, zatem \(\displaystyle{ a_{1} \ i \ a_{2}}\) są w jednym cyklu.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Rozkład permutacji na cykle rozłączne

Post autor: Zordon »

Wasilewski pisze:Dzięki, to jest dla mnie jasne. Mamy rozkład, sprawdzamy, ile razy trzeba złożyć ze sobą permutację, by zachodziła zapisana przez Ciebie równość (oznaczamy jako n). Jeśli mamy inny rozkład, to składamy permutację n razy i okazuje się, że ta równość zachodzi, zatem \(\displaystyle{ a_{1} \ i \ a_{2}}\) są w jednym cyklu.
Tak, dokładnie.

-- 8 lutego 2009, 22:12 --

A co do wyznaczonych rozkładów to wydaje mi sie, że nie są dobre, chyba, że jest tu przyjęta inna konwencja zapisu złożenia funkcji. Tzn. standardowo jest
\(\displaystyle{ fg(x)=f(g(x))}\)

A u Ciebie wygląda jakbyś przyjmował:
\(\displaystyle{ fg(x)=g(f(x))}\)

Dla przykładu dla pierwszej permutacji wyszło Ci, że 1 przechodzi na 3 (bo jest cykl \(\displaystyle{ (1,3,4,)}\)). Według zwykłej konwencji byłoby (patrzymy od prawej) \(\displaystyle{ 1\to2\to3\to4\to4}\) czyli 1 przechodzi na 4.
Wasilewski
Użytkownik
Użytkownik
Posty: 3921
Rejestracja: 10 gru 2007, o 20:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 36 razy
Pomógł: 1194 razy

Rozkład permutacji na cykle rozłączne

Post autor: Wasilewski »

Coś pomyliłem i źle liczyłem. Ale fajnie, że napisałeś to w taki sposób, bo teraz już widzę metodę.
ODPOWIEDZ