Sbírka matematických úloh

Počty permutací

Úloha číslo: 2452

• Nápověda

  Zvažte, jakými způsoby lze \((n-1)\)-prvkovou permutaci rozšířit na \(n\)-prvkovou.

• Řešení

  Celkem je na \(n\) prvcích \(n!\) permutací.

  Permutace s kladným znaménkem (sudé) tvoří podgrupu. Pro \(n\ge 2\) existují i permutace se záporným znaménkem (liché) a ty tvoří jedinou rozkladovou třídu odlišnou od této podgrupy.

  Nebo elementárně:

  Z permutace \(p\) na \(n-1\) prvcích lze vyvořit permutaci na \(n\) prvcích umístěním \(n\) na pvní, resp. druhou, atd. až na poslední \(n\)-tou pozici. V prvním případě přibude \(n-1\) inverzí, v druhém \(n-2\), atd. až v posledním případě nepřibude žádná inverze navíc. Tedy \(\lceil\frac{n}{2}\rceil\) nových permutací má stejné znaménko jako \(p\) a \(\lfloor\frac{n}{2}\rfloor\) má znaménko opačné. Tím je vyřešen případ pro sudé \(n\) - sudých i lichých permutací musí být stejně.

  Pro lichá \(n\ge 3\) musíme využit předpoklad o stejném počtu sudých a lichých permutací na \(n-1\) prvcích, což je konkrétně \(\frac{(n-1)!}{2}\).

  Potom sudých (resp. i lichých) je \( \frac{(n-1)!}{2}\lceil\frac{n}{2}\rceil+ \frac{(n-1)!}{2}\lfloor\frac{n}{2}\rfloor= \frac{n!}{2}\)
  

  Ještě alternativní elementární řešení v duchu podgrupy: Pro \(n \geq 2\) najdeme bijekci mezi sudými a lichými permutacemi. Jmenovitě permutaci \(p\) přiřadíme permutaci \(f(p) := p \circ (1{,}2)\). Protože znaménko transpozice \((1{,}2)\) je \(-1\), \(f\) převádí liché permutace na sudé a naopak. Navíc \(f(f(p)) = p\), z čehož už plyne, že \(f\) je bijekce mezi sudými a lichými permutacemi. (Ověřte si, že \(f\) je prostá a na.) Tedy sudých a lichých permutací je stejný počet.

• Výsledek

  Permutací s kladným i se záporným znaménkem je stejně, čili \(\frac{n!}{2}\) (pro \(n\ge 2\)).