Püsipunktita permutatsioon

Graaf, mis vastab arvude 1 kuni 8 ühele püsipunktita permutatsioonile. See permutatsioon ei jäta ühtki arvu paigale

Püsipunktita permutatsioon ehk korratus on kombinatoorikas hulga elementide permutatsioon, mis ei jäta ühtki elementi paigale.

${\displaystyle n}$-elemendilise hulga võimalike püsipunktita permutatsioonide arvu näitab subfaktoriaal ${\displaystyle {!}n}$.

Arvu ${\displaystyle n}$ kasvades läheneb ${\displaystyle n}$ elemendi permutatsioonide hulgas püsipunktideta permutatsioonide osakaal kiiresti arvu e pöördväärtusele.

Juhul kui permutatsioonis jääb osa elemente paigale, saab rääkida osalisest korratusest. Osaliste korratuste arvu näitavad kohtumiste arvud.

Lähteülesanne

Kaardimängus "Treize" võidab mängija, kui 13 segatud ühte masti kaardist (alumine rida) asetseb vähemalt üks kaart oma õigel kohal (ülemine rida). Siin asetseb kümme õigel kohal.

Prantsuse matemaatik Pierre Rémond de Montmort tutvustas 18. sajandi alguses oma raamatus "Essai d'analyse sur les jeux de hazard" kaardimängu nimega "Treize" ("Kolmteist"), mis lihtsustatud kujul käib nii:^[1] "Mängija segab 13 ühte masti mängukaardi komplekti ning asetab kaardid enda ette pakki. Nüüd avab ta ükshaaval kaardid, kutsudes järjekordset kaarti vastavalt järjekorrale nimega äss, kaks, kolm jne kuni kuningani. Kui kutsutud kaart peaks millalgi avatud kaardiga kokku langema, siis ta võidab mängu; kui seda ühegi kaardi puhul 13 seast ei juhtu, siis ta kaotab." Montmort küsis, millise tõenäosusega mängija mängu võidab. Oma raamatu esimeses trükis aastast 1708 esita de Montmort küll õige tulemuse, kuid ilma täpsema tuletuskäiguta. Teises trükis aastast 1713 esitas ta kaks tõestust: üks on tema enda oma ja põhineb rekurrentsetel esitustel, teine pärineb kirjavahetusest Nikolaus I Bernoulliga ja põhineb inklusiooni ja eksklusiooni printsiibil. De Montmort näitab edasi, et võidu tõenäosus on väga lähedal arvule ${\displaystyle 1-e^{-1}\approx 0{,}6321}$. Tõenäoliselt on tegu eksponentfunktsiooni esimese rakendusega tõenäosusteoorias.^[2]

Varasemaid töid tundmata analüüsis Leonhard Euler 1753 sarnast õnnemängu nimega "Rencontre", mis käib nii:^[3] "Kahel mängijal on kummalgi täielik 52 mängukaardi komplekt. Nad segavad oma kaardid ja panevad enda ette pakki. Nüüd võtavad mõlemad mängijad korraga oma pakist kõige ülemise kaardi. Kui millalgi tuleb kaks korda sama kaart, siis võidab üks mängija, vastasel juhul teine." Jälle tekib küsimus võidu tõenäosusest. Euler tuletab lahenduse uute rekurrentsete valemite abil, kusjuures ta tohib eeldada, et ainult üks mängijatest oma kaarte segab ja teine mängija avab oma kaardid etteantud järjekorras.

Küsimuseasetuse teisi variante ja üldistusi uurisid teiste seas Abraham de Moivre^[4], Johann Heinrich Lambert^[5] ja Pierre-Simon Laplace^[6].

Tänapäeva kombinatoorikaõpikutes sõnastatakse seda ülesannet sageli "Vahetusse läinud kübarate probleemina" (kübarate asemel võivad olla ka n näiteks mantlid, kohvrid või kirjad) umbes nii:^[7][8][9] "Vastuvõtul annavad ${\displaystyle n}$ külalist kübarad garderoobi ära. Riidehoidja on sel õhtul aga väga hajameelne ning annab lahkumisel igale külalisele tagasi juhuslikult valitud kübara. Kui suur on tõenäosus, et vähemalt üks külaline saab õige kübara?"

Need kolm matemaatilist probleemi on teatud mõttes samaväärsed ning neid saab lahendada, uurides püsipunktita permutatsioone.

Definitsioon

Olgu ${\displaystyle S_{n}}$ sümmeetriline rühm, mille moodustavad hulga ${\displaystyle \{1,\ldots ,n\}}$ kõik permutatsioonid. Permutatsiooni ${\displaystyle \pi =(\pi (1),\pi (2),\ldots ,\pi (n))\in S_{n}}$ nimetatakse püsipunktivabaks, kui kõigi ${\displaystyle i=1,\ldots ,n}$ korral

${\displaystyle \pi (i)\neq i}$.

Püsipunktivaba permutatsioon on seega permutatsioon, mille korral ükski element ei jää paigale, ehk teiste sõnadega, ei esine tsüklit pikkusega üks.

Püsipunktita permutatsiooni tõenäosus

Olgu ${\displaystyle D_{n}}$ kõigi püsipunktita permutatsioonide hulk hulgas ${\displaystyle S_{n}}$ ning ${\displaystyle d_{n}=|D_{n}|}$ nende arv. Osakaal

${\displaystyle p_{n}={\frac {|D_{n}|}{|S_{n}|}}={\frac {d_{n}}{n!}}}$.

ongi Laplace'i valemi järgi püsipunktita permutatsiooni tõenäosus, kui eeldada, et kõik ${\displaystyle n!}$ võimaliku permutatsiooni on hulgas ${\displaystyle S_{n}}$ võrdtõenäosed.

Üldisemalt võib vaadelda ka mis tahes lõplike hulkade, näiteks tähestike permutatsioone, matemaatiliste omaduste uurimisel võib aga piirduda esimese ${\displaystyle n}$ naturaalarvuga.

Näited

Permutatsiooni püsipunkt ilmneb permutatsiooni kaherealises esituses sellena, et samal kohal on mõlemas reas sama arv.

Ainsal permutatsioonil hulgas ${\displaystyle S_{1}}$

${\displaystyle {\begin{pmatrix}1\\1\end{pmatrix}}}$

on püsipunkt ning seetõttu ${\displaystyle d_{1}=0}$ ja ${\displaystyle p_{1}=0}$. Hulgas ${\displaystyle S_{2}}$ on kaks permutatsiooni

${\displaystyle {\begin{pmatrix}1&2\\1&2\end{pmatrix}}}$   ja   ${\displaystyle {\begin{pmatrix}1&2\\2&1\end{pmatrix}}}$,

kusjuures neist esimesel on kaks püsipunkti ja teisel pole ühtki. Nii et ${\displaystyle d_{2}=1}$ ja ${\displaystyle p_{2}={\tfrac {1}{2}}}$.

Hulga ${\displaystyle S_{3}}$ kuuest permutatsioonist

${\displaystyle {\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}},{\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}},{\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}},{\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}},{\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}}$   ja   ${\displaystyle {\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}}$

on ainult neljas ja viies püsipunktita, seega ${\displaystyle d_{3}=2}$ ja ${\displaystyle p_{3}={\tfrac {2}{6}}={\tfrac {1}{3}}}$.

Hulga ${\displaystyle S_{0}}$ puhul on kandja tühi hulk, millel on üksainus permutatsioon. Et tühjast hulgast ei saa elementi välja valida, siis on see permutatsioon püsipunktita, nii et ${\displaystyle d_{0}=1}$ und ${\displaystyle p_{0}=1}$.

Viited

1. Pierre Rémond de Montmort. Essai d'analyse sur les jeux de hazard, Paris: Jacque Quillau 1708, lk 58; 2. trükk 1713 muu hulgas koos Nikolaus I Bernoulli kirjadega
2. Florence Nightingale David. Games, Gods and Gambling, London 1962, lk 162.
3. Leonhard Euler. Calcul de la probabilité dans le jeu de rencontre. – Memoirs de l'academie des sciences de Berlin, 1753, kd 7.
4. Abraham de Moivre. Doctrine of Chances, London: W. Pearson 1718, lk 109–117
5. Johann Heinrich Lambert. Examen d’une espèce de Superstition ramenée au calcul des probabilités. – Nouveaux Mémoires de l’Académie Royale des Sciences et des Belles-Lettres, 1771,lk 411–420.
6. Pierre-Simon Laplace. Théorie Analytique des Probabilités, Paris: Courcier 1812.
7. Matoušek, Nešetřil. Diskrete Mathematik: Eine Entdeckungsreise, lk 100–101.
8. Kütting, Sauer. Elementare Stochastik: Mathematische Grundlagen und didaktische Konzepte, lk 155.
9. Beutelspacher, Zschiegner. Diskrete Mathematik für Einsteiger, lk 57.