Kombinatorika

Permutacija

Ključne reči: permutacija, sa ponavljanjem, sa ponavljanjem

Permutacija bez ponavljanja

Potrebno je n elemenata poređati na sve razičite načine (uređene n-torke).

Broj mogućih permutacija je:

P n = n · ( n 1 ) · ( n 2 ) · . . . · 2 · 1 = n !

Primer:

U slučaju poređenja 4 elemenata: {a,b,c,d} : n = 4 , P 4 = 4 ! = 4 · 3 · 2 · 1 = 24

abcd bacd cabd dabc
abdc badc cadb dacb
acbd bcad cbad dbac
acdb bcda cbda dbca
adbc bdac cdab dcab
adcb bdca cdba dcba

Permutacija sa ponavljanjem

Potrebno je poređati n elemenata na sve moguće načine od kojih ima identičnih. Broj elemenata koji se ponavljaju:

k 1 , k 2 , k 3 , . . . , k r ; ( k 1 + k 2 + k 3 + . . . + k r n )

Broj mogućih permutacija je:

P n k 1 , k 2 , k 3 , . . . , k r = n ! k 1 ! · k 2 ! · k 3 ! · . . . · k r !

Primer:

U slučaju 7 elemenata: {a,a,a,a,b,b,c}, vidimo da prvi element učestvuje 4 puta, dok drugi element učestvuje 2 puta: n=7, k1=4,k2=2, k1=1

Prema tome broj svih mogućih permutacija je: P74,2,1=7!4!·2!·1!=105