Znaménko inverzní premutace

Úloha číslo: 2445

Ukažte čtyřmi způsoby, proč má inverzní permutace \(p^{-1}\) stejné znaménko jako původní permutace \(p\)?

  • Nápověda

    Uvažte cykly, počet inverzí, rozklad na transpozice a zachování znaménka při skládání.

  • Řešení

    Permutace \(p\) a \(p^{-1}\) mají stejné délky cyklů (a na stejných prvvcích), protože permutace \(p^{-1}\) vznikne z \(p\) otočením šipek v grafu cyklů.

    Permutace \(p\) a \(p^{-1}\) mají stejný počet inverzí, protože v bipartitním grafu permutace zůstanou křížení nezměněna pokud otočíme směr šipek.

    Je-li \(p=t_1\circ t_2\circ…\circ t_k\) rozklad \(p\) na transpozice, pak \(p^{-1}=t_k\circ t_{k-1}\circ…\circ t_1\). Snadno ověříme, že složením získáme identitu.

    Z rovnice \(sgn(p)\cdot sgn(p^{-1})=sgn(p\circ p^{-1})=sgn(\imath)=1\) plyne okamžitě, že \(sgn(p)= sgn(p^{-1})\).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze