Permutacije

PERMUTACIJE

UVOD V UREJENE RAZPOREDITVE

Permutacije so temeljni pojem v kombinatoriki, ki opisujejo vse možne urejene razporeditve elementov dane množice. Pri permutacijah uporabimo vse elemente, njihova razporeditev pa je pomembna. Vsaka sprememba vrstnega reda pomeni drugo permutacijo, kar razlikuje permutacije od kombinacij, kjer vrstni red ni pomemben.

Če imamo n različnih elementov, je število vseh možnih permutacij teh elementov:

P(n) = n! (n fakulteta)
kjer je n! = n × (n – 1) × (n – 2) × … × 2 × 1

PRIMER 1: OSNOVNE PERMUTACIJE

Koliko različnih razporeditev črk A, B in C obstaja?

n = 3 → P(3) = 3! = 6

Permutacije: ABC, ACB, BAC, BCA, CAB, CBA

PERMUTACIJE Z ENAKIMI ELEMENTI

Če imamo v množici ponavljajoče se elemente, potem vsaka zamenjava enakih elementov ne ustvari nove permutacije. Takrat število permutacij zmanjšamo z deljenjem s fakultetami števila ponovitev:

Če imamo n elementov, od katerih:

• r₁ je prvih enakih,
• r₂ drugih enakih,
• …,
• rₖ k-tih enakih,

potem:

P(n; r₁, r₂, …, rₖ) = n! / (r₁! × r₂! × … × rₖ!)

PRIMER 2: PERMUTACIJE Z ENAKIMI ELEMENTI

Koliko različnih permutacij ima beseda MAMA?

Črke: M – 2×, A – 2× → n = 4, r₁ = 2, r₂ = 2

P = 4! / (2! × 2!) = 24 / (2 × 2) = 6

Permutacije: MAMA, MAAM, AMMA, AAMM, AMAM, MAAM

CIRKULARNE PERMUTACIJE

Če elemente razporedimo v krog, govorimo o krožnih (cirkularnih) permutacijah. V krogu se šteje, da rotacije ne pomenijo novih razporeditev.

Za n različnih elementov v krogu:

Pₖrog(n) = (n – 1)!

Primer: Razporeditev 5 oseb okrog mize → (5 – 1)! = 4! = 24 možnosti.

POVEZAVA Z VARIACIJAMI IN KOMBINACIJAMI

• Permutacije: vsi elementi, vrstni red je pomemben
• Variacije: del množice, vrstni red je pomemben
• Kombinacije: del množice, vrstni red ni pomemben

UPORABA PERMUTACIJ

Permutacije se uporabljajo pri:

• razporejanju oseb, predmetov, znakov,
• kodiranju in ustvarjanju gesel,
• premeščanju elementov brez ponavljanja,
• reševanju problemov v teoriji iger in optimizaciji.

ZAKLJUČEK

Permutacije predstavljajo vse možne načine razvrščanja elementov, kjer je vrstni red ključen. Število permutacij hitro narašča s številom elementov, še posebej kadar ni ponavljanj. Razumevanje osnovnih in posebnih oblik permutacij je bistveno za učinkovito reševanje kombinatoričnih problemov.