Permutacije bez ponavljanja
- Autor:
- Vesna Josipović
- Tema:
- Kombinatorika
Primjer 1.
Ante želi na policu staviti ove tri knjige: Volim matematiku, Nogometna matematika i fizika, Mali princ.
Na koliko načina to može napraviti?
Rj. Ante može prvu knjigu odabrati na 3 načina.
Nakon toga, preostale su mu još 2 knjige pa drugu može odabrati na 2 načina.
Na kraju, na treće mjesto stavlja preostalu knjigu (1 način).
Dakle, prema principu umnoška postoji načina slaganja tih knjiga.
_ _ _
Označimo knjige: M - Volim matematiku, N - Nogometna matematika i fizika, P - Mali princ
i ispišimo sve načine slaganja:
M N P N M P P M N
M P N N P M P N M
Neka je S = { } skup koji ima 3 elemenata. Svaka uređena trojka različitih elemenata iz skupa S
naziva se permutacija skupa S.
Skup može imati i više elemenata pa govorimo o petorkama, šestorkama, ... općenito n-torkama.
Ako su elementi skupa S različiti često se koristi i naziv permuacije bez ponavljanja.
Zapamtimo:
Sve elemente skupa S razmještamo na sve moguće načine , pri čemu je bitan poredak elemenata.
Faktorijeli
Umnožak prvih n prirodnih brojeva označavamo n! i čitamo "en faktorijela".
1!=1, 2!=, 3!=, 4!=, 5!=, ...
Po definiciji stavljamo 0!=1.
Vrijedi formula: n! = n (n-1)!
Npr. 5!=54!, 5!=543!, 7!=76!=7654!
Broj svih permutacija skupa od n elemenata jednak je
Primjer 2.
Neka je zadan skup S={ 0,2,4,6,8 }.
a) Koliko postoji permutacija skupa S?
b) Koliko permutacija skupa S završava sa 6?
c) Koliko permutacija skupa S ne završava sa 6?
Rj.
a) Skup S ima 5 elemenata i broj svih permutacija jednak je 120.
b) Tražene permutacije su oblika _ _ _ _ 6
Na prva 4 mjesta možemo rasporediti preostale elemente 0,2,4,8 na 4!=24 načina.
c) Broj permutacija skupa S koje ne završavaju sa 6 možemo dobiti tako da
od ukupnog broja permutacija oduzmemo one permutacije koje počinju sa 6,
a njih ima (rj. a) - rj. b)): 120 - 24 =96