Kaj je permutacija?

Permutacija je ena od tem, obravnavanih v disciplini kombinatorna analiza v matematiki. Če imamo v roki poljubno urejeno zaporedje z "n" številom ločenih elementov, se vsako drugo zaporedje, ki ga tvorijo isti "n" preurejeni elementi, imenuje permutacija.

Tako lahko rečemo, da če sta A permutacija B, sta A in B sestavljeni iz istih elementov, vendar različno urejeni.

Od kod prihajajo permutacije?

Permutacije so osamljeni primeri Preprosti dogovori. To so urejene skupine množice elementov A, tako da imajo skupine manj ali enako število elementov kot množica A.

Niz A = {X, Y, Z}, {X, Y} in {Y, X} je a preprost dogovor elementov iz A vzetih 2 do 2. Število elementov A je predstavljeno s črko "n". O številka naročila, ali številka razreda, je "k". To število je število elementov v vsakem preprostem polju (v primeru je to število 2).

Seznam z vsemi preprostimi ureditvami treh elementov A iz 3 do 3 je naslednji:

XYZ, XZY, ZXY, ZYX, YZX in YXZ

Ta seznam je ravno poseben primer dogovorov, ki dobijo ime permutacije.

Izračun enostavnih dogovorov

Število preprostih razporeditev niza A, ki ima št sprejeti elementi k The oh, lahko izračunamo po naslednji formuli:

THE_{ne, ok} = ne!
(n - k)!

Opredelitev permutacije

Naj bo A niz z št ločeni elementi. Ti preprosti dogovori od teh elementov, vzetih n do n, se imenujejo preproste permutacije od A. Da bi šlo za permutacijo, mora biti številka naročila k biti enako številu št elementov A. Iz tega izhajajo naslednji izračuni:

Če vzamemo formulo, ki se uporablja za preproste nize, in zaporedno številko k = n, bomo imeli:

To je formula, ki se uporablja za izračun števila permutacij elementov množice A, običajno označenih s P_št. Kmalu:

Ne ustavi se zdaj... Po oglaševanju je še več;)

P_št = A_{ne, ne} = n!

P_št = n!

Primer

Izračunajte število permutacij črk besede LJUBEZEN.

Rešitev:

Upoštevajte, da ima beseda LJUBEZEN 4 različne elemente. Za izračun števila permutacij te besede bomo uporabili zgornjo formulo:

P_št = n!

P₄ = 4!

P₄ = 4·3·2·1

P₄ = 24

Zato je mogoče oblikovati 24 različnih permutacij črk besede LJUBEZEN. Imenujejo se tudi besedne permutacije anagrami.

Permutacije s ponavljajočimi se elementi

Vsak niz ima lahko ponavljajoče se elemente. Ob permutacije ta niz bi moral upoštevati ponavljanje teh elementov, ker vrstni red, v katerem se pojavljajo, ni pomemben, za razliko od vrstnega reda drugih elementov niza. Če v besedi AMAR spremenimo samo dve »A« na mestu, bomo dobili isto besedo. Podobne besede niso permutacijezato je treba to ponovitev odšteti v formuli za permutacije.

Da odštejemo vse možne ponovitve elementov v enem permutacija s ponavljajočimi se elementi, narediti moramo naslednje:

Naj bo A niz z št elementi, od katerih k elementi se ponavljajo. Formula za izračun permutacij A je:

P_št^k = ne!
k!

Če je nastavljeno A, z št elementi, posedovati k ponovitve elementa in j ponovitev drugega, se bo izračun izvedel na naslednji način:

P_št^haha =  ne!
k! · j!

Če je niz A, z št elementov, ima k ponovitve elementa, j ponovitve drugega,..., m ponovitev druge formule ima naslednjo obliko:

P_št^{k, j,..., m} =  ne!
k! · j! ·... · M!

Primer

Izračunaj število anagramov besede ANTONIA.

Rešitev:

Za rešitev primera samo izračunajte permutacije s ponavljajočimi se elementi besede ANTONIA. Tako črko A kot črko N ponovimo 2-krat. Pazi:

P₇^2,2 =  7!
2!·2!

P₇^2,2 = 7·6·5·4·3·2·1
2·1·2·1

P₇^2,2 = 5040
4

P₇^2,2 = 1260

Avtor Luiz Paulo Moreira
Diplomiral iz matematike