Rozklad pomocí transpozic (1,i)
Úloha číslo: 2446
Ukažte, že každou permutaci na \(n\) prvcích, lze rozložit na transpozice typu \((1,i)\) pro \(i \in \{2,…, n\}\).
Pokuste se omezit délku výsledného rozkladu.
Nápověda
Odvoďte a použijte vztah \((a,b)=(c,a)(c,b)(c,a)\).
Řešení
Rozložíme permutaci na cykly.
Cyklus, v němž se vyskytuje 1, např. \((1,a,b,c,…)\) rozložíme \((1,a,b,c,…)=(1,a)(1,b)(1,c)…\)
Ostatní cykly např. \((a,b,c,…)\) nejprve rozložíme \((a,b,c,…)=(a,b)(a,c)…\) Každou transpozici rozložíme \((a,b)=(1,a)(1,b)(1,a)\), tedy \((a,b)(a,c)…=(1,a)(1,b)(1,a)(1,a)(1,c)(1,a)…\) Po eliminaci sousedících dvojic \((1,a)(1,a)\) dostaneme výsledný rozklad \((1,a)(1,b)(1,c)…(1,a)\).
Délka rozkladu je omezena výrazem \(\frac{2n-1}{3}=1+\frac{2}{3}(n-2)\), který se nabývá tehdy, když je daná permutace složena ze samých dvoucyklů neboli z transpozic na disjunktních dvojicích.
