Lineární algebra

Tvrzení naší věty je: „počet různých permutací n prvků je roven číslu n!ÿ. Dokážeme v prvním

kroku pro n = 1, tj. „počet různých permutací jednoho prvku je roven číslu 1! = 1ÿ. O tom ale asi nikdo
nepochybuje, nelze totiž vytvořit nic jiného než permutaci (1).

Nyní dokážeme indukční krok. Předpokládáme tedy, že počet různých permutací n prvků je roven

číslu n! a dokážeme, že počet různých permutací n+1 prvků je roven číslu (n+1)! . Prozkoumejme nejprve,
kolik existuje permutací n + 1 prvků, které mají v první složce zapsáno číslo 1. Je jich n!, protože zbylých
n složek můžeme zaplnit čísly {2, 3, . . . , n, n + 1} a máme v tomto případě stejné množství možností,
jako je počet permutací n prvků. Těch je podle indukčního předpokladu n! . Ze stejného důvodu existuje
n! různých permutací n + 1 prvků, které mají v první složce zapsáno číslo 2. Totéž platí pro čísla
3, 4, . . . , n, n + 1 v první složce permutace. Existuje tedy (n + 1) · n! = (n + 1)! různých permutací n + 1
prvků.

4.4. Příklad. Uvedeme si všechny permutace tří prvků. Podle věty 4.3 je jejich počet roven šesti. Hledané
permutace jsou:

(1, 2, 3),

(1, 3, 2),

(2, 1, 3),

(2, 3, 1),

(3, 1, 2),

(3, 2, 1).

Zkusíme ještě zapsat všechny permutace čtyř prvků. Je jich 24.

(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3),

(2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 2, 1, 4), (3, 2, 4, 1), (3, 1, 2, 4), (3, 1, 4, 2),

(3, 4, 2, 1), (3, 4, 1, 2), (4, 2, 3, 1), (4, 2, 1, 3), (4, 3, 2, 1), (4, 3, 1, 2), (4, 1, 2, 3), (4, 1, 3, 2).