Kombinatorika

Poradia (pertmutácie)

Definícia
Poradie je usporiadaná n-tica navzájom rôznych prvkov množiny M. Počet všetkých poradí prvkov n-prvkovej množiny M označujeme P(n). I. v rade vyberám z n, 2. už len z n-1, predposledného z 2, posledného z 1 a počet všetkých poradí n-prvkovej množiny je n*(n-1)*(n-2)*...2*1 = n!

Dôkaz: Matematickou indukciou.
Pre n=1 to platí. Predpokladajme, že P(n) = n!. Ako z n-prvkových poradí dostaneme všetky poradie po pridaní (n+1). prvku? Pre každé poradie môžem ten nový prvok dať na (n+1) miest. Teda P(n+1) = (n+1)P(n)= (n+l)n! = (n+1)!