Permutace devětkrát jinak

Úkol:

  1. Kolik nejvíc inverzí může být v permutaci množiny o $ n$ prvcích?
  2. Stačí $ n-1$ transpozic na vytvoření libovolné permutace na $ n$ prvcích?
  3. Jaký je horní odhad složitosti bublinkového třídění?
  4. Znám počet inverzí v permutaci $ a_1,a_2,\ldots,a_n$. Kolik je inverzí v permutaci $ a_n,a_{n-1},\ldots,a_1$?
  5. Kolik je inverzí ve všech permutacích na $ n$ prvcích dohromady?
  6. Kolik nejméně transpozic sousedních prvků je třeba k převedení permutace o $ k$ inverzích na tvar $ 1,2,\ldots,n$?
  7. Označme $ [n,k]$ počet permutací na $ n$ prvcích, které obsahují právě $ k$ inverzí. Odvoďte rekurentní relaci

    $\displaystyle [n+1,k] = [n,k] + [n,k-1] + [n,k-2] + \ldots + [n,k-n]\,,$

    přičemž dodefinujeme $ [n,j]=0$ pro $ j$ mimo rozmezí 0 $ \frac{1}{2}n(n-1)$.
  8. Mějme permutaci

    $\displaystyle A=\left(\begin{array}{ccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & ...
...\\ 3 & 8 & 11 & 9 & 13 & 2 & 6 & 12 & 5 & 10 & 1 & 7 & 4 \\ \end{array}\right).$ (11)

    Spočtěte $ A^{111}$. Pro jaké mocniny je $ A^n$ identická permutace? Určete znak $ A$ a $ A^{111}$.
  9. Za jakých podmínek existuje druhá odmocnina z permutace? Kolik jich existuje?


Řešení:


1. Protože inverze je taková dvojice $ i<j$, pro niž je $ p(i)>p(j)$, bude nejvíc inverzí zřejmě v permutaci $ n,n-1,\ldots,2,1$. Tam jsou v inverzi každé dva prvky, proto celkový počet inverzí je $ \frac{1}{2}n(n-1)$.


2. Stačí. Víme, že každou permutaci lze složit z jednoho či více cyklů. Cyklus na $ k$ prvcích se dostane složením $ k-1$ transpozic $ (a_1,a_2),\allowbreak(a_2,a_3),\ldots,
(a_{k-1},a_{k})$. Permutace, skládající se z jediného cyklu, spotřebuje $ n-1$ transpozic, za každý další cyklus se odpočítá jednička. Je zřejmé, že méně transpozic obecně nestačí.


3. Bublinkové třídění spočívá v prohazování sousedních prvků, jinými slovy se tedy ptáme na maximální počet transpozic sousedních prvků, které jsou potřeba k sestavení libovolné permutace. Během prvního průchodu algoritmu se dostane určitě $ n$ na poslední místo, protože je větší než všechno a prohazujeme jej tudíž vždycky. Potřebujeme k tomu $ n-1$ porovnávání. Při druhém průchodu algoritmu tedy stačí jen $ n-2$ porovnávání, ve třetím $ n-3$, atd. celkem $ \frac{1}{2}n(n-1)$ porovnávání. Nejhorší, co se může stát, je, že po každém porovnávání musíme také prohazovat, to nastane v případě permutace $ n,n-1,\ldots,2,1$. Tedy horní odhad časové složitosti algoritmu je $ \frac{1}{2}Kn(n-1)$, kde $ K$ je čas potřebný na porovnání a prohození dvou prvků.


4. Při přechodu k druhé permutaci se obrací pořadí všech prvků, tedy jestliže nejprve jsme měli $ k$ inverzí, po obrácení jich bude $ \frac{1}{2}
n(n-1) -k$.


5. Sestavíme všech $ n!$ permutací do dvojic, v nichž permutaci $ a_1,a_2,\ldots,a_n$ je přiřazena obrácená permutace $ a_n,a_{n-1},\ldots,a_1$. V každé dvojici je $ \frac{1}{2}n(n-1)$ inverzí (viz předchozí otázku), tedy celkový počet inverzí ve všech dvojicích je $ \frac{1}{2} n!
\cdot\frac{1}{2}n(n-1)$


6. Také $ k$. Stačí si uvědomit, že každý krok bublinkového třídění likviduje právě jednu inverzi a že bublinkové třídění je, co se počtu transpozic sousedů týče, nejúspornější možné.


7. Jakými způsoby lze realizovat $ (n+1)$-prvkovou permutaci s $ k$ inverzemi? První člen na pravé straně dokazované relace odpovídá umístění prvku $ n+1$ na konec libovolné $ n$-prvkové permutace o $ k$ inverzích (v této poloze není $ n+1$ v inverzi s ničím) a $ k$ inverzím na zbylých prvcích. Druhý člen klade $ n+1$ na předposlední místo, čímž generuje jednu inverzi a na zbylých $ n$ prvků zbývá $ k-1$ inverzí, atd. Poslední člen odpovídá situaci, kdy je $ n+1$ obrazem jedničky a je tak v inverzi se všemi zbylými $ n$ prvky.

Obrázek: Rozklad permutace $ A$ (viz 11) na cykly délek 3,5,4,1.
=1mm \includegraphics[scale=0.7]{OBRAZKY/permutace.eps} (-104,16)1 (-91,16)3 (-99,5)11 (-71,0)2 (-59,0)8 (-76,11)6 (-55,11)12 (-65,21)7 (-37,4)4 (-25,4)9 (-38,17)13 (-26,17)5 (-6.5,12)10


8. Rozložíme permutaci na cykly $ (1,3,11);\allowbreak\,
(2,8,12,7,6);\allowbreak\,(10);\allowbreak\,(4,9,5,13)$, viz obrázek 5. Jelikož tato permutace obsahuje jeden cyklus sudé délky, je to lichá permutace. Ostatní metody určování znaménka (počítání transpozic či inverzí) by zde byly pracnější.

Mocnění permutace pouze točí s cykly, nanejvýš je může roztrhnout, pokud je počet prvků v cyklu soudělný s exponentem. V opačném případě zbytek po dělení počtu prvků v cyklu exponentem udává, o kolik se tento cyklus pootočí. V našem konkrétním případě je to $ 0,1,3,0$, výsledná permutace je kompozicí cyklů $ (1);(3);(11);(2,8,12,7,6); (4,13,5,9);(10)$. Znaménko této permutace je opět minus, což jsme ostatně již věděli díky $ \mathop{\rm zn}\nolimits A^n=(\mathop{\rm zn}\nolimits A)^n$ (viz příklad 2.8).

Zjevně identitu dostaneme pro libovolný společný násobek délek cyklů, tedy $ n=60k$, kde $ k$ je libovolné přirozené. Upozorňujeme, že $ A^n=\mathop{{\rm Id}}$ je něco jiného než $ A^n=A$. Druhá rovnice je splněna pro $ n=60k+1$.


9. Každý cyklus délky $ 2n$ se po umocnění na druhou rozpadne na dva cykly délky8$ n$. Cykly délky $ 2n-1$ se mocněním převádějí opět na cykly délky $ 2n-1$. Tedy pokud máme v zadané permutaci nějaký cyklus sudé délky, musel nutně vzniknout umocněním cyklu dvojnásobné délky. Tudíž takové permutace, které obsahují pro některé sudé $ k$ lichý počet cyklů délky $ k$, druhou odmocninu nemají. K ostatním permutacím odmocninu najdeme vždycky, jednoznačně pouze za předpokladu, že pro lichá $ k$ máme nejvýše jeden cyklus délky $ k$ a pro sudá $ k$ žádný9, protože každé slévání cyklů delších než jedna lze provést více způsoby.

Pro permutaci rozloženou na $ N$ disjunktních lichých cyklů délky $ n$ lze celkový počet odmocnin nalézt následující úvahou: počet permutací na $ N$ prvcích je $ N!$. Za pozice $ 0,2,4,, \ldots, N'$, kde $ N'$ je nejvyšší sudé číslo menší nebo rovno $ N$, lze vsunout zarážku, která odděluje cykly, které budeme slévat do dvojic, od cyklů, které neslejeme. Slévat budeme vždy cykly, které se ocitnou na místech (1,2),(3,4) atd.; z nich můžeme slít celkem $ k=0,1,\ldots, \frac{1}{2}N'$ dvojic a zbylých $ N-2k$ dvojic cyklů neslít. Pro každé $ k$ zvlášť pak musíme $ N!$ vydělit permutacemi slévaných dvojic, kterých je $ k!$, kde $ 2k$ je pozice zarážky. Dále musíme vydělit $ (N-2k)!$, což odpovídá permutacím na neslévaných cyklech (za zarážkou), a pak ještě $ 2^k$, protože v každé dvojici lze vyměnit její členy mezi sebou. Nakonec musíme ještě vynásobit počtem způsobů, kolika lze slít dva cykly.

Umocnit dlouhý cyklus na druhou vlastně znamená oddělit členy na lichých pozicích od členů na sudých. Slévání tedy můžeme chápat jako vložení jednoho cyklu do mezer mezi členy druhého cyklu tak, že v každé mezeře sídlí právě jedno číslo a zachovává se pořadí. Takových vložení je zjevně tolik, kolik je délka slévaných cyklů. Celkový výraz pro počet odmocnin permutace, která obsahuje $ N$ cyklů liché délky $ n$, je tedy

$\displaystyle \sum_{k=0}^{\lfloor \frac{N}{2} \rfloor} \left(\frac{n}{2} \right)^k
\frac{N!}{k!(N-2k)!}\,, $

$ \lfloor\frac{N}{2}\rfloor$ označuje celou část čísla $ \frac{N}{2}$ (tedy $ \frac{N'}{2}$). Pro případ sudých cyklů nemáme na výběr, zda slévat, či neslévat, což situaci výrazně zjednoduší. Odvoláme-li se na představu použitou u lichých cyklů, smíme tentokrát dát zarážku pouze na konec a vzorec pro počet odmocnin je

$\displaystyle \left(\frac{n}{2} \right)^k \frac{(2k)!}{k!}\,,$    kde $\displaystyle k=\frac{N}{2}\,.$

Počet odmocnin obecné permutace, v jejímž rozkladu jsou cykly různých délek, se dostane prostým součinem. Čtenář si může rozmyslet, jak by se řešila $ s$-tá odmocnina -- v prvočíselném případě se bude výsledek podobat vzorcům pro $ s=2$, neboť bude docházet pouze ke slévání $ s$ cyklů dohromady, pro $ s$ složené se bude moci slévat i $ r$ cyklů, kde $ r$ je nějaký dělitel $ s$. Způsobů slévání bude $ (r-1)!n^{r-1}$, protože $ r-1$ cyklů lze do mezer ukládat v libovolném pořadí a každý lze $ n$ způsoby pootočit.

$ \ast$$ \ast$