A szeptember 19-i gyakorlat témája

A múlt gyakorlaton megbeszéltük, hogy hány különböző módon lehet kiválasztani n elemből k elemet. Valójában ez négy különböző probléma. Azt kell nézni, hány különböző módon lehet n elemből k elemet kiválasztani, ha

a) Visszatevés nélkül választjuk ki az elemeket, és a sorrend számít.

b) Visszatevés nélkül választjuk ki az elemeket, és a sorrend nem számít.

c) Visszatevéssel választjuk ki az elemeket, és a sorrend számít.

d) Visszatevéssel választjuk ki az elemeket, és a sorrend nem számít.

Ezen esetek közül a b) eset a legfontosabb. Több ekvivalens megfogalmazású probléma van, amely gyakran felmerül. Ezért érdemes ezeket részletesebben megtárgyalni.

A múlt gyakorlaton megbeszéltük, hogy a b) kérdésre adott válasz ekvivalens a következő állítással.

Azon k hosszúságú szigorúan monoton egész számokból álló sorozatok száma, amelyek elemei az \{1, …, n\} halmazból vannak kiválasztva. \binom{n}{k}.

1.) Lássuk be, hogy az előző állítás ekvivalens a következő állítással: Egy n elemű halmaznak \binom{n}{k} k elemű részhalmaza van. Megoldás: Feltehetjük, hogy az n elemű halmaz az {1, …, n} halmaz. Ennek k elemű részhalmazai azonosíthatóak (a részhalmaz elemeit nagyság szerint sorba rendezve) azon k hosszúságú szigorúan monoton egész számokból álló sorozatokkal, amelyek elemei az {1, …, n} halmazból vannak kiválasztva. Az ilyen sorozatok száma viszont \binom{n}{k}.

Egy másik ekvivalens megfogalmazás: 2.) Legyen adva két urna, és dobjunk be egymás után n golyót e két urna valame-

lyikébe. Hány különböző olyan dobássorozat van, amelyik során az első urnába k a második urnába pedig n − k golyó kerül? Megoldás: A válasz \binom{n}{k}. Egy ilyen dobássorozatot egyértelműen megadunk, ha megmondjuk, hányadik dobások kerülnek az első urnába. Az ilyen indexek száma \binom{n}{k}, mert az \{1, 2, …, n\} dobások száma \binom{n}{k}, mert az első urnába k golyó esik.

3.) Legyen adva k urna, és dobjunk be egymás után n golyót e k urna valamelyikébe.

Rögzítsünk k nem-negatív l_{1}, …, l_{k} egész számot úgy, hogy ∑_{j=1}^{k} l_{j} = n. Hány

különböző olyan dobássorozat van, amelyek során a j-ik urnába l_{j} golyó esik minden 1 ≤ j ≤ k indexre? Megoldás: A válasz \frac{n!}{l_{1}!···l_{k}!}. Az első urnába eső l_{1} golyó dobás időpontját \binom{n}{l_{1}}- féle módon választhatjuk. A maradék n − l_{1} golyóból a második urnába eső dobások időpontját \binom{n−l_{1}}{l_{2}}-féleképp választhatjuk. A harmadik urnába eső golyók dobás időpontja az első két urnába eső golyók dobás időpontját korábban rögzítve \binom{n−l_{1}−l_{2}}{l_{3}}-féleképp választható. Hasonlóan a j-ik urnába eső golyók dobás időpontja \binom{n−l_{1}−···−l_{j−1}}{l_{j}}-féleképp választható, ha az előző j − 1 urnába eső golyók dobás időpontját már rögzítettük. Ez igaz minden 1 ≤ j ≤ k számra, ha bevezetjük az l_{0} = 0 jelölést (abból a célból, hogy az állítás j = 1 esetre is érvényes legyen). Ezért a keresett dobássorozatok száma

∏_{j=1}^{k} \binom{n − l_{1} − ⋯ − l_{j−1}}{l_{j}} = ∏_{j=1}^{k} \frac{(n − l_{1} − ⋯ − l_{j−1})!}{(n − l_{1} − ⋯ − l_{j})!}l_{j}! = \frac{n!}{l_{1}! ⋯ l_{k}!},

ahol az n − l_{1} − ⋯ − l_{j−1} = n konvenciót alkalmazzuk a j = 1 esetben. Második megoldás. (Rövid megoldásvázlat.) Sorsoljuk ki először azt az l_{1} időpontot, amikor az első urnába, azután azt az l_{2} időpontot amikor a második urnába dobjuk a golyót, és így tovább, végül azt az l_{1} időpontot, amikor a k-ik urnába dobjuk a golyót. Az ilyen húzássorozatok száma n!. (Az első urnába eső dobások időpontjait n(n − 1) ⋯ (n − l_{1} + 1, a második urnába eső dobások időpontjait (n − l_{1}) ⋯ (n−l_{1} −l_{2} +1)-féleképp, és így tovább a k-ik urnába eső dobások időpontjait (n − l_{1} − ⋯ − l_{k−1}) ⋯ (n − l_{1} − ⋯ − l_{k} + 1) módon választhatjuk. Emlékezzünk,

hogy ∑_{j=1}^{k} l_{j} = n.) Viszont ily módon minden lehetséges húzássorozatot l_{1}! ⋯ l_{k}!

multiplicitással számoltuk, mert nincs jelentősége annak, hogy a j-ik urnába eső l_{j} dobások időpontot milyen sorrendben sorsoltuk ki.

4.) Legyen adva k urna, és dobjunk be egymás után n golyót e k urna valamelyikébe. Legyen minden dobássorozat valószínűsége egyforma. Rögzítsünk k nem-negatív

l_{1}, …, l_{k} egész számot úgy, hogy ∑_{j=1}^{k} l_{j} = n. Mi annak a valószínűsége, hogy a j-ik

urnába l_{j} golyó minden 1 ≤ j ≤ k indexre? Megoldás: A válasz \frac{1}{k^{n}} \frac{n!}{l_{1}!···l_{k}!}. Ugyanis k^{n} lehetséges dobássorozat van, így minden dobássorozat valószínűsége \frac{1}{k^{n}}. Innen, és az előző feladat eredményéből következik az állítás.

5. Egy urnában 20 piros és 30 fehér golyó van. Kihúzunk 25 golyót visszatevéssel. Mi annak a valószínűsége annak, hogy az első húzás eredménye piros. Annak, hogy az első húzás eredménye piros és a másodiké fehér? Annak, hogy az ötödik húzás eredménye piros? Annak, hogy az ötödik húzás eredménye piros és a tízenhatodik húzás eredménye fehér? Megoldás: Annak a valószínűsége, hogy az első húzás piros \frac{20}{50} = \frac{2}{5}, mert 50 golyóból húzzuk ki a 20 piros golyó valamelyikét, és minden golyót egyforma valószínűséggel húzunk ki. Annak a valószínűsége, hogy az első húzás piros, a második fehér, \frac{2}{5} · \frac{3}{5} = \frac{6}{25}, mert először 50 golyó közül választjuk ki a húsz piros golyó valamelyikét majd 50 golyó valamelyikéből a 30 fehér golyó valamelyikét, és minden húzás egyforma valószínű. Hasonlóan annak valószínűsége, hogy az 5. húzásban piros golyót húzunk ki \frac{2}{5}, és annak valószínűsége, hogy az 5. húzás során piros és a 16. húzás során fehér golyót húzunk \frac{2}{5} · \frac{3}{5} = \frac{6}{25}.

Jegyezzük meg, hogy a következő feladat megoldása egy olyan érvet tartalmaz, amelyik ebben az esetben is alkalmazható, és megmutatja, hogy annak valószínűsége, hogy az 5. húzás piros és a 16. húzás fehér megegyezik annak valószínűségével, hogy az első húzás piros és a második húzás fehér. Érdemes ezeket az érveléseket mégegyszer végiggondolni azután, hogy megtárgyaltuk a valószínűségi mező pontos definicióját.

6. Egy urnában 20 piros és 30 fehér golyó van. Kihúzunk 25 golyót visszatevés nélkül. Mi a valószínűsége annak, hogy az első húzás eredménye piros? Annak, hogy az első húzás eredménye piros és a másodiké fehér? Annak, hogy az ötödik húzás eredménye fehér? Annak, hogy az ötödik húzás eredménye piros és a tízenhatodik húzás eredménye fehér?

Megoldás: Annak a valószínűsége, hogy az első húzás piros \frac{20}{50} = \frac{2}{5}, mert 50 golyóból húzzuk ki a 20 piros golyó valamelyikét, és minden golyót egyforma valószínűséggel húzunk ki. Annak a valószínűsége, hogy az első húzás piros, a második fehér, \frac{2}{5}·\frac{30}{49} = \frac{60}{245}, mert először 50 golyó közül választjuk ki a húsz piros golyó valamelyikét, majd 49 golyó valamelyikéből a 30 fehér golyó valamelyikét, és minden húzás egyforma valószínű. Belátjuk, hogy annak valószínűsége, hogy a 16. húzásban piros golyót húzunk ki, megegyezik annak a valószínűségével, hogy az első húzás piros, azaz ez \frac{2}{5}. Továbbá annak a valószínűsége, hogy az 5. húzás során piros és a 16. húzás során fehér golyót húzunk megegyezik annak a valószínűségével, hogy az első húzás eredménye fehér, a második húzás eredménye piros. Ezért ez a valószínűség is \frac{2}{5} · \frac{30}{49} = \frac{60}{245}.

Tekintsük ugyanis az összes 25 hosszúságú húzássorozatot. Ekkor annak valószínűsége, hogy az 5. húzás eredménye piros a 16. húzás eredménye fehér megegyezik az összes olyan 25 hosszúságú húzássorozat valószínűségének az összegével, amelyek 5. helyén piros és a 16. helyén fehér jegy áll. Hasonlóan számítható ki annak a valószínűsége, hogy az első húzás piros és a második húzás eredménye fehér, azzal a különbséggel, hogy az 5. hely helyett az első és a 16. hely helyett a második helyet kell tekinteni. Be fogjuk látni, hogy ugyanaz a képlet fejezi ki ezt a két különböző valószínűséget, erért ezek a valószínűségek megegyeznek.

Vegyük észre, hogy annak valószínűsége, hogy egy előírt konkrét 25 hosszúságú sorozat jelenik meg csak attól függ, hogy a sorozat hány piros és hány fehér golyót tartalmaz, de nem függ a fehér és piros húzások sorrendjétől. Valóban, ha egy húzássorozat k piros és 25 − k fehér golyót tartalmaz, akkor ennek valószínűsége P (k) = \frac{25·24···(25−k+1)·30·29···(30−(25−k)+1)}{50·49···26}. Ugyanis egy előírt húzássorozat való-

színűsége ∏_{j=1}^{25} \frac{l(j)}{50−j+1}, ahol l(j) az a j − 1-ik húzás után az urnában maradt piros

golyók száma, ha a j-ik húzás piros, és a j − 1-ik húzás után az urnában maradt fehér golyók száma, ha a j-ik húzás fehér. Gondoljuk meg, hogy ez a kifejezés megegyezik a megadott formulával.

Jelölje A(k; 5, 16) az olyan 25 hosszúságú sorozatok számát, amelyek k piros és 25 − k fehér jelet tartalmaznak, és az 5. helyen piros a 16. helyen pedig fehér jel áll. Jelölje továbbá A(k; 1, 2) az olyan 25 hosszúságú sorozatok számát, amelyek k piros és 25 − k fehér jelet tartalmaznak, az 1. helyen piros a 2. helyen pedig fehér jel áll. Ekkor a két összehasonlítandó valószínűség ∑_{k} A(k; 5, 16)P (k) illetve

∑_{k} A(k; 1, 2)P (k). Ezért annak érdekében, hogy megmutassuk a kívánt azonosság

teljesülését elegendő belátni azt, hogy A(k; 5, 16) = A(k; 1, 2) minden k számra. Viszont nem nehéz belátni, hogy A(k; 5, 16) = A(k; 1, 2) = \binom{23}{k−1}, mert mind a két esetben 23 előírt helyre kell írni k − 1 piros és 25 − (k + 1) fehér golyót. Az utolsó azonosság egy másik lehetséges bizonyítása: Mutassuk meg, hogy ha tekintjük az összes 25 hosszúságú k piros és 25−k fehér golyót tartalmazó sorozatot, akkor az ilyen sorazatok 5. jelét kicserélve az elsővel és a 16. jelét a másodikkal kölcsönösen egyértelmű megfeleltetést kapunk azon halmazok között, amelyek számosságaként definiáltuk az A(k; 5, 16) és A(k; 1, 2) számokat. Hasonlóan mutatható meg, hogy annak a valószínűsége, hogy az első, illetve hogy az ötödik húzás piros megegyezik.

7. Egy urnában 20 piros és 30 fehér golyó van. Kihúzunk 25 golyót. Minden húzás után a kihúzott golyót visszadobjuk egy másik ugyanolyan színű golyóval. Lássuk be, hogy annak a valószínűsége, hogy a 3. és 7. húzáskor piros golyót húzunk megegyezik annak valószínűségével, hogy az első és második húzáskor piros golyót húzunk. Számítsuk ki ezt a valószínűséget. Megoldás: Tekintsünk egy olyan 25 hosszúságú húzássorozatot, amely k piros és 25−k fehér golyót tartalmaz. Vegyük észre, hogy egy ilyen sorozat p_{k} valószínűsége csak a k számtól függ, de nem függ attól, hogy mely helyeken vannak a piros húzások. Valóban,

p_{k} = \frac{20(20 + 1) ⋯ (20 + k − 1)30(30 + 1) ⋯ (30 + (25 − k) − 1)}{50(50 + 1) ⋯ (50 + 25 − 1)}

Jelőlje, A(k) azon 25 hosszúságú sorozatok számát, amelyek k piros és 25 − k fehér golyót tartalmaznak, és az 1. és 2. húzás piros; B(k) azon 25 hosszúságú sorozatok számát, amelyek k piros és 25 − k fehér golyót tartalmaznak, és a 3. és 7. húzás piros. Ekkor a két vizsgált valószínűség a ∑_{k} A(k)p_{k}, illetve ∑_{k} B(k)p_{k} kifejezéssel

egyenlő. Ezért a feladat megoldásához elég belátni, hogy A(k) = B(k) minden k

számra is. Ez valóban igaz, mert A(k) = B(k) = \binom{23}{k − 2}. Könnyű közvetlenül

kiszámolni, annak valószínűségét, hogy az első két húzás piros. \frac{20}{50} · \frac{21}{51}, mivel az első húzásban \frac{20}{50} valószínűséggel húzunk pirosat, és ha az első húzás piros volt, akkor a második húzásban \frac{21}{51} valószínűséggel húzunk pirosat a 21 piros és 30 fehér golyó közül.

Házi feladat: Számítsuk ki annak valószínűségét, hogy lottón legalább három találatot érünk el.