Permutatsioonid ja faktoriaal

Permutatsioon

Permutatsioon on lihtsalt mingite fikseeritud objektide kindel ülesrivistus. Näiteks on jalgpallimeeskonna täpne reastus hümni laulmise aegu üks võimalik põhikoosseisu permutatsioon. Samuti on permutatsioon nelja tinasõduri ülesrivistus aknalaual ning kõikvõimalikud laused, mida võib moodustada kolme sõnaga – mulle, meeldib, matemaatika.

Põhiliselt huvitab meid siin peatükis permutatsioonide arv, mida n objekti korral tähistatakse Pn. Muidugi ei ole siin objektide enda täpne olemus oluline – meil on sama palju reastusi 10-st tinasõdurist kui 10-st tõsisest kaitseväelasest.

Permutatsioonide arv

Kui palju lauseid võib moodustada kolme sõnaga mulle, meeldib, matemaatika? Rõõmuks ja motivatsiooniks paneme nad esiteks muidugi kirja:

Mulle meeldib matemaatika.

Mulle matemaatika meeldib.

Meeldib mulle matemaatika.

Meeldib matemaatika mulle.

Matemaatika mulle meeldib.

Matemaatika meeldib mulle.

Neid lauseid on seega täpselt kuus. Eesti keel on vahva, kuna paljudes teistes keeltes ei oleks kõik toodud kuus lausest grammatiliselt võimalikud, meil aga teatud mööndustega on.

Siiski oleks olnud ilmselt meeldivam, kui ei oleks pidanud kõiki lauseid loetlema ning oleksime võinud kohe mõne valemi abil öelda, palju erinevaid lauseid leidub.

Kuidas sellist valemit leida?

  • Märkame, et esimese sõna valikuks on meil kolm võimalust: mulle, meeldib või matemaatika.
  • Kui oleme esimese sõna valinud, jääb täpselt kaks võimalust teise sõna valikuks.
  • Kui aga teinegi sõna on valitud, võime kolmanda sinna vaid lõppu visata.

Esimesel sammul oli meil 3 võimalust, teisel 2 ja kolmandal ainult 1 võimalus. Kuna kõik valikud on üksteisest sõltumatud, on võimalusi kokku täpselt 3 · 2 · 1 = 6.

Oleks meil neli sõna, ei oleks kõik moodustatavad laused ilmselt enam grammatiliselt korrektsed, ent sarnase arutelu kaudu näeksime siiski, et moodustada on võimalik 4 · 3 · 2 · 1 = 24 erinevat lauset.

Sama  mõttemustrit edasi viies näeme, et sõna jaoks oleks lausete arv n · (n – 1) · … 3 · 2 · 1 ehk teisisõnu

figury61

Faktoriaal

 

Selgub, et järjestikuste arvude korrutamine on nii mõnus ja nii tihti ettetulev tegevus, et sellele tasub ka päris oma tähistus anda.

Nii tähistabki 10-faktoriaal esimese kümne positiivse täisarvu korrutist 1 · 2 · … · 10 ning n-faktoriaal seega korrutist 1 · 2 · … ·(n – 1) · n. Kuni 19. sajandini tähistati n-faktoriaali sümboliga

figury62

Varsti leidis õnneks esteetilise tunnetusega prantsuse matemaatik Christian Kramp, et tegemist ei ole teab mis kena sümboliga, ning tõi kasutusele tänapäevase tähistuse: n!.

Nagu äsja lugesime, ongi n objekti permutatsioonide arv täpselt võrdne n-faktoriaaliga ehk, kuna matemaatikud sümbolitega ei priiska:

figury63

 

Faktoriaali kasv*

 

Faktoriaali juures on muljet avaldav tema kasvukiirus. Kui hakkame järjest faktoriaali välja arvutama, oleme varsti pigis – taskuarvuti ütleb üles!

Juba 20! annab meile arvu 2 432 902 008176 640 000. Kui faktoriaali meile juba tuntud funktsioonidega võrrelda, siis faktoriaal kasvab kiiremini kui ükskõik milline polünoom [lk 266] ja isegi kiiremini kui ükskõik milline eksponentsiaalfunktsioon [lk 280].

Eks lihtsaim viis ülevaate saamiseks on ikka oma silmaga mõnd näidet uurida. Jälgi, kuidas kolm erinevat funktsiooni (lilla on polünoom, tumesinine eksponentsiaalfunktsioon ning helesinine faktoriaal) kasvavad:

Faktoriaal kihutab juba üsna varakult polünoomist mööda ja veidi hiljem möödub ka eksponentsiaalfunktsioonist. Kui ainult pilt pole veel piisavalt veenev, siis võib lugeda ka järgnevat selgitust, mis küll rangele matemaatilisele täpsusele ei pretendeeri.

Märkame, et …

  1. Polünoomi y = x10 kasvust võime mõelda järgmiselt: kui tema argumenti (muutuja xväärtust) 2 korda suurendame, siis funktsioon kasvab 210 korda.
  2. Eksponentsiaalfunktsiooni y = 10x kasvust võime mõelda järgmiselt: kui tema argumenti ehk x-isuurendada 2 korda, siis on see võrdväärne funktsiooni ruutu tõstmisega.

Kumb neist kasvab kiiremini? Mõtleme juhule, kui meil on argumendiks väga suur arv, näiteks 350.

Selle argumendi väärtuse kahekordistamisel suureneb polünoomfunktsioon ainult 210 korda, eksponentsiaalfunktsioon aga tervelt 350 korda – seega kasvab eksponentsiaalfunktsioon vähemalt selles vahemikus palju kiiremini. Kiire mõtisklus näitab, et küllap ta siis rebib varem või hiljem ette.

Aga mida tähendab faktoriaali jaoks argumendi kahekordistamine?

Arvust m! saab (2m)! ja seega argumendi 350 jaoks saame argumendi kahekordistamisel algse faktoriaali 350! asemele faktoriaali (2 · 350). See tähendab, et korrutame kokku 2 · 350 esimest naturaalarvu.

Seega faktoriaal kasvab täpselt

figury65

korda. See arv on aga palju suurem kui 350 – meil on kokku 350 tegurit, millest iga on suurem kui 350!. Teisisõnu, argumendi kahekordistamisel suureneb faktoriaal veel mitu korda rohkem kui ruutuvõtmise korral. Jällegi, varem või hiljem rebib ta ka eksponentsiaalfunktsioonist ette.

Niisiis peaks olema täiesti usutav, et faktoriaal kasvab kiiremini kui eksponentsiaalfunktsioon ja seega ka kiiremini kui polünomiaalfunktsioon.

Järelikult kui keegi räägib oma varade eksponentsiaalsest kasvust, tuleb muidugi üle kelkida ja vastata: see pole veel midagi, minu varandus kasvab faktoriaalselt!

 

Kombinatsioonid ja variatsioonid