Mam permutację \(\displaystyle{ { 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \choose 2 \ 3 \ 9 \ 1 \ 5 \ 4 \ 8 \ 7 \ 6} }\).
Rozłożyłam ją na transpozycje
\(\displaystyle{ (1 \ 4)(1 \ 6)(1 \ 9)(1 \ 3)(1 \ 2)(5)(7 \ 8)}\)
i teraz chce te transpozycje rozłożyć na transpozycje liczb sąsiednich.
Zrobiłabym to tak:
\(\displaystyle{ (1 \ 4) = (1 \ 2)(2 \ 3)(3 \ 4)}\) i tak po kolei rozpisując każdą coś by mi wyszło, jednak zastanawiam się czy to w ogóle jest poprawne i czy nie da się sprytniej.
Jeszcze: jak zapisać transpozycję liczb sąsiednich takiego cyklu \(\displaystyle{ (5)}\)?
Rozkład na transpozycje liczb sąsiednich
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Rozkład na transpozycje liczb sąsiednich
Jeśli wymnożysz te transpozycje, to zobaczysz, że podana równość nie jest prawdziwa. Poprawnie rozkłada się tak - na przykładzie:
\(\displaystyle{ (2 \ 5) = (2 \ 3)(3 \ 4)(4 \ 5)(4 \ 3)(3 \ 2)}\).
-
- Użytkownik
- Posty: 101
- Rejestracja: 7 gru 2019, o 19:36
- Płeć: Kobieta
- wiek: 19
- Podziękował: 58 razy
Re: Rozkład na transpozycje liczb sąsiednich
Okej, czyli muszę jakby "wrócić". Czyli każdą transpozycję powyżej muszę tak rozpisać? Trochę tego dużo
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Rozkład na transpozycje liczb sąsiednich
Dla pojedynczej transpozycji powyższa metoda daje rozkład na najmniejszą możliwą liczbę transpozycji liczb sąsiednich. Można za to rozkładać na transpozycje liczb sąsiednich od razu całą permutację i wtedy najmniejsza ich liczba jest równa liczbie inwersji wyjściowej permutacji. Robi się to tak: w każdym kroku chwytamy najmniejszą liczbę w dolnym rzędzie, która nie jest na swoim miejscu (kolor czerwony), i przesuwamy ją tak, by się na nim znalazła, pchając wszystkie liczby po drodze o jedną pozycję w prawo (kolor niebieski). Taka operacja powoduje wyłączenie z prawej strony odpowiedniego cyklu (kolor zielony). Przykład:
\(\displaystyle{
\begin{align*}
\binom{\textcolor{limegreen}{1 \ 2 \ 3 \ 4} \ 5 \ 6 \ 7 \ 8 \ 9}{\textcolor{blue}{2 \ 3 \ 9} \ \textcolor{red}{1} \ 5 \ 4 \ 8 \ 7 \ 6} & = \binom{\textcolor{limegreen}{1 \ 2 \ 3 \ 4} \ 5 \ 6 \ 7 \ 8 \ 9}{\textcolor{red}{1} \ \textcolor{blue}{2 \ 3 \ 9} \ 5 \ 4 \ 8 \ 7 \ 6} (\textcolor{limegreen}{1 \ 2 \ 3 \ 4}) \\
\binom{1 \ 2 \ 3 \ \textcolor{limegreen}{4 \ 5 \ 6} \ 7 \ 8 \ 9}{1 \ 2 \ 3 \ \textcolor{blue}{9 \ 5} \ \textcolor{red}{4} \ 8 \ 7 \ 6} & = \binom{1 \ 2 \ 3 \ \textcolor{limegreen}{4 \ 5 \ 6} \ 7 \ 8 \ 9}{1 \ 2 \ 3 \ \textcolor{red}{4} \ \textcolor{blue}{9 \ 5} \ 8 \ 7 \ 6} (\textcolor{limegreen}{4 \ 5 \ 6}) \\
\binom{1 \ 2 \ 3 \ 4 \ \textcolor{limegreen}{5 \ 6} \ 7 \ 8 \ 9}{1 \ 2 \ 3 \ 4 \ \textcolor{blue}{9} \ \textcolor{red}{5} \ 8 \ 7 \ 6} & = \binom{1 \ 2 \ 3 \ 4 \ \textcolor{limegreen}{5 \ 6} \ 7 \ 8 \ 9}{1 \ 2 \ 3 \ 4 \ \textcolor{red}{5} \ \textcolor{blue}{9} \ 8 \ 7 \ 6} (\textcolor{limegreen}{5 \ 6}) \\
& \vdots \\
\binom{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ \textcolor{limegreen}{8 \ 9}}{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ \textcolor{blue}{9} \ \textcolor{red}{8}} & = \binom{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ \textcolor{limegreen}{8 \ 9}}{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ \textcolor{red}{8} \ \textcolor{blue}{9}}(\textcolor{limegreen}{8 \ 9}) \\[1ex]
\binom{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9}{2 \ 3 \ 9 \ 1 \ 5 \ 4 \ 8 \ 7 \ 6} & = (8 \ 9) \ldots (5 \ 6)(4 \ 5 \ 6)(1 \ 2 \ 3 \ 4)
\end{align*}
}\)
Cykle zaś rozpisujemy zgodnie z regułą
\(\displaystyle{ (1 \ 2 \ 3 \ 4) = (1 \ 2)(2 \ 3)(3 \ 4)}\).
\(\displaystyle{
\begin{align*}
\binom{\textcolor{limegreen}{1 \ 2 \ 3 \ 4} \ 5 \ 6 \ 7 \ 8 \ 9}{\textcolor{blue}{2 \ 3 \ 9} \ \textcolor{red}{1} \ 5 \ 4 \ 8 \ 7 \ 6} & = \binom{\textcolor{limegreen}{1 \ 2 \ 3 \ 4} \ 5 \ 6 \ 7 \ 8 \ 9}{\textcolor{red}{1} \ \textcolor{blue}{2 \ 3 \ 9} \ 5 \ 4 \ 8 \ 7 \ 6} (\textcolor{limegreen}{1 \ 2 \ 3 \ 4}) \\
\binom{1 \ 2 \ 3 \ \textcolor{limegreen}{4 \ 5 \ 6} \ 7 \ 8 \ 9}{1 \ 2 \ 3 \ \textcolor{blue}{9 \ 5} \ \textcolor{red}{4} \ 8 \ 7 \ 6} & = \binom{1 \ 2 \ 3 \ \textcolor{limegreen}{4 \ 5 \ 6} \ 7 \ 8 \ 9}{1 \ 2 \ 3 \ \textcolor{red}{4} \ \textcolor{blue}{9 \ 5} \ 8 \ 7 \ 6} (\textcolor{limegreen}{4 \ 5 \ 6}) \\
\binom{1 \ 2 \ 3 \ 4 \ \textcolor{limegreen}{5 \ 6} \ 7 \ 8 \ 9}{1 \ 2 \ 3 \ 4 \ \textcolor{blue}{9} \ \textcolor{red}{5} \ 8 \ 7 \ 6} & = \binom{1 \ 2 \ 3 \ 4 \ \textcolor{limegreen}{5 \ 6} \ 7 \ 8 \ 9}{1 \ 2 \ 3 \ 4 \ \textcolor{red}{5} \ \textcolor{blue}{9} \ 8 \ 7 \ 6} (\textcolor{limegreen}{5 \ 6}) \\
& \vdots \\
\binom{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ \textcolor{limegreen}{8 \ 9}}{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ \textcolor{blue}{9} \ \textcolor{red}{8}} & = \binom{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ \textcolor{limegreen}{8 \ 9}}{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ \textcolor{red}{8} \ \textcolor{blue}{9}}(\textcolor{limegreen}{8 \ 9}) \\[1ex]
\binom{1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9}{2 \ 3 \ 9 \ 1 \ 5 \ 4 \ 8 \ 7 \ 6} & = (8 \ 9) \ldots (5 \ 6)(4 \ 5 \ 6)(1 \ 2 \ 3 \ 4)
\end{align*}
}\)
Cykle zaś rozpisujemy zgodnie z regułą
\(\displaystyle{ (1 \ 2 \ 3 \ 4) = (1 \ 2)(2 \ 3)(3 \ 4)}\).