Permutacije Flashcards
Kaj so permutacije brez ponavljanja in koliko jih je?
O permutacijah govorimo, kadar razporejamo vse elemente dane končne množice v vrsto. Če so elementi dane množice med seboj različni, vsak od njih v posamezni permutacji nastopa natanko enkrat. Takim razporedbam rečemo permutacije brez ponavljanja.
Naj bo dana končana množica z n med seboj različni elementi a1,a2,a3… Razporedimo vse njegove elemente vi vrsto, npr. od leve proti enkrat. Na prvo mesto lahko postavimo katerega koli od n elementov, na drugo od preostalih (n - 1) in tako naseljujemo do zadnjega elementa, ki ga postavimo na n mesto.
Število permutacij je Pn = n!
Razporejanje elementov končne množice je bijektivna preslikava te množice nase.
Kaj so permutacije s ponavljanjem in koliko jih je?
V primerih, ko elementi dane množice niso vsi med seboj različni oz nekaterih elementov ne ločimo med seboj, govorimo o permuijah s ponavljanjem. Teh je manj kot permutacij brez ponavljanja, saj razporeba elementov predstavlja isto permutacijo, ko prerazporejamo enake elemente.
Naj bo iz n elementov med seboj enakih r1 enakih, r2 enakih … rk enakih ter r1 + r2 + rk ≤ n. Potem število permutacij n elementov s ponavljanjem izračunamo: Pn^r1,r2,rk = n!/ r1!r2!rk!
