Rozkład permutacji.

[0Mniac]

Witam. Zmagam się z takim zadaniem: Rozłożyć na rozłączne cykle oraz zbadać parzystość następującej permutacji:

\(\displaystyle{ {1 2 3 4 5 6 7 8 9 10 11 12 \choose 8 4 1 3 7 11 6 2 12 5 9 10}}\)

I teraz nie wiem czy dobrze to wykonałem, rozkład u mnie wygląda tak:

\(\displaystyle{ \left( 1, 8, 2 \right) \cdot \left( 2, 4, 3 \right) \cdot \left( 3,1 \right) \cdot \left( 4,3 \right) \cdot \left( 5, 7, 6 \right) \cdot \left( 6, 11, 9 \right) \cdot \left( 7, 6 \right) \cdot \left( 8, 2 \right) \cdot \left( 9, 12, 10 \right) \cdot \left( 10, 5 \right) \cdot \left( 11, 9 \right) \cdot \left( 12, 10 \right)}\)

Natomiast przy parzystości liczba transpozycji to 5, czyli:

\(\displaystyle{ \left( 1, 8 \right)\left( 2, 4 \right)\left( 5, 7 \right)\left( 6, 11 \right)\left( 9, 12 \right)}\)

Czyli cykl nieparzysty.
Pytanie czy zadanie jest poprawnie rozwiązane?

[Peter Zof]

Skąd Ci wyszło \(\displaystyle{ (1, 8, 2)}\) ? Przecież 8 przechodzi na 6.

[ZF+GCH]

Skąd Ci wyszło \(\displaystyle{ (1, 8, 2)}\) ? Przecież 8 przechodzi na 6.

\(\displaystyle{ 8}\) przechodzi na \(\displaystyle{ 2}\). W dolnym wierszu przed \(\displaystyle{ 6}\) jest \(\displaystyle{ 11}\), więc akurat to jest ok.

Natomiast rozkład na cykle jest bardzo nieudany. Powinno być tak \(\displaystyle{ (1, 8, 2, 4, 3)(5, 7, 6, 11, 9, 12, 10)}\). Cykl musi być "domknięty". Gdy piszę, że cyklem jest \(\displaystyle{ (a, b, c)}\) to znaczy, że \(\displaystyle{ a}\) przechodzi na \(\displaystyle{ b}\), \(\displaystyle{ b}\) na \(\displaystyle{ c}\), \(\displaystyle{ c}\) na \(\displaystyle{ a}\). Twój zapis jest zatem niedobry. Ponadto, niektóre rzeczy powtarzasz : piszesz \(\displaystyle{ (2, 4, 3)}\), a potem znowu \(\displaystyle{ (4, 3)}\).

Rozkład na transpozycje również jest zły. Nie wiadomo na co przechodzi \(\displaystyle{ 3}\) oraz \(\displaystyle{ 10}\). Ponadto, z Twojego zapisu wynika np., że \(\displaystyle{ 7}\) przechodzi na \(\displaystyle{ 5}\). Iloczyn cykli (transpozycji) jest złożeniem, czyli należy czytać to tak : gdy piszę \(\displaystyle{ (1, 3)(1,2)}\), i chcę np. sprawdzić na co przechodzi \(\displaystyle{ 2}\), to sprawdzam od prawej : \(\displaystyle{ (1, 2)}\) oznacza, że \(\displaystyle{ 1}\) przechodzi na \(\displaystyle{ 2}\), a \(\displaystyle{ 2}\) na \(\displaystyle{ 1}\); mam więc, że \(\displaystyle{ 2}\) przechodzi na \(\displaystyle{ 1}\), stąd idę do kolejnego cyklu licząc od prawej strony, czyli do cyklu \(\displaystyle{ (1, 3)}\) i widzę, że \(\displaystyle{ 1}\) przechodzi na \(\displaystyle{ 3}\), ostatecznie więc \(\displaystyle{ 2}\) przechodzi na \(\displaystyle{ 3}\). Podobnie sprawdzając pozostałe "drogi" sprawdzisz, że \(\displaystyle{ (1, 3)(1, 2)=(1, 2, 3)}\). Wracając do naszego przykładu patrzę na Twój zapis \(\displaystyle{ \left( 1, 8 \right)\left( 2, 4 \right)\left( 5, 7 \right)\left( 6, 11 \right)\left( 9, 12 \right)}\), i np. chcę sprawdzić na co przechodzi \(\displaystyle{ 7}\). No więc pierwszy cykl od prawej z liczbą \(\displaystyle{ 7}\), to \(\displaystyle{ (5, 7)}\), więc \(\displaystyle{ 7}\) przechodzi na \(\displaystyle{ 5}\), przesuwam się dalej w lewo i widzę, że \(\displaystyle{ 5}\) już nie występuje, więc \(\displaystyle{ 7}\) przechodzi na \(\displaystyle{ 5}\), a wiemy, że przechodzi na \(\displaystyle{ 6}\).
Rozłożyłem naszą permutację na dwa rozłączne piecio- i siedmiowyrazowe cykle. Pokazałem Ci jak rozkłada się trzywyrazowy cykl na iloczyn transpozycji. Twoim zadaniem jest uogólnienie tego sposobu, tak byś umiał rozłożyć na iloczyn transpozycji cykle \(\displaystyle{ (1, 2, 3, 4, 5), (1, 2, 3, 4, 5, 6, 7)}\) i zastosować to do cykli \(\displaystyle{ (1, 8, 2, 4, 3), (5, 7, 6, 11, 9, 12, 10)}\)

[0Mniac]

\(\displaystyle{ {1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot \cdot 7 \cdot 8 \cdot \cdot 9 \cdot 10 \cdot 11 \cdot 12 \choose 8 \cdot 4 \cdot 1 \cdot 3 \cdot 7 \cdot 11 \cdot 6 \cdot 2 \cdot 12 \cdot 5 \cdot 9 \cdot 10}}\)

Może taki zapis będzie czytelniejszy, bo faktycznie z tego co napisałem ciężko jest coś wyciągnąć.

I zgodnie z tym co zrozumiałem transpozycja wyglądać będzie:

\(\displaystyle{ \left( 1,3\right) \left( 1,4\right) \left( 1,2 \right), \left( 1,8\right), \left( 5,10\right), \left( 5,12\right), \left( 5,9\right), \left( 5,11\right), \left( 5,6\right), \left( 5,7\right)}\)-- 14 cze 2015, o 15:14 --@UP, z tego co wyczytałem to potrzeba policzyć inwersje. Czyli dla lewego cyklu byłoby to:

\(\displaystyle{ (8,2),(8,4),(8,3),(4,3)}\), a prawy: \(\displaystyle{ (7,6),(11,9),(11,10),(12,10)}\)

Prawda?