Sbírka matematických úloh

Základní vlastnosti

Úloha číslo: 2444

• Varianta 1

  \(p=(6\ 4\ 1\ 5\ 3\ 2)\), \(q=(6\ 4\ 3\ 2\ 5\ 1)\).

• Nápověda

  Inverze jsou takové páry čísel \(i,j\) kde \(j\) je v permutaci před \(i\) a navíc \(j>i\).

  Mnemotechnický výpočet počtu inverzí ze zápisu permutace \((p(1)\ p(2)\ \cdots \ p(n))\) – pro každé \(j\) započti všechna čísla, která jsou v zápisu před \(p(j)\), t.j. mezi prvními \(j-1\) čísly, a jsou větší než \(p(j)\).

  Složení permutací \(q\circ p\) má znaménko \(sgn(p)sgn(q)\) – dá se snadno nahlédnout přes počet křížení (dvě křížení se mohou eliminovat).

  Transpozice \((i,j)\) dá za vznik \(2(j-i-1)+1\) inverzím, tedy právě změní znaménko.

  Pro rozklad cyklu na transpozice využijeme pravidla: \((i_1,…,i_k)=(i_1,i_2)\circ(i_2,…,i_k)\) popř. \((i_1,…,i_k)=(i_1,i_k)\circ(i_1,…,i_{k-1})\).

  Znaménko permutace je tedy rovno paritě počtu inverzí nebo paritě počtu transpozicí z libovolného rozkladu (rozklad není jednoznačný) nebo též paritě počtu sudých cyklů.

  Inverze se najde mnemotechnicky: na kterém místě v permutaci je \(i\)?

• Řešení

  \(q\circ p=(1\ 2\ 6\ 5\ 3\ 4)\), \(p\circ q=(2\ 5\ 1\ 4\ 3\ 6)\)

  Permutace \(p\) má 11 inverzí: \((1{,}2),(1{,}3),(1{,}4),(1{,}5),(1{,}6),\) \((2{,}3),(2{,}5),(2{,}6),\) \((4{,}5),(4{,}6),(5{,}6)\), viz např. z grafu křížení.

  \(q\) má 12 inverzí, obě složené permutace \(q\circ p\) i \(p\circ q\) mají 5 inverzí.

  Cyklický zápis \(p=(1{,}6,2{,}4,5{,}3)\), \(q=(1{,}6)(2{,}4)(3)(5)\),
  \(q\circ p=(1)(2)(3{,}6,4{,}5)\), \(q\circ p=(1{,}2,5{,}3)(4)(6)\)

  Rozklad na transpozice: \(p=(1{,}6)\circ(6{,}2)\circ(2{,}4)\circ(4{,}5)\circ(5{,}3)\), \(q=(1{,}6)\circ(2{,}4)\), \(q\circ p=(3{,}6)\circ(6{,}4)\circ(4{,}5)\), \(p\circ q=(1{,}2)\circ(2{,}5)\circ(5{,}3)\).

  Znaménka jsou po řadě \(-1,+1,-1\) a \(-1\).

  Inverzní permutace jsou \(p^{-1}=(3\ 6\ 5\ 2\ 4\ 1)\), \(q^{-1}=(6\ 4\ 3\ 2\ 5\ 1)\), \((q\circ p)^{-1}=(1\ 2\ 5\ 6\ 4\ 3)\), \((p\circ q)^{-1}=(3\ 1\ 5\ 4\ 2\ 6)\).

• Varianta 2

  \(p=(1\ 2\ 7\ 6\ 5\ 4\ 3\ 8\ 9)\), \(q=(1\ 3\ 5\ 7\ 9\ 8\ 6\ 4\ 2)\).

• Výsledek

  \(p\): \(p^{-1}=(1\ 2\ 7\ 6\ 5\ 4\ 3\ 8\ 9)\)
  10 inverzí, cykly \((1)(2)(3{,}7)(4{,}6)(5)(8)(9)\), 2 transpozice \((3{,}7)\circ(4{,}6)\), znaménko \(+1\),

  \(q\): \(q^{-1}=(1\ 9\ 2\ 8\ 3\ 7\ 4\ 6\ 5)\)
  16 inverzí, cykly \((1)(2{,}3,5{,}9)(4{,}7,6{,}8)\), 6 transpozic, znaménko \(+1\),

  \(q\circ p=(1\ 3\ 6\ 8\ 9\ 7\ 5\ 4\ 2)\): \((q\circ p)^{-1}=(1\ 9\ 2\ 8\ 7\ 3\ 6\ 4\ 5)\)
  18 inverzí, cykly \((1)(2{,}3,6{,}7,5{,}9)(4{,}8)\), 6 transpozic, znaménko \(+1\),

  \(p\circ q=(1\ 7\ 5\ 3\ 9\ 8\ 4\ 6\ 2)\): \((p\circ q)^{-1}=(1\ 9\ 4\ 7\ 3\ 8\ 2\ 6\ 5)\)
  18 inverzí, cykly \((1)(2{,}7,4{,}3,5{,}9)(6{,}8)\), 6 transpozic, znaménko \(+1\).

• Varianta 3

  \(p=(5\ 4\ 3\ 2\ 1\ 9\ 8\ 7\ 6)\), \(q=(8\ 6\ 4\ 2\ 1\ 3\ 5\ 7\ 9)\).

• Výsledek

  \(p\): \(p^{-1}=(5\ 4\ 3\ 2\ 1\ 9\ 8\ 7\ 6)\),
  16 inverzí, cykly \((1{,}5)(2{,}4)(3)(6{,}9)(7{,}8)\), 4 transpozice, znaménko \(+1\),

  \(q\): \(q^{-1}=(5\ 4\ 6\ 3\ 7\ 2\ 8\ 1\ 9)\),
  16 inverzí, cykly \((1{,}8,7{,}5)(2{,}6,3{,}4)(9)\), 6 transpozic, znaménko \(+1\),

  \(q\circ p=(1\ 2\ 4\ 6\ 8\ 9\ 7\ 5\ 3)\), \((q\circ p)^{-1}=(1\ 2\ 9\ 3\ 8\ 4\ 7\ 5\ 6)\)
  12 inverzí, cykly \((1)(2)(3{,}4,6{,}9)(5{,}8)(7)\), 4 transpozice, znaménko \(+1\),

  \(p\circ q=(7\ 9\ 2\ 4\ 5\ 3\ 1\ 8\ 6)\), \((p\circ q)^{-1}=(7\ 3\ 6\ 4\ 5\ 9\ 1\ 8\ 2)\)
  20 inverzí, cykly \((1{,}7)(2{,}9,6{,}3)(4)(5)(8)\), 4 transpozice, znaménko \(+1\).

• Varianta 4

  \(p=(3\ 6\ 9\ 2\ 5\ 8\ 1\ 4\ 7)\), \(q=(9\ 8\ 7\ 6\ 5\ 4\ 3\ 2\ 1)\).

• Výsledek

  \(p\): \(p^{-1}=(7\ 4\ 1\ 8\ 5\ 2\ 9\ 6\ 3)\),
  18 inverzí, cykly \((1{,}3,9{,}7)(2{,}6,8{,}4)(5)\), 6 transpozic, znaménko \(+1\),

  \(q\): \(q^{-1}=(9\ 8\ 7\ 6\ 5\ 4\ 3\ 2\ 1)\),
  36 inverzí, cykly \((1{,}9)(2{,}8)(3{,}7)(4{,}6)(5)\), 4 transpozice, znaménko \(+1\),

  \(q\circ p=(7\ 4\ 1\ 8\ 5\ 2\ 9\ 6\ 3)\), \((q\circ p)^{-1}=(3\ 6\ 9\ 2\ 5\ 8\ 1\ 4\ 6)\)
  18 inverzí, cykly \((1{,}7,9{,}3)(2{,}4,8{,}6)(5)\), 6 transpozic, znaménko \(+1\),

  \(p\circ q=(7\ 4\ 1\ 8\ 5\ 2\ 9\ 6\ 3)\), \((p\circ q)^{-1}=(3\ 6\ 9\ 2\ 5\ 8\ 1\ 4\ 6)\)
  18 inverzí, cykly \((1{,}7,9{,}3)(2{,}4,8{,}6)(5)\), 6 transpozic, znaménko \(+1\),

  Všímněte si, že \(q\circ p=p\circ q\).