Feladat: F.1809 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1972/október, 60 - 62. oldal  PDF file
Témakör(ök): Sorozat határértéke, Rekurzív eljárások, Kombinációk, Klasszikus valószínűség, Feladat
Hivatkozás(ok):Feladatok: 1972/február: F.1809

Levelet írtunk tíz barátunknak és a leveleket a megcímzett borítékokba véletlenszerűen tettük bele. Mi a valószínűsége annak, hogy pontosan 5 levél kerül ahhoz, akinek szántuk ?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A lehetséges események száma 10!, ennyiféleképpen permutálhatjuk a leveleket az egy sorban lerögzített borítékok előtt a betevés céljára.
Kedvező eseménynek azt tekintjük, ha a levelek közül valamelyik 5 a saját borítékjába jut, a többi 5 levél viszont úgy helyezkedik el a maradó 5 borítékban ‐ vagyis éppen a nekik szánt 5 borítékban ‐, hogy egyik sem a saját borítékjában van benne. A helyesen borítékolt 5 levél (105) különböző módon választható meg. Minden ilyen esetben lényegében ugyanaz a további feladat áll előttünk: a hátralevő 5 levél ‐ jelöljük őket röviden az 1, 2, 3, 4, 5 számokkal ‐ olyan sorrendjei, permutációi számának megállapítása a rendre hozzájuk tartozó 1, 2, 3, 4, 5 sorszámú borítékok előtt ‐ röviden: helyeken ‐, amelyekben minden egyes szám részére egy-egy hely tiltott és megfordítva minden egyes hely részére egy-egy szám tiltott, pl. az 1-es szám bárhol állhat, csak az 1. helyen nem, és az 1. helyen bármi állhat, csak az 1-es szám nem, és így tovább.
Nevezzük általában az 1,2,...,n számok ilyen sorrendjeit e számok abszolút permutációinak, jelöljük a számukat An-nel. Tegyük fel, hogy A1, A2, A3 és A4 értékét már ismerjük, megmutatjuk, hogy ezekből A5 értéke kiszámítható.
Állítsuk az 5-öst valamelyik kisebb sorszámú helyre, mondjuk a 4-ikre. (Ezzel természetesen a 4-es számra is teljesül a követelmény.) Ha most a 4-est az 5. helyre írjuk be ‐ vagyis a 4 és 5 helyet cserél ‐, ezáltal feladatunk leszűkül az 1, 2, 3 számok abszolút permutálására, az ilyenek száma tehát A3.
Ha pedig a 4-est nem az 5. helyre tesszük, akkor az 1, 2, 3, 4 számok abszolút permutációit kell képeznünk az 1., 2., 3. és 5. helyeken (a 4-es részére más szempont miatt tilos az 5. hely, ti. azért, mert az olyan permutációkat már elintéztük), ide tehát A4 számú sorrend tartozik.
Amíg tehát az 5-ös a 4. helyen áll, A3+A4 abszolút permutációt kapunk, és ha az 5-ös szám sorra veszi a részére megengedett 4 helyet, akkor A5=4(A3+A4)-et.
Ugyanezzel a gondolatmenettel A4=3(A2+A3) és A3=2(A1+A2), másrészt nyilvánvalóan A1=0 és A2=1. Ezek szerint A3=2,A4=9 és A5=44, tehát a levél elkeveredési problémában (105)44 a kedvezőnek tekintett esetek száma.
A keresett valószínűség pedig

p=110!(105)44=10!4410!5!5!=441202=113600=0,0031.
(Másképpen: 3600 találomra vett próbálkozás közül 11-szer, azaz 1000-ből 3-szor várható a kívánt típusú elrendeződés.)
 

Megjegyzések. 1. Hasonlóan azoknak az eseteknek a k száma, amelyekben pontosan j a jól borítékolt levelek száma:
 

j=0,1,2,3,4,k=1334961,ll1334960,ll667485,ll222480,ll55650,l
 

j=5,6,7,8,9,l10,lk=11088,ll1890,ll240,ll45,ll0,ll1.l
 

Feltűnő, hogy a j=0 és j=1 számokhoz tartozó k0=A10 és k1=10A9 számok csak 1-gyel térnek el egymástól, tehát A10=10A9+1. Ez nem véletlen, alább magyarázatát adjuk.
 

2. A megoldás gondolatmenete szerint An=(n-1)(An-1+An-2). Írjuk fel ezt az egyenlőséget egymás alá A2n-re, A2n-1-re,...,A3-ra, szorozzuk meg a páratlan indexűekre vonatkozó sorokat (-1)-gyel:
A2n=(2n-1)A2n-1+(2n-1)A2n-2,-A2n-1=-(2n-2)A2n-2-(2n-2)A2n-3,A2n-2=(2n-3)A2n-3+(2n-3)A2n-4,........................-A5=-4A4-4A3,A4=3A3+3A2,-A3=-2A2-2A1.
Összeadással, rendezéssel, A1=0 és A2=1 figyelembevételével
A2n=2nA2n-1+1,
majd lényegében ugyanígy
A2n+1=(2n+1)A2n-1,
azaz egységesen
An=nAn-1+(-1)n.

3. Meglepő a hasonlóság eredményünk és a permutációk számára érvényes Pn=nPn-1 összefüggés között. De mit tesz az a (-1)n tagocska, amit a kombinatorikában megszokott "nagy'' számok mellett hajlamosak vagyunk lekicsinyelni! Az első három tagban letöri An-et Pn-hez képest! A2=2A1+(-1)2 esetében még ez a "nagyobbik'' a két tag közül, de már így is A2 csak fele a P2-nek; ezután A3=3A2-1 esetében még jelentősen csökkent a (-1)3 tag, és A3=P3/3. A talált 1/3 az An/Pn arány legkisebb értéke.
Meg lehet mutatni ‐ az érkezett megoldások ezzel, vagy a hozzá vezető meggondolással dolgoztak, ‐ hogy minden n-re
An=n!-n!1!+n!2!-n!3!+...+(-1)nn!n!,
ebből pedig
limnAnPn=1e=0,36...,
ahol e a természetes logaritmus alapszáma.
 

4. A valószínűségszámítás "őskorában'', amikor még kizárólag szerencsejátékok kérdéseit vizsgálták, problémánk 13-as játék (franciául: jeu du treize) néven szerepelt: a francia kártya egy színének 13 lapja hányféleképpen rendezhető el úgy (vagy keverés után vakon egymás után rakva hányféleképpen adódhat), hogy egyik lap se álljon a maga számának megfelelő helyen (a fiú a 11., a dáma a 12., a királya 13 helyen).