\input amstex
\magnification=\magstep1
\hsize=16truecm

\parskip=1pt plus 1pt
\define\A{{\bold A}}
\define\BB{{\bold B}}
\define\DD{{\bold D}}
\define\T{{\bold T}}
\define\U{{\bold U}}
\define\({\left(}
\define\){\right)}
\define\[{\left[}
\define\]{\right]}
\define\e{\varepsilon}
\define\oo{\omega}
\define\const{\text{\rm const.}\,}
\define\supp {\sup\limits}
\define\inff{\inf\limits}
\define\summ{\sum\limits}
\define\prodd{\prod\limits}
\define\limm{\lim\limits}
\define\limsupp{\limsup\limits}
\define\liminff{\liminf\limits}
\define\bigcapp{\bigcap\limits}
\define\bigcupp{\bigcup\limits}
\define\Var{\text{\rm Var}\,}
\define\Cov{\text{\rm Cov}\,}

\beginsection A szita formula \'es alkalmaz\'asai.

Gyakran tal\'alkozunk az al\'abbi k\'erd\'essel, sokszor egy
\"osszetett feladat r\'esz\-fel\-ada\-ta\-k\'ent. Tekints\"unk bizonyos
$A_1,\dots,A_n$ esem\'enyeket, \'es sz\'am\'{\i}tsuk ki annak a
val\'o\-sz\'{\i}\-n\H{u}\-s\'e\-g\'et, hogy legal\'abb az egyik\"uk
bek\"ovetkezik. Form\'alisan megfogalmazva, sz\'am\'{\i}tsuk ki a
$P(A_1\cup\cdots\cup A_n)$ val\'osz\'{\i}n\H{u}s\'eget.

A k\"ovetkez\H{o} k\'et fontos speci\'alis esetben egyszer\H{u}en 
meg tudjuk oldani ezt a feladatot:

\medskip
\item{a)} Ha az $A_1,\dots,A_n$ esem\'enyek diszjunktak,
azaz $A_i\cap A_j=\emptyset$, ha $i\neq j$, $1\le i,j\le n$,
\item{b)} Ha az $A_1,\dots,A_n$ esem\'enyek f\"uggetlenek.
\item{} Az a) esetben
$$
P(A_1\cup\cdots\cup A_n)=P(A_1)+\cdots+P(A_n).
$$
A b) esetben
$$
\align
P(A_1\cup\cdots\cup A_n)
&=1-P(\overline{A_1\cup\cdots\cup A_n})
=1-P(\bar A_1\cap\cdots\cap \bar A_n)\\
&=1-P(\bar A_1)\cdots P(\bar A_n)
=1-(1-P(A_1))\cdots (1-P(A_n)),
\endalign
$$
ahol $\bar A=\Omega\setminus A$ az $A$ esem\'eny komplementer\'et
jel\"oli. (A fenti sz\'amol\'asban kihaszn\'altuk azt az eredm\'enyt,
amely szerint, ha az $A_1,\dots, A_n$ esem\'enyek f\"ug\-get\-le\-nek, 
akkor az $\bar A_1,\dots,\bar A_n$ esem\'enyek is azok.)
\medskip

Mit mondhatunk az \'altal\'anos esetben, ha a tekintett
$A_1,A_2,\dots,A_n$ esem\'enyek nem felt\'etlen\"ul diszjunktak,
\'es nem felt\'etlen\"ul f\"uggetlenek? Ez nehezebb k\'erd\'es,
\'es az \'altal\'anos esetben a $P(A_1\cup\cdots\cup A_n)$
val\'osz\'{\i}n\H{u}s\'eget nem lehet kifejezni csak a $P(A_j)$
val\'osz\'{\i}n\H{u}s\'egek seg\'{\i}ts\'eg\'evel. De ebben az
esetben is van egy hasznos \'es tartalmas eredm\'eny, az
\'ugynevezett szita formula, amely lehet\H{o}v\'e teszi a
$P(A_1\cup\cdots\cup A_n)$ val\'osz\'{\i}n\H{u}s\'eg
kisz\'am\'{\i}t\'as\'at bizonyos plusz inform\'aci\'ok
seg\'{\i}ts\'eg\'evel. Ismertetem ezt az eredm\'enyt.
Tov\'abb\'a t\'argyalni fogok
olyan feladatokat, amelyeket ennek az eredm\'enynek a
seg\'{\i}ts\'eg\'evel tudunk megoldani.

A kombinatorik\'aban is van az ismertetetend\H{o} eredm\'enynek
egy megfelel\H{o}je, amelyet szint\'en szita formul\'anak neveznek.
\'Erdemes ezt a k\'et eredm\'enyt, amelyek, mint k\'es\H{o}bb
l\'atni fogjuk val\'oj\'aban ekvivalensek p\'arhuzamosan
ismertetni. Annak \'erdek\'eben, hogy megk\"ul\"onb\"oztess\"uk
\H{o}ket, kombinatorikus \'es
val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formul\'ar\'ol
fogok besz\'elni.

El\H{o}sz\"or a kombinatorikus szita formul\'at ismertetem: Legyen
adva egy v\'eges $A$ halmaz, amely el\H{o}\'all bizonyos nem
felt\'etlen\"ul diszjunkt $A_j$, $1\le j\le n$, halmazok
$A=A_1\cup A_2\cup\cdots\cup A_n$ uni\'ojak\'ent.
Szeretn\'enk megsz\'amolni az $A$ halmaz elemeinek $|A|$ sz\'am\'at.
Tekints\"unk egy olyan esetet, amikor erre k\"ozvetlen\"ul nem
vagyunk k\'epesek, de meg tudjuk sz\'amolni az $A_j$ halmazok
elemeinek $|A_j|$ sz\'am\'at minden $1\le j\le n$ sz\'amra. Ekkor
az $S_1=\summ_{j=1}^n |A_j|$ mennyis\'eg  term\'eszetes becsl\'es
lenne az $|A|$ sz\'amra. De ez csak egy fels\H{o} becsl\'es az
\'altal\'anos esetben, mert egy olyan elemet, amely mind az $A_i$
mind az $A_j$ halmazban benne van valamely $i\neq j$ indexp\'arra
k\'etszer sz\'amoltunk az $S_1$ kifejez\'esben holott csak egyszer
kellett volna. Ezt korrig\'aland\'o vezess\"uk be az
$S_2=\summ_{1\le i<j\le n}|A_i\cap A_j|$ \"osszeget, \'es vegy\"uk
az $S_1-S_2$ becsl\'est. Ekkor azonban csak az $S_1-S_2\le |A|$
egyenl\H{o}tlens\'eget kapjuk, mert p\'eld\'aul egy olyan elemet,
amely h\'arom halmazban van benne h\'aromszor sz\'amoltuk az $S_1$
\"osszegben \'es h\'aromszor vontuk le az $S_2$ \"osszegben, teh\'at
az ilyen pontok l\'etez\'es\'et nem vett\"uk figyelembe az $S_1-S_2$
becs\-l\'es\-ben. (Ha az $A_i$, $A_j$ \'es $A_k$ halmazban van a 
tekintett pont akkor pozit\'{\i}v el\H{o}jellel sz\'amoltuk az $S_1$
\"osszeg $|A_i|$, $|A_j|$ \'es $|A_k|$ tagjaiban \'es
negat\'{\i}v el\H{o}jellel az $S_2$ \"osszeg $|A_i\cap A_j|$,
$|A_i\cap A_k|$ \'es $|A_j\cap A_k|$ tagjaiban.) Ez\'ert
korrig\'aljuk ezt az \"osszeget is. Vezess\"uk be az
$S_3=\summ_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|$
kifejez\'eseket. Ekkor be lehet l\'atni, hogy $S_1-S_2+S_3\ge |A|$.
Ha azonoss\'agot akarunk kapni akkor ezt a korrekci\'os elj\'ar\'ast
tov\'abb kell folytatni, mert p\'eld\'aul
a 4 k\"ul\"onb\"oz\H{o} $A_j$ halmazban szerepl\H{o} elemeket
figyelembe v\'eve \dots A fenti, kiss\'e nagyvonal\'uan t\'argyalt
gondolatmenetet r\'eszletesebben kidolgozva \'es folytatva a
k\"ovetkez\H{o} eredm\'enyhez jutunk.

\medskip\noindent
{\bf Kombinatorikus szita formula.} {\it Legyenek adva bizonyos
v\'eges sok elemet tartalmaz\'o $A_1,\dots,A_n$ halmazok,
\'es tekints\"uk ezek $A=A_1\cup A_2\cup\cdots\cup A_n$
uni\'oj\'at. Jel\"olje $|X|$ egy v\'eges $X$ halmaz elemeinek a
sz\'am\'at. Az $A$ halmaz elemeinek $|A|$ sz\'am\'at a
k\"ovetkez\H{o} formul\'aval fejezhetj\"uk ki. Vezess\"uk be az
$$
S_k=\sum_{1\le j_1<\cdots<j_k\le n} |A_{j_1}\cap \cdots\cap  A_{j_k}|,
\quad 1\le k\le n,
$$
mennyis\'egeket. Ekkor
$$
|A|=|A_1\cup \cdots\cup A_n|=S_1-S_2+S_3-\cdots +(-1)^{n+1}S_n.
$$
Tov\'abb\'a,
$$
S_1-S_2=\sum _{j=1}^n|A_j|-\sum_{1\le j<k\le n}|A_j\cap A_k|\le
|A|=|A_1\cup \cdots\cup A_n|\le S_1=\sum_{j=1}^n|A_j|
$$
\'es \'altal\'aban
$$
\sum_{k=1}^{2l}(-1)^{k+1}S_k\le
|A|=|A_1\cup \cdots\cup A_n|\le \sum_{k=1}^{2l-1}(-1)^{k+1}S_k
$$
minden $l\ge1$ indexre. (Legyen $S_k=0$, ha $k>n$.) Ez az
egyenl\H{o}tlens\'eg azt jelenti, hogy a kombinatorikus 
szita formul\'aban szerepl\H{o}
$S_1-S_2+S_3-\cdots$ el\H{o}jeles \"osszeg p\'aratlan sz\'am\'u
tagot tartalmaz\'o r\'eszlet\"osszegei fels\H{o} \'es p\'aros
sz\'am\'u tagot tartalmaz\'o r\'eszlet\"osszegei als\'o becsl\'est
adnak az $|A|=|A_1\cup\cdots\cup A_n|$ mennyis\'egre.}

\medskip
Ezen eredm\'eny val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi
megfelel\H{o}je, a val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita
formula hasonl\'o eredm\'enyt \'all\'{\i}t bizonyos $A_1,\dots,A_n$
esem\'enyek uni\'oj\'anak a
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-g\'e\-r\H{o}l.

\medskip\noindent
{\bf Val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formula.}
{\it Legyenek adva tetsz\H{o}leges $A_1,\dots,A_n$
ese\-m\'e\-nyek egy $(\Omega,\Cal A,P)$ val\'osz\'{\i}n\H{u}s\'egi
mez\H{o}n. Ekkor
$$
P(A_1\cup \cdots\cup A_n)=S_1-S_2+S_3-\cdots +(-1)^{n+1}S_n,
$$
ahol
$$
S_k=\sum_{1\le j_1<\cdots<j_k\le n}P(A_{j_1}\cap\cdots\cap A_{j_k}), 
\quad 1\le k\le n.
$$
Tov\'abb\'a,
$$
S_1-S_2=\sum _{j=1}^nP(A_j)-\sum_{1\le j<k\le n}P(A_j\cap A_k)\le
P(A_1\cup \cdots\cup A_n)\le S_1=\sum_{j=1}^nP(A_j)
$$
\'es \'altal\'aban
$$
\sum_{k=1}^{2l}(-1)^{k+1}S_k\le
P(A_1\cup \cdots\cup A_n)\le \sum_{k=1}^{2l-1}(-1)^{k+1}S_k
$$
minden $l\ge1$ indexre. (Legyen $S_k=0$, ha $k>n$.) Ez az
egyenl\H{o}tlens\'eg azt jelenti, hogy a $P(A_1\cup\cdots\cup A_n)$
val\'osz\'{\i}n\H{u}s\'eget a szita formul\'aban kifejez\H{o}
$S_1-S_2+S_3-\cdots$ el\H{o}jeles \"osszeg p\'aratlan sz\'am\'u tagot
tartalmaz\'o r\'eszlet\"osszegei fel\"ulr\H{o}l \'es p\'aros sz\'am\'u
tagot tartalmaz\'o r\'eszlet\"osszegei alulr\'ol becs\"ulik meg a
vizsg\'alt val\'osz\'{\i}n\H{u}s\'eget.
}\medskip

{\it H\'azi feladat:}

\item{} Mutassuk meg, hogy a
val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formula a
kor\'abban ismertetett k\'epleteket adja speci\'alis esetk\'ent
diszjunkt vagy f\"uggetlen $A_1,\dots,A_n$ esem\'enyek
uni\'oj\'anak $P(A_1\cup\cdots\cup A_n)$
val\'osz\'{\i}n\H{u}s\'eg\'ere.

\medskip\noindent
Mutatok egy olyan feladatot, amelyet viszonylag
k\"onnyen meg tudunk oldani az el\H{o}bb
megfogalmazott val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi
szita formula se\-g\'{\i}t\-s\'e\-g\'e\-vel.

\medskip
{\it Feladat:}

\medskip
\item{} Egy est\'elyen megjelenik $n$ h\'azasp\'ar. Egy
t\'ancmester, aki nem tudja, hogy kik h\'azast\'arsak \'es kik nem,
v\'eletlen m\'odon p\'arba rendezi a f\'erfiakat \'es n\H{o}ket
a t\'anc el\H{o}tt. Mi a val\'osz\'{\i}n\H{u}s\'ege annak, hogy
egyetlen h\'azasp\'ar sem t\'ancol egy\"utt? Mi ennek a
val\'osz\'{\i}n\H{u}s\'egnek a hat\'ar\'ert\'eke, ha $n\to\infty$?
\item{} {\it Megold\'as:}\/ Defini\'aljuk a k\"ovetkez\H{o} $A_j$
esem\'enyeket:
$$
A_j=\text{a $j$-ik h\'azasp\'ar egy\"utt t\'ancol,}\quad 1\le j\le n.
$$
Ekkor minket a $P(\overline{A_1\cup\dots\cup A_{n}})=
1-P(A_1\cup\dots\cup A_{n})$ val\'osz\'{\i}n\H{u}s\'eg \'erdekel.
Sz\'amoljuk ki a $P(A_1\cup\dots\cup A_{n})$
val\'osz\'{\i}n\H{u}s\'eget a 
val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formula
seg\'{\i}ts\'eg\'evel. Ennek \'erdek\'eben vegy\"uk \'eszre, hogy
a $P(A_{j_1}\cap \cdots\cap A_{j_k})=\frac{(n-k)!}{n!}$ azonoss\'ag
\'erv\'enyes minden lehets\'eges $1\le j_1<\cdots<j_k\le n$
sz\'am-$k$-asra. Ugyanis az \"osszes lehets\'eges
p\'arba\'all\'{\i}t\'asok sz\'ama $n!$, m\'{\i}g az olyan
p\'arba\'all\'{\i}t\'asok sz\'ama, amelyben a $j_1$-ik,
$j_2$-ik,\dots, $j_k$-ik h\'azasp\'ar egy p\'arba ker\"ul $(n-k)!$.
Ez\'ert a val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita
formul\'aban bevezetett $S_k$ mennyis\'eg \'ert\'eke
$S_k=\binom nk\frac{(n-k)!}{n!}=\frac1{k!}$ minden $1\le k\le n$
sz\'amra.

\item{} Innen ad\'odik, hogy a minket \'erdekl\H{o}
val\'osz\'{\i}n\H{u}s\'eg $n$ h\'azasp\'ar eset\'en
$$
\align
P(\overline{A_1\cup \dots\cup A_{n}})&=1-P(A_1\cup\dots\cup A_{n}) \\
&=1-S_1+S_2+\cdots+(-1)^n S_n=\sum_{k=0}^n\frac{(-1)^k}{k!},
\endalign
$$
ahonnan
$$
P(\overline{A_1\cup \dots\cup A_{n}})
=\sum_{k=0}^n\frac{(-1)^k}{k!}\to \sum_{k=0}^\infty\frac{(-1)^k}{k!}
=\frac1e\quad \text{ ha } n\to\infty.
$$
Teh\'at nagy $n$ sz\'amra annak a val\'osz\'{\i}n\H{u}s\'ege, hogy
egy h\'azasp\'ar sem fog egy\"utt t\'ancolni k\"ozel\'{\i}t\H{o}leg
$\frac1e$.

\medskip
Mutatok h\'arom m\'asik feladatot is, ahol a szita formula j\'ol 
alkalmazhat\'o.

\medskip
{\it 1. feladat:}

\medskip
\item{} Egy urn\'ab\'ol, amelyben az $1,\dots,n$ sz\'amokat tartalmaz\'o
lapok vannak, kih\'uzunk $m$ lapot visszatev\'essel. Minden lapot
egyforma val\'osz\'{\i}n\H{u}s\'eggel h\'uzunk. Mi annak a 
val\'osz\'{\i}n\H{u}s\'ege, hogy az $1,\dots,k$ sz\'amot tartalmaz\'o
lapok mindegyik\'et kih\'uztuk? Mi ennek a 
val\'osz\'{\i}n\H{u}s\'egnek a hat\'ar\'ert\'eke r\"ogz\'{\i}tett
$k$ sz\'amra \'es $m=n$ h\'uz\'assz\'amra, ha $n\to\infty$?
\item{} {\it Megold\'as:}\/ Jel\"olje $A_j$, $1\le j\le k$, azt az
esem\'enyt, hogy a $j$ sz\'amot tartalmaz\'o lapot nem h\'uztuk ki,
\'es jel\"olje $\bar B$ egy $B$ esem\'eny komplementer\'et. Ekkor a
$P(\bar A_1\cap\bar A_2\cap \cdots\cap\bar A_k)
=P(\overline{ A_1\cup A_2\cup\cdots\cup A_k})
=1-P(A_1\cup A_2\cup\cdots\cup A_k)$
val\'osz\'{\i}n\H{u}s\'eget kell kisz\'amolnunk. Tov\'abb\'a,
$P(A_{j_1}\cap A_2\cap\cdots\cap A_{j_l})=\(\frac{n-l}n\)^m$
minden r\"ogz\'{\i}tett $1\le j_1<\cdots< j_l\le k$ indexsorozatra,
mert ez egy olyan esem\'eny  val\'osz\'{\i}n\H{u}s\'eg\'evel 
egyenl\H{o}, ahol $m$ (egym\'ast\'ol f\"uggetlen) h\'uz\'as  
mindegyik\'eben $n$ lehet\H{o}s\'eg k\"oz\"ul $l$ sz\'am 
kih\'uz\'as\'at tiltjuk meg. Innen
$S_l=\sum_{1\le j_1<\cdots<j_l\le k}P(A_{j_1}\cap\cdots\cap A_{j_l}) 
=\binom kl\(\frac{n-l}n\)^m$, minden $1\le l\le k$ indexre,
\'es a szita formula alapj\'an a keresett
val\'osz\'{\i}n\H{u}s\'eg
$1-P(A_1\cup A_2\cup\cdots\cup A_k)=1-S_1+S_2-\cdots+(-1)^kS_k=
1-\summ_{l=1}^k (-1)^l\binom kl\(1-\frac ln\)^m$.
Ennek hat\'ar\'ert\'eke $m=n$ \'es $n\to\infty$ eset\'en
$1-\summ_{l=1}^k (-1)^l\binom kle^{-l}=\summ_{l=0}^k \binom kl\(-\frac1e\)^l
=\(1-\frac1e\)^k$, mert $\limm_{n\to\infty}\(1-\frac ln\)^n=e^{-l}$.

\medskip
{\it 2. feladat:}

\medskip
\item{} Le\'{\i}runk egy 20 hossz\'us\'ag\'u sz\'ot, amelyik csak $A$, 
$B$, $C$ \'es $D$ bet\H{u}t tartalmaz. V\'alasszuk ki a sz\'o mindegyik
bet\H{u}j\'et egym\'ast\'ol f\"uggetlen\"ul egyforma
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'eg\-gel. 
\itemitem{a.)} Mi annak a val\'osz\'{\i}n\H{u}s\'ege, hogy a fel\'{\i}rt
sz\'o mind a n\'egy bet\H{u}t tartalmazza?
\itemitem{b.)} H\'any olyan 20 hossz\'us\'ag\'u n\'egy bet\H{u}s sz\'o
van, amelyik mind a n\'egy bet\H{u}t tartalmazza?
\item{} {\it Megold\'as:}\/ Jel\"olje, 1, 2, 3 \'es 4 a n\'egy bet\H{u}t.
Ezzel a megfogalmaz\'assal az a) r\'esz megegyezik az els\H{o} 
feladat probl\'em\'aj\'aval, ha $n=k=4$, \'es $m=20$. Ez\'ert az a)
r\'esz eredm\'enye
$1-\summ_{l=1}^4 (-1)^l\binom 4l\(1-\frac l4\)^{20}$.
\item{} \"Osszesen $4^{20}$ 20 hossz\'us\'ag\'u 4 bet\H{u}b\H{o}l
\'all\'o sz\'o van. Ez\'ert az a) r\'esz megold\'as\'ab\'ol k\"ovetkezik,
hogy a b) r\'esz megold\'asa
$4^{20}\(1-\summ_{l=1}^4 (-1)^l\binom 4l\(1-\frac l4\)^{20}\)
=4^{20}-\summ_{l=1}^4 (-1)^l\binom 4l\(4^{20}-l\)$. Ez az eredm\'eny
egy\'ebk\'ent k\"ozvetlen\"ul is levezethet\H{o} a kombinatorikus
szita formula seg\'{\i}ts\'eg\'evel.

\medskip
{\it 3. feladat:}

\medskip
\item{} Egy cornflake gy\'art\'o c\'eg minden dobozba betesz
egy kupont, \'es \"osszesen 10 k\"u\-l\"on\-b\"o\-z\H{o} kupont
haszn\'al. Mekkora annak a val\'osz\'{\i}n\H{u}s\'ege, hogy mind
a 10 kupont megkapja egy olyan v\'as\'arl\'o, aki 25 doboz
cornflake-et vesz?
\item{} {\it Megold\'as:}\/ Jel\"olje $A_j$, $1\le j\le10$, azt az
esem\'enyt, hogy a $j$-ik kupont megkapta a v\'as\'arl\'o, \'es
$\bar A_j$ ennek az esem\'enynek a komplementer\'et. Ekkor a
$P\(\bigcapp_{j=1}^{10}A_j\)$ val\'osz\'{\i}n\H{u}s\'eget kell
kisz\'amolnunk. Viszont $P\(\bigcapp_{j=1}^{10}A_j\)=
1-P\(\bigcupp_{j=1}^{10}\bar A_j\)$, \'es
$P\(\bigcupp_{j=1}^{10}\bar A_j\)=\summ_{k=1}^{10}(-1)^kS_k$,
ahol
$S_k=\summ P(\bar A_{j_1}\cap\bar A_{j_2}\cap\cdots \cap\bar A_{j_k})$,
\'es a $\{j_1,\dots,j_k\}$ indexhalmaz a fenti szumm\'aban
az $\{1,\dots,10\}$ halmaz \"osszes $k$ elem\H{u} 
r\'esz\-hal\-ma\-z\'a\-b\'ol \'all.
\item{} Viszont
$P(\bar A_{j_1}\cap\bar A_{j_2}\cap\cdots \cap\bar A_{j_k})
=\(\frac{10-k}{10}\)^{25}$, annak a val\'osz\'{\i}n\H{u}s\'ege,
hogy a lehets\'eges 10 kuponb\'ol mind a 25 v\'as\'arl\'asn\'al
a $j_1$,\dots $j_k$ index\H{u} kuponokt\'ol
k\"ul\"onb\"oz\H{o} $10-k$ kupon valamelyik\'et kapjuk. Ez\'ert
$S_k=\binom{10}k \(\frac{10-k}{10}\)^{25}$ minden $1\le k\le10$
indexre $k=10$-re $S_k=S_{10}=0$, ahonnan
$P\(\bigcapp_{j=1}^{10}A_j\)=
\summ_{k=0}^9(-1)^k\binom{10}k\(1-\frac k{10}\)^{25}$.

\medskip
A val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formula
bizony\'{\i}t\'as\'at egy kieg\'esz\'{\i}t\'esben fogom 
t\'ar\-gyal\-ni. Al\'abb megmutatom, hogy a kombinatorikus szita 
formula egyszer\H{u}en le\-ve\-zet\-he\-t\H{o} a
val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formul\'ab\'ol,
\'es vice versa.

A kombinatorikus szita formula igazol\'asa \'erdek\'eben 
tekints\"unk bizonyos $A_1,\dots,A_n$ v\'eges halmazokat, \'es 
jel\"olj\"uk e halmazok uni\'oj\'at $A=A_1\cup\cdots\cup A_n$-nel. 
Legyen $A=\{x_1,\dots,x_N\}$ egy $N$ elem\H{u} halmaz, \'es 
vezess\"uk be azt a val\'osz\'{\i}n\H{u}s\'egi mez\H{o}t, amelyben 
az $A$ halmaz elemeit v\'alaszthatjuk ki egyenletes eloszl\'assal.
R\'eszletesebben kifejtve, a k\"ovetkez\H{o} $(\Omega,\Cal A,P)$
val\'osz\'{\i}n\H{u}s\'egi mez\H{o}t defini\'aljuk: $\Omega=A$,
$\Cal A$ az $A$ halmaz \"osszes r\'eszhalmaz\'ab\'ol \'all\'o
$\sigma$-algebra, $P(\{x_j\})=\frac1N$ minden $1\le j\le N$
sz\'amra, ahonnan $P(B)=\frac{|B|}N$ minden $B\subset A$ halmazra.
Megmutatom, hogy a kombinatorikus szita formul\'at megkaphatjuk a
val\'osz\'{\i}n\H{u}s\'egi szita formula seg\'{\i}ts\'eg\'evel, ha
azt a most defini\'alt $(\Omega,\Cal A,P)$ val\'osz\'{\i}n\H{u}s\'egi
mez\H{o}n az $A_1,\dots,A_n$ halmazokra alkalmazzuk.

Jel\"olj\"uk a kombinatorikus szita formul\'aban defini\'alt $S_j$,
$1\le j\le n$, \"osszegek megfelel\H{o}it a val\'osz\'{\i}n\H{u}s\'egi
szita formul\'aban $\bar S_j$-vel. Ekkor ny\'{\i}lv\'an
$S_j=N\bar S_j$. Tov\'abb\'a, mivel $P(A)=1$, a
val\'osz\'{\i}n\H{u}s\'egi szita formula azt adja, hogy
$S_1-S_2+S_3-\cdots +(-1)^{n+1}S_n=
N(\bar S_1-\bar S_2+\bar S_3-\cdots +(-1)^{n+1}\bar S_n)=NP(A)=N$,
\'es mivel $|A|=N$, ezt kellett bizony\'{\i}tanunk. A
kombinatorikus szita formul\'aban megfogalmazott
egyen\-l\H{o}t\-len\-s\'e\-gek hasonl\'oan vezethet\H{o}k le
ezen \'all\'{\i}t\'asok megfelel\H{o}ib\H{o}l a
val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formul\'aban.

Megford\'{\i}tva, a val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi
szita formula is egyszer\H{u}en levezethet\H{o} a kombinatorikus
szita formul\'ab\'ol. Annak \'erdek\'eben, hogy ezt megtegy\"uk
tekints\"uk azt az $(\Omega,\Cal A,P)$ val\'osz\'{\i}n\H{u}s\'egi 
me\-z\H{o}t, ahol az $A_1$,\dots, $A_n$ esem\'enyek defini\'alva 
vannak, \'es defini\'aljuk minden $\oo\in\Omega$ elemi 
esem\'enyre \'es $B\in\Cal A$ halmazra azt a $\bar B=\bar B(\oo)$
halmazt, amelyre $\bar B(\oo)=\{\oo\}$, ha $\oo\in B$, \'es
$\bar B(\oo)=\emptyset$, ha $\oo\notin B$. Fel\'{\i}rom a
kombinatorikai szitaformul\'at az 
$\bar A_1(\oo)\cup\cdots\cup\bar A_n(\oo)$ halmaz sz\'amoss\'ag\'ara
minden $\oo\in\Omega$ elemi esem\'enyre, majd megmutatom, hogy
ezt az azonoss\'agot az $\oo$ szerint ki\'atlagolva, azaz
v\'arhat\'o \'ert\'eket v\'eve megkapjuk a
val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi
szita formul\'at.

A kombinatorikai szita formula szerint
$|\bar A_1(\oo)\cup\cdots\cup\bar A_n(\oo)|=\bar S_1(\oo)-\bar S_2(\oo)
+\bar S_3(\oo)-\cdots +(-1)^{n+1}\bar S_n(\oo)$, ahol
$\bar S_k(\oo)=\summ_{1\le j_1<\cdots<j_k\le n}
|\bar A_{j_1}(\oo)\cap\cdots\cap \bar A_{j_k}(\oo)|
=\summ_{1\le j_1<\cdots<j_k\le n}I_{A_{j_1}\cap\cdots\cap A_{j_k}}(\oo)$,
$1\le k\le n$. Itt \'es a tov\'abbiakban $I_B(\oo)$ jel\"oli egy
$B\in \Cal A$ halmaz indik\'atorf\"uggv\'eny\'et. Tov\'abb\'a
$|\bar A_1(\oo)\cup\cdots\cup\bar A_n(\oo)|
=I_{A_1\cup\cdots\cup A_n}(\oo)$. Teh\'at 
$I_{A_1\cup\cdots\cup A_n}(\oo)=\bar S_1(\oo)-\bar S_2(\oo)
+\bar S_3(\oo)-\cdots +(-1)^{n+1}\bar S_n(\oo)$. 
Mivel $E\bar S_k(\oo)=S_k$. $1\le k\le n$, a fenti azonoss\'agban
v\'arhat\'o \'ert\'eket v\'eve megkapjuk a
$P(A_1\cup\cdots\cup A_n)=S_1-S_2+S_3-\cdots +(-1)^{n+1}S_n$
azonoss\'agot. A val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi 
szita formul\'aban fel\'{\i}rt egyen\-l\H{o}t\-len\-s\'e\-gek 
hasonl\'oan bizony\'{\i}that\'oak. A
$$
\sum_{k=1}^{2l}(-1)^{k+1}\bar S_k(\oo)\le
I_{A_1\cup \cdots\cup A_n}(\oo)\le \sum_{k=1}^{2l-1}(-1)^{k+1}\bar S_k(\oo)
$$
egyenl\H{o}tlens\'eget kell fel\'{\i}rni a kombinatorikus szita formula
seg\'{\i}ts\'eg\'evel, \'es v\'arhat\'o \'ert\'eket kell venni ebben
a rel\'aci\'oban.

\beginsection 1.~kieg\'esz\'{\i}t\'es. {\it A
val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formula
\'es annak egy \'altal\'anos\'{\i}t\'asa.}

A val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formula egy
olyan bizony\'{\i}t\'as\'at ismertetem, amely egy \"onmag\'aban
is \'erdekes, \'es m\'as esetekben is alkalmazhat\'o eredm\'enyen
alapul. Ezt az al\'abbi lemm\'aban fogalmazom meg.

\medskip\noindent
{\bf Lemma.} {\it Legyenek adva valamely $A_1,\dots,A_n$ esem\'enyek
egy $(\Omega,\Cal A,P)$ val\'osz\'{\i}n\H{u}s\'egi mez\H{o}n, \'es
defini\'aljuk ezek felhaszn\'al\'as\'aval v\'eges sok uni\'o, metszet
\'es komplementer seg\'{\i}ts\'eg\'evel bizonyos
$B_j=f_j(A_1,\dots,A_n)$, $1\le j\le k$, esem\'enyeket.
R\"ogz\'{\i}ts\"unk valamely $c_1,\dots,c_k$ val\'os sz\'amokat. A
$$
\summ_{j=1}^kc_j P(B_j)=
\summ_{j=1}^kc_j P\(f_j(A_1,\dots,A_n)\)\ge0
$$
egyenl\H{o}tlens\'eg teljes\"ul tetsz\H{o}leges
val\'osz\'{\i}n\H{u}s\'egi mez\H{o}n defini\'alt tetsz\H{o}leges
$A_1,\dots,A_n$ halmazokra, ha speci\'alisan teljes\"ul abban a
($2^n$ sz\'am\'u) speci\'alis esetben, amikor mindegyik $A_j$ halmaz
vagy az $\Omega$ biztos vagy az $\emptyset$ \"ures esem\'eny.}

\medskip\noindent
{\it A lemma bizony\'{\i}t\'asa.}\/ Jel\"olje
$A_j^{-1}=\Omega\setminus A_j$ az $A_j$ halmaz komplementer\'et.
Vezess\"uk be az $A_j^1=A_j$ jel\"ol\'est, \'es jel\"olj\"on
$(k_1,\dots,k_n)$, $k_j=\pm1$, $1\le j\le n$, valamely $n$
hossz\'us\'ag\'u $\pm1$ sorozatot. \'Irjuk fel mindegyik
$B_j=f_j(A_1,\dots,A_n)$ esem\'enyt konjunkt\'{\i}v norm\'alforma
alakban. Felhaszn\'alva, hogy a konjunkt\'{\i}v norm\'alform\'aban
diszjunkt halmazok uni\'oja jelenik meg, a vizsg\'aland\'o
egyenl\H{o}tlens\'eg fel\'{\i}rhat\'o
$$
\summ_{(k_1,\dots,k_n)\colon\;  k_j=\pm1,\; j=1,\dots,n}
d(k_1,\dots,k_n)P\(A_{1}^{k_1}\cap\cdots\cap A_{n}^{k_n}\)\ge0
\tag A
$$
alakban alkalmas $d(k_1,\dots,k_n)$ egy\"utthat\'okkal. Az~(A)
egyenl\H{o}tlens\'eg ny\'{\i}lv\'an
\'erv\'enyes minden $A_1,\dots,A_n$ halmazrendszerre, ha
$d(k_1,\dots,k_n)\ge0$ minden $(k_1,\dots,k_n)$ argumentumra.
Ez\'ert el\'eg megmutatni, hogy amennyiben az~(A)
egyenl\H{o}tlens\'eg teljes\"ul minden olyan speci\'alis esetben,
amikor az $A_j$, $1\le j\le n$, halmazok mindegyike vagy az
$\Omega$ biztos vagy az $\emptyset$ \"ures esem\'eny, akkor
$d(k_1,\dots,k_n)\ge0$ az \"osszes $(k_1,\dots,k_n)$ argumentumra.

Ezt megmutatand\'o, r\"ogz\'{\i}ts\"unk egy $n$ hossz\'us\'ag\'u
$(k_1,\dots,k_n)$ $\pm1$ sorozatot, \'es de\-fi\-ni\-\'al\-juk
ennek seg\'{\i}ts\'eg\'evel $A_1,\dots,A_n$ halmazoknak azt a
sorozat\'at, amelyre $A_j=\Omega$, ha $k_j=1$, \'es $A_j=\emptyset$,
ha $k_j=-1$, $1\le j\le n$. Ezzel a v\'alaszt\'assal az (A) formula
baloldal\'an szerepl\H{o} kifejez\'es $d(k_1,\dots,k_n)$-nel
egyenl\H{o}, ez\'ert ez csak \'ugy lehet nem negat\'{\i}v, ha
$d(k_1,\dots,k_n)\ge0$. Mivel ezt az \'ervet minden lehets\'eges
$(k_1,\dots,k_n)$ $\pm1$ sorozatra alkalmazhatjuk innen
k\"ovetkezik a lemma \'all\'{\i}t\'asa.

\medskip\noindent
{\it A val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita formula
bizony\'{\i}t\'asa a lemma seg\'{\i}ts\'eg\'evel.}\/ A lemma
alap\-j\'an a val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi szita 
formula azonoss\'ag\'at elegend\H{o} abban a speci\'alis esetben
bel\'atni, ha mindegyik $A_j$ esem\'eny vagy a biztos vagy az 
\"ures esem\'eny. Ekkor ugyanis a szita formula azonoss\'ag\'aban
szerepl\H{o} kifejez\'esek bal \'es jobboldal\'an szerepl\H{o} 
formul\'ak k\"ul\"onbs\'eg\'er\H{o}l tudjuk, hogy az egyr\'eszt 
nagyobb vagy egyenl\H{o}, m\'asr\'eszt kisebb egyenl\H{o}, mint 
nulla. Ez\'ert az null\'aval egyenl\H{o}. Tekints\"uk azokat az
eseteket, amikor az $A_j$ esem\'enyek k\"oz\"ott $r$ darab biztos
\'es $n-r$ \"ures esem\'eny van, $0\le r\le n$. Feltehetj\"uk, hogy
$r\ge1$, mert $r=0$ eset\'en, amikor mindegyik $A_j$ esem\'eny az
\"ures halmaz, az azonoss\'ag mindk\'et oldala null\'aval
egyenl\H{o}. Ha $1\le r\le n$, akkor
$S_l=\binom rl$ az $1\le l\le r$ esetben, \'es $S_l=0$, ha $l>r$.
Ez\'ert az $1\le r\le n$ esetben a szita formula jobboldal\'an
\'all\'o kifejez\'es $\summ_{l=1}^r(-1)^{l+1}S_l=
\summ_{l=1}^r(-1)^{l+1}\binom rl=1-\summ_{l=0}^r(-1)^{l}\binom
rl=1-(1-1)^r=1$, a baloldali kifejez\'es pedig szint\'en
$P(A_1\cup\cdots\cup A_n)=P(\Omega)=1$.

Hasonl\'o meggondol\'asok alapj\'an a szita formul\'aban
megfogalmazott egyen\-l\H{o}t\-len\-s\'e\-gek igazol\'as\'ahoz 
el\'eg azt megmutatni, hogy $1-\summ_{l=1}^s(-1)^{l+1}\binom rl\le 0$,
azaz $\summ_{l=0}^s(-1)^l\binom rl\le 0$, ha $1\le s\le r$, \'es
$s$ p\'aratlan sz\'am, \'es $\summ_{l=0}^s(-1)^l\binom rl\ge 0$,
ha $1\le s\le r$, \'es $s$ p\'aros sz\'am. (A bizony\'{\i}tand\'o
\'all\'{\i}t\'as ezen redukci\'oj\'ahoz \'ugy jutunk a fenti lemma
seg\'{\i}ts\'eg\'evel, hogy $r$-val jel\"olj\"uk azon $A_j$
halmazok sz\'am\'at, amelyekre $A_j=\Omega$, \'es fel\'{\i}rjuk,
hogy mit jelent a lemma szerint bizony\'{\i}tand\'o
\'all\'{\i}t\'as ebben az esetben. Az $r=0$ esetben az
ellen\H{o}rizend\H{o} egyenl\H{o}tlens\'egek nyilv\'anval\'oan
teljes\"ulnek, mert ekkor minden tekintett kifejez\'es null\'aval
egyenl\H{o}.)

A bizony\'{\i}tand\'o egyenl\H{o}tlens\'egek k\"ovetkeznek az al\'abbi
tartalmasabb azonoss\'agb\'ol.
$$
\summ_{l=0}^s(-1)^l\binom rl=(-1)^s\binom{r-1}s, \quad 0\le s\le r.
$$
Ez azonoss\'ag ny\'{\i}lv\'anval\'o az $s=0$ esetben, az \'altal\'anos
esetben pedig az $s$ v\'altoz\'o szerinti indukci\'oval kapjuk, hogy
$\summ_{l=0}^s(-1)^l\binom rl=(-1)^{s-1}\binom{r-1}{s-1}+(-1)^s\binom rs
=(-1)^s\binom{r-1}s$.

Ismertetem a szita formula egy hasonl\'oan bizony\'{\i}that\'o 
\'altal\'anos\'{\i}t\'as\'at.

\medskip\noindent
{\bf A szita formula egy \'altal\'anos\'{\i}t\'asa.}
{\it Legyenek adva tetsz\H{o}leges $A_1,\dots,A_n$ ese\-m\'e\-nyek egy
$(\Omega,\Cal A,P)$ val\'osz\'{\i}n\H{u}s\'egi mez\H{o}n, \'es
vezess\"uk be az $N=N(\oo)$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot,
amely egyen\H{o} azon $j$ indexek sz\'am\'aval, amelyekre az 
$\oo\in A_j$ rel\'aci\'o teljes\"ul. Ekkor
$$
P(N=r)=\sum_{i=0}^{n-r}(-1)^i{i+r\choose i}S_{i+r},\quad
\text{minden } 0\le r\le n \text{ sz\'amra},
$$
ahol
$$
S_0=1,\quad S_k=\sum_{1\le i_1<\dots<i_k\le n}
P\(A_{i_1}\cap\dots\cap A_{i_k}\),\quad 1\le k\le n.
$$
Tov\'abb\'a ezen \"osszeg r\'eszlet\"osszegei felv\'altva als\'o
illetve fels\H{o} becsl\'est adnak a tekintett
val\'osz\'{\i}n\H{u}s\'egekre, azaz
$$
\sum_{i=0}^s(-1)^i{i+r\choose i}S_{i+r}\ge P(N=r)
\quad \text{ha } 0\le s\le n-r \text{ \'es } s
\text{ p\'aros sz\'am.}
$$
\'es
$$
\sum_{i=0}^s(-1)^i{i+r\choose i}S_{i+r}\le P(N=r)
\quad \text{ha } 0\le s\le n-r \text{ \'es } s
\text{ p\'aratlan sz\'am.}
$$
}

\medskip\noindent
{\it Megjegyz\'es.}\/ Mivel $P(N=0)=1-P(A_1\cup\cdots\cup A_n)$
\'es $S_0=1$ ez az eredm\'eny az $r=0$ esetben megegyezik a szita
formul\'aval.

\medskip\noindent
{\it A szita formula \'altal\'anos\'{\i}t\'as\'anak a
bizony\'{\i}t\'asa.}\/ A szita formula bizony\'{\i}t\'as\'ahoz
hasonl\'oan ebben az esetben is reduk\'alhatjuk a
bizony\'{\i}tand\'o \'all\'{\i}t\'as igazol\'as\'at arra a
speci\'alis esetre, amikor a tekintett $A_j$ esem\'enyek k\"oz\"ott
$k$ darab $\Omega$ biztos \'es $n-k$ darab \"ures esem\'eny van,
$0\le k\le n$. S\H{o}t, azt is feltehetj\"uk, hogy $k>r$. Ugyanis
$k<r$ eset\'en a fel\'{\i}rt azonoss\'ag illetve
egyenl\H{o}tlens\'egek mind a k\'et oldala 0-val, m\'{\i}g $k=r$
eset\'en 1-gyel egyenl\H{o}. Ugyanis $S_{r+i}=0$, ha $r+i>k$, ami
minden $i\ge 0$-ra teljes\"ul, ha $k<r$. Ez\'ert ebben az
esetben a tekintett azonoss\'ag \'es egyenl\H{o}tlens\'egek
jobboldal\'an 0 \'all. A $k=r$ esetben $S_{r+i}=0$, ha $i\ge1$,
\'es $S_{r+0}=1$. M\'asr\'eszt $P(N=r)=0$, ha $k\neq r$, \'es
$P(N=r)=k$, ha $k=r$. Ezekb\H{o}l az \'all\'{\i}t\'asokb\'ol
k\"ovetkezik az \'all\'{\i}t\'as fenti redukci\'oj\'anak a
jogoss\'aga.

M\'asr\'eszt a tekintett speci\'alis esetben (amikor pontosan $k$
darab biztos esem\'eny van, \'es a t\"obbi $n-k$ esem\'eny pedig
\"ures) $S_{r+i}=\binom k{r+i}$, \'es
$\binom{i+r}i\binom k{i+r}=\binom kr\binom{k-r}i$. Innen a
bizony\'{\i}tand\'o azonoss\'ag jobboldal\'an \'all\'o kifejez\'es
$$
\align
\sum_{i=0}^{n-r}(-1)^i{i+r\choose i}S_{r+i}
&=\sum_{i=0}^{n-r}(-1)^i{i+r\choose i}\binom k{r+i}
=\sum_{i=0}^{n-r}(-1)^i\binom kr\binom{k-r}i\\
&=\binom kr\sum_{i=0}^{k-r}(-1)^i\binom{k-r}i
=\binom kr\sum_{i=0}^{k-r}(1-1)^{k-r}=0,
\endalign
$$
ha $k>r$. Innen k\"ovetkezik, hogy a fel\'{\i}rt azonoss\'ag
val\'oban \'erv\'enyes. Az egyen\-l\H{o}t\-len\-s\'e\-gek
bizony\'{\i}t\'asa hasonl\'o, csak ebben az esetben a sz\'amol\'as
v\'eg\'en a $\summ_{i=0}^{k-r}(-1)^i\binom{k-r}i=0$ azonoss\'ag
helyett a szita formula bizony\'{\i}t\'asa sor\'an m\'ar igazolt
a $\summ_{i=0}^s(-1)^i\binom{k-r}i\ge0$, ha $0\le s\le k-r$
\'es $s$ p\'aros sz\'am, \'es
$\summ_{i=0}^s(-1)^i\binom{k-r}i\le0$, ha $0\le s\le k-r$ \'es $s$
p\'aratlan sz\'am egyenl\H{o}tlens\'egeket kell haszn\'alni.

\medskip
Bebizony\'{\i}tok egy hasonl\'o azonoss\'agot, amelyben a
$P(N\ge r)$ val\'osz\'{\i}n\H{u}s\'eget sz\'a\-mol\-juk ki az $S_k$
mennyis\'egek seg\'{\i}ts\'eg\'evel, azaz annak a
val\'osz\'{\i}n\H{u}s\'eg\'et, hogy legal\'abb $r$ darab $A_j$ 
esem\'eny k\"ovetkezett be. Megmutatom, hogy ez a formula 
egyszer\H{u}en  le\-ve\-zet\-he\-t\H{o} az el\H{o}z\H{o} 
eredm\'enyben bizony\'{\i}tott a $P(N=r)$ val\'osz\'{\i}n\H{u}s\'eget
kifejez\H{o} azo\-nos\-s\'ag\-b\'ol.

\medskip\noindent
{\bf Formula a $P(N\ge r)$ val\'osz\'{\i}n\H{u}s\'eg
kifejez\'es\'ere.} {\it A szita formula el\H{o}bb megfogalmazott
\'altal\'anos\'{\i}t\'as\'aban bevezetett jel\"ol\'eseket
alkalmazva fel\'{\i}rhatjuk a
$$
P(N\ge r)=\sum_{i=0}^{n-r}(-1)^i{i+r-1\choose i}S_{i+r},\quad
\text{minden } 1\le r\le n \text{ sz\'amra},
$$
azonoss\'agot, ahol
$$
S_0=1,\quad S_k=\sum_{1\le i_1<\dots<i_k\le n}
P\(A_{i_1}\cap\dots\cap A_{i_k}\),\quad 1\le k\le n.
$$
}
\medskip\noindent
{\it A formula bizony\'{\i}t\'asa.}\/ A k\'eplet $r=n$-re
\'erv\'enyes, mert $P(N\ge n)=S_n$, \'es az azonoss\'ag jobboldal\'an
\'all\'o kifejez\'es is ezzel egyenl\H{o} az $r=n$ esetben. (Ekkor
az \"osszeg csak az $i=0$ tagot tartalmazza.) Az azonoss\'agot $r$
szerinti backward indukci\'oval \'es a $P(N=r)$ kifejez\'esre m\'ar
bizony\'{\i}tott azonoss\'ag seg\'{\i}ts\'eg\'evel bizony\'{\i}tjuk
be. Ugyanis, ha az azonoss\'agot tudjuk $r+1$-re, akkor
fel\'{\i}rhatjuk a
$$
\align
P(N\ge r)&=P(N=r)+P(N\ge r+1)\\
&=\sum_{i=0}^{n-r}(-1)^i{i+r\choose i}S_{i+r}+
\sum_{i=0}^{n-r-1}(-1)^i{i+r\choose i}S_{i+r+1}
\endalign
$$
azonoss\'agot. Mivel
$\summ_{i=0}^{n-r-1}(-1)^i{i+r\choose i}S_{i+r+1}
=\summ_{i=1}^{n-r}(-1)^{i-1}{i+r-1\choose i-1}S_{i+r}$, innen azt
kap\-juk, hogy
$$
\align
P(N\ge r)
&=\sum_{i=1}^{n-r}(-1)^i\({i+r\choose i}-\binom{i+r-1}{i-1}\)S_{i+r}+S_r\\
&=\sum_{i=1}^{n-r}(-1)^i{i+r-1\choose i}S_{i+r}+S_r,
\endalign
$$
mivel $\binom{i+r}i=\binom{i-r-1}{i-1}+\binom{i+r-1}i$, \'es ezt az
azonoss\'agot kellett bizony\'{\i}tani.

\medskip
{\it Feladat:}
\medskip
\item{} Tekints\"uk a jegyzet elej\'en
megfogalmazott p\'eld\'at, \'es sz\'amoljuk ki az
\'altal\'anos\'{\i}tott szita formula seg\'{\i}ts\'eg\'evel
annak val\'osz\'{\i}n\H{u}s\'eg\'et, hogy pontosan $r$, $r\ge0$,
h\'azasp\'ar t\'ancol egy\"utt. Mi e val\'osz\'{\i}n\H{u}s\'eg
hat\'ar\'ert\'eke, ha $n\to\infty$?
\item{} {\it Megold\'as:}\/ Az eredeti feladat megold\'asa sor\'an
kisz\'amoltuk, hogy $S_k=\frac1{k!}$. Ez\'ert az
\'altal\'anos\'{\i}tott szita formula alapj\'an annak a
val\'osz\'{\i}n\H{u}s\'ege, hogy az $n$ h\'azasp\'arb\'ol \'all\'o
t\'arsas\'agban az egy\"utt t\'ancol\'o h\'azasp\'arok $N_n$ sz\'ama
pontosan $r$
$$
P(N_n=r)=\sum_{i=0}^{n-r}(-1)^i{i+r\choose i}S_{i+r}=
\sum_{i=0}^{n-r}(-1)^i{i+r\choose i}\frac1{(i+r)!}=
\frac1{r!}\sum_{i=0}^{n-r}(-1)^i\frac1{i!}.
$$

Innen
$$
\lim_{n\to\infty} P(N=r)=\frac1{r!}\sum_{i=0}^\infty(-1)^i\frac1{i!}
=\frac1{r!}\frac1e.
$$

\medskip\noindent
{\it Megjegyz\'es.}\/ Az el\H{o}z\H{o} feladat eredm\'enye speci\'alisan
azt jelenti, hogy a feladatban te\-kin\-tett egym\'assal t\'ancol\'o
h\'azasp\'arok sz\'am\'anak eloszl\'asa tart az 1 param\'eter\H{u} 
Poisson eloszl\'ashoz, ha $n\to\infty$.

\medskip
Tekints\"uk a k\"ovetkez\H{o} m\'odos\'{\i}tott feladatot. Legyen
adva $n$ h\'azasp\'ar, \'es t\'an\-col\-ja\-nak a feles\'egek 
egym\'as ut\'an egy v\'eletlen\"ul kiv\'alasztott f\'erfival \'ugy, 
hogy minden f\'erfit egyforma
val\'osz\'{\i}n\H{u}s\'eggel v\'alasztanak, \'es minden egyes ilyen
p\'arv\'alaszt\'as f\"uggetlen egym\'ast\'ol. (Lehets\'eges, hogy
lesz olyan f\'erj, amely t\"obbsz\"or, illetve olyan f\'erj, amely 
egyszer sem t\'ancolt.) K\'erd\'es: Mi annak a 
val\'osz\'{\i}n\H{u}s\'ege, hogy pontosan $r$ feles\'eg t\'ancolt 
a f\'erj\'evel? Mi ennek a val\'osz\'{\i}n\H{u}s\'egnek a 
hat\'ar\'ert\'eke r\"ogz\'{\i}tett $r$ sz\'amra, ha a 
h\'azasp\'arok $n$ sz\'ama tart a v\'egtelenhez?

Ezt a feladatot a benne szerepl\H{o} f\"uggetlens\'egi tulajdons\'agok
miatt k\"onnyen meg lehet oldani. Nevezetesen a keresett
val\'osz\'{\i}n\H{u}s\'eg \'ert\'eke 
$\binom nr\(\frac1n\)^r\(1-\frac 1n\)^{n-r}$, aminek a 
hat\'ar\'ert\'eke r\"ogz\'{\i}tett $r$ sz\'amra $n\to\infty$ 
eset\'en $\frac1{r!}e^{-1}$. (Vegy\"uk \'eszre, hogy 
$\(1-\frac 1n\)^{n-r}=\(1-\frac1n\)^{-r}\(1-\frac 1n\)^n\to e^{-1}$, 
\'es $\binom nr\(\frac1n\)^r\to\frac1{r!}$, ha $n\to\infty$.) 
 Egy\'ebk\'ent a kapott eredm\'eny a f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okra vonatkoz\'o Poisson
eloszl\'as\'u ha\-t\'ar\-elosz\-l\'as\-t\'e\-tel spe\-ci\'a\-lis esete, 
amely azt adja, hogy a keresett hat\'ar\'ert\'ek megegyezik annak a 
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-g\'e\-vel, hogy egy 
1 param\'eter\H{u} Poisson eloszl\'as\'u val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'o az $r$ \'ert\'eket veszi fel.

Teh\'at a tekintett k\'et feladatban ugyanaz a hat\'areloszl\'as
jelent meg. Ez a k\"ovetkez\H{o} t\'ennyel van kapcsolatban. Az
eredeti feladatban az a megk\"ot\'es, hogy az a f\'erj, akit
egyszer kijel\"oltek t\'ancpartnernek nem v\'alaszthat\'o 
m\'egegyszer t\'ancpartnernek a f\"ug\-get\-len 
p\'arv\'alaszt\'as bizonyos megszor\'{\i}t\'as\'at jelenti, de 
ez egy nagyon enyhe megszor\'{\i}t\'as. Ez\'ert a f\'erj\"ukkel 
t\'ancol\'o feles\'egek sz\'ama fel\'{\i}rhat\'o, mint olyan 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok \"osszege, amelyek ugyan
nem f\"uggetlenek, de majdnem azok. Ez\'ert \"osszeg\"uk hasonl\'o 
hat\'areloszl\'ast\'etelt teljes\'{\i}t, mint amilyennel a 
f\"uggetlen esetben tal\'alkoztunk.

\beginsection 2. kieg\'esz\'{\i}t\'es. {\it  A vizsg\'alt 
hat\'areloszl\'ast\'etel egy m\'as bizony\'{\i}t\'asa.}

Tanuls\'agos lehet megmutatni, hogy hogyan lehet egyszer\H{u}en 
(a szita formula haszn\'alata n\'elk\"ul) bebizony\'{\i}tani
azt, hogy az e jegyzet feladat\'aban vizsg\'alt egy\"utt 
t\'ancol\'o h\'a\-zas\-p\'a\-rok sz\'am\'anak a hat\'areloszl\'asa 
az 1 param\'eter\H{u} Poisson eloszl\'as, ha a h\'azasp\'arok 
sz\'ama tart a v\'egtelenhez.

A bizony\'{\i}t\'as a k\"ovetekez\H{o} k\'et lemm\'an alapul.

\medskip\noindent
{\bf 1.~lemma.} {\it Tekints\"uk a k\"ovetkez\H{o} feladatot. Egy 
est\'elyen megjelenik $n$
h\'azasp\'ar. Egy t\'ancmester, aki nem tudja, hogy kik
h\'azast\'arsak \'es kik nem, v\'eletlen m\'odon p\'arba rendezi a
f\'erfiakat \'es n\H{o}ket a t\'anc el\H{o}tt. Jel\"olje $T_n$ az
egy\"utt t\'ancol\'o h\'azasp\'arok sz\'am\'at. Mutassuk meg, hogy
$E\binom{T_n}k=\frac1{k!}$ minden $1\le k\le n$ sz\'amra.}

\medskip\noindent
{\bf 2.~lemma.} {\it Legyen $\zeta=\zeta_\lambda$ egy $\lambda$
param\'eter\H{u} Poisson eloszl\'as\'u val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o. Ekkor $E\binom\zeta k=\frac{\lambda^k}{k!}$ minden
$k=1,2,\dots$ sz\'amra}

\medskip\noindent
{\it 1. lemma bizony\'{\i}t\'asa.}\/ Vezess\"uk be minden
$1\le j_1<j_2<\dots<j_k\le n$ $k$ hossz\'us\'ag\'u sorozatra a
k\"ovetkez\H{o}
$\eta(j_1,\dots,j_k)$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot:
$\eta(j_1,\dots,j_k)=1$, ha a $j_1$-ik, $j_2$-ik,\dots $j_k$-ik
h\'azasp\'arok mindegyike egym\'assal t\'ancol, \'es
$\eta(j_1,\dots,j_k)=0$ egy\'ebk\'ent. Ekkor
$$
\binom {T_n}k=\summ_{1\le j_1<\cdots<j_k\le n}\eta(j_1,\dots,j_k),
$$
ahonnan
$$
E\binom {T_n}k=\summ_{1\le j_1<\cdots<j_k\le n}
E\eta(j_1,\dots,j_k).
$$
Viszont
$E\eta(j_1,\dots,j_k)=\frac{(n-k)!}{n!}$, ahonnan
$E\binom {T_n}k=\binom nk\frac{(n-k)!}{n!}=\frac1{k!}$, amint
\'all\'{\i}tottuk.

\medskip\noindent
{\it 2. lemma bizony\'{\i}t\'asa.}\/
$$
E\binom\zeta k=\summ_{n=k}^\infty\binom nk\frac{\lambda^n}{n!}
e^{-\lambda}=e^{-\lambda}\lambda^k
\summ_{n=k}^\infty \frac1{k!}\frac{\lambda^{n-k}}{(n-k)!}
=\frac{\lambda^k}{k!}
e^{-\lambda}\summ_{n=k}^\infty\frac{\lambda^{n-k}}{(n-k)!}
=\frac{\lambda^k}{k!}.
$$

Az 1. \'es 2. lemm\'ab\'ol k\"ovetkezik, hogy az 1. lemm\'aban 
defini\'alt $T_n$ valamint egy a 2. lemm\'aban tekintett
$\zeta=\zeta_1$ $\lambda=1$ param\'eter\H{u} Poisson eloszl\'as\'u
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok momentumaira \'erv\'enyes a
$\limm_{n\to\infty}ET_n^k=E\zeta^k$ azonoss\'ag minden 
$k=1,2,\dots$ sz\'amra.

Val\'oban, vegy\"uk \'eszre, hogy a
$E\binom{T_n}0=E\binom\zeta0=1$, ami az ott
megfogalmazott \'all\'{\i}t\'asok megfelel\H{o}je az `elfajul\'o'
$k=0$ esetben. Tov\'abb\'a megadhat\'o az $E\binom \eta k$ kifejez\'es
$E\binom \eta k=\frac1{k!}E\eta(\eta-1)\cdots(\eta-k+1)=\frac1{k!}
(E\eta^k+B_{k-1,k}E\eta^{k-1}+\cdots+B_{1,k}E\eta+B_{0,k})$
alak\'u form\'aban alkalmas $B_{j,k}$, $0\le j\le k-1$ konstansokkal. 
Ezen konstansok \'ert\'ekeit explicit m\'odon meg lehet adni, de 
erre nem lesz sz\"uks\'eg\"unk. Ebb\H{o}l a rel\'aci\'ob\'ol az is 
k\"ovetkezik, hogy az $E\eta^k$ momentumot ki lehet fejezni az 
$E\binom \eta j$, $0\le j\le k$, kifejez\'esek line\'aris
kombin\'aci\'ojak\'ent. Az $ET_n^k$ momentum hasonl\'oan kifejezhet\H{o}
az $E\binom {T_n}j$, $0\le j\le k$, kifejez\'esek line\'aris
kombin\'aci\'ojak\'ent ugyanazon egy\"utthat\'okkal. Ebb\H{o}l a
t\'enyb\H{o}l, illetve az 1. \'es 2. lemm\'ab\'ol k\"ovetkezik, hogy
$\limm_{n\to\infty}ET_n^k=E\zeta^k$ minden 
$k=0,1,2,\dots$ sz\'amra, amint \'all\'{\i}tottam.

Viszont a val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'as alapvet\H{o}
eredm\'enyeib\H{o}l k\"ovetkezik, hogy ha teljes\"ul a
$\limm_{n\to\infty}ET_n^k=E\zeta^k$ rel\'aci\'o  
minden $k=0,1,2,\dots$ sz\'amra \'es egy Poisson eloszl\'as\'u
$\zeta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ora, akkor a $T_n$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok eloszl\'asban
konverg\'alnak a $\zeta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ohoz.

Az, hogy eloszl\'asok momentumainak a konvergenci\'aj\'ab\'ol egy 
Poisson eloszl\'as\'u val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o 
momentumaihoz k\"ovetkezik az eloszl\'asok konvergenci\'aj\'a ezen
Poisson eloszl\'as\'u val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o 
eloszl\'as\'ahoz k\"ovetkezik a k\"ovetkez\H{o} h\'arom feladat 
ered\-m\'e\-nyei\-b\H{o}l. Val\'oj\'aban egy \'elesebb \'all\'{\i}t\'as
is k\"ovetkezik ezen feladatok ered\-m\'e\-nyei\-b\H{o}l. Az, hogy ha
eloszl\'asok egy sorozat\'anak minden momentuma konverg\'al egy 
olyan eloszl\'as megfelel\H{o} momentum\'ahoz, amelynek eloszl\'as\'at
egy\'ertelm\H{u}en meghat\'arozz\'ak momentumai, akkor az eloszl\'asok
sorozata konverg\'al ehhez az eloszl\'ashoz. 

\medskip
{\it 1. feladat:}

\item{} Legyen adva $\mu_n$, $n=1,2,\dots$, val\'osz\'{\i}n\H{u}s\'egi 
m\'ert\'ekek egy olyan sorozata, amelyre l\'etezik a
$\limm_{n\to\infty}\int x^k\mu_n(\,dx)=B_k<\infty$ hat\'ar\'ert\'ek
minden $k=1,2,\dots$ indexre. Ekkor
a $\mu_n$ sorozat relative kompakt, azaz minden
$\mu_{n_k}$ r\'eszsorozat\'anak van $\mu_{n_{k_j}}$ eloszl\'asban 
konvergens r\'eszsorozata.

\vfill\eject

{\it 2. feladat:}

\item{} Legyen adva $\mu_n$, $n=1,2,\dots$, val\'osz\'{\i}n\H{u}s\'egi 
m\'ert\'ekek egy olyan sorozata, amely eloszl\'asban konverg\'al egy
$\mu_0$ val\'osz\'{\i}n\H{u}s\'egi m\'ert\'ekhez, tov\'abb\'a amely\-re
l\'etezik a $\limm_{n\to\infty}\int x^k\mu_n(\,dx)=B_k<\infty$ 
hat\'ar\'ert\'ek minden $k=1,2,\dots$ indexre. Ekkor ez a 
hat\'ar\'ert\'ek teljes\'{\i}ti a $B_k=\int x^k\mu_0(\,dx)$ 
rel\'aci\'ot minden $k=1,2,\dots$ indexre.

\medskip
{\it 3. feladat:}

\item{} Legyen adva $\mu_n$, $n=1,2,\dots$, val\'osz\'{\i}n\H{u}s\'egi 
m\'ert\'ekek egy olyan sorozata, amely\-re 
$\limm_{n\to\infty}\int x^k\mu_n(\,dx)=\int x^k\mu_0(\,dx)$ minden 
$k=1,2,\dots$ indexre valamely $\mu_0$ 
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi m\'ert\'ekkel. Ha a $\mu_0$ 
m\'ert\'eket meghat\'arozz\'ak momentumai, akkor a $\mu_n$ sorozat 
eloszl\'asban konverg\'al a $\mu_0$ val\'osz\'{\i}n\H{u}s\'egi 
m\'ert\'ekhez.

\medskip
\item{} {\it Seg\'{\i}ts\'eg:} Az els\H{o} feladat megold\'as\'aban
a val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'as
\'altal\'anos eredm\'enyei alapj\'an el\'eg ellen\H{o}rizni, hogy minden
$\e>0$ sz\'amhoz l\'etezik olyan $K=K(\e)$ sz\'am, amelyre $\mu_n(x\colon\;
|x|>K)<\e$ minden $n=1,2,\dots$ indexre. Ez igaz, mert 
 a feladat felt\'etelei szerint $\int x^2\mu_n(\,dx)<B$ alkalmas 
$B>0$ sz\'ammal minden $n$ indexre.
\item{} A gyenge konvergenci\'ab\'ol k\"ovetkezik, hogy
$\limm_{n\to\infty}\int_{-A}^A x^k\mu_n(\,dx)=\int_{-A}^A x^k\mu_0(\,dx)$
minden olyan $A$ sz\'amra, amely folytonoss\'agi pontja a $\mu_0$
m\'ert\'eknek. Ahhoz, hogy a 2.~feladatot ennek alapj\'an $A\to\infty$ 
hat\'ar\'atmenettel megoldjuk el\'eg bel\'atni, hogy minden $k$ 
eg\'esz \'es $\e>0$ val\'os sz\'amra l\'etezik olyan $B=B(k,\e)$ 
sz\'am, amely\-re $\int_{x\colon\;|x|>B} |x|^k\mu_n(\,dx)<\e$ minden 
$n$ indexre. Viszont $\int_{x\colon\;|x|>B} |x|^k\mu_n(\,dx)<
\frac1{B^k}\int_{x\colon\;|x|>B} |x|^{2k}\mu_n(\,dx)<
\frac1{B^k}\int |x|^{2k}\mu_n(\,dx)<\e$ minden $n\ge1$ indexre, ha 
$B$ el\'eg nagy. N\'emi plusz munk\'aval l\'athat\'o, hogy ez a 
becsl\'es $n=0$ indexre is \'erv\'enyes.
\item{} A 3. feladat \'all\'{\i}t\'asa egyszer\H{u}en k\"ovetkezik az
els\H{o} \'es m\'asodik feladat eredm\'eny\'eb\H{o}l.
 

\bye

\item{2.)} Tekints\"uk az el\H{o}z\H{o} feladat k\"ovetkez\H{o}
m\'odos\'{\i}tott v\'altozat\'at. Egy est\'elyen ott van $n$
h\'azasp\'ar minden f\'erfi tagja. Egym\'as ut\'an megjelennek a
feles\'egek, akiket egy jelenlev\H{o} t\'ancmester megt\'ancoltat
egy \'altala v\'eletlen\"ul kiv\'alasztott f\'erfival. Minden
f\'erfit egyforma val\'osz\'{\i}n\H{u}s\'eggel v\'alaszt, \'es az
egyes v\'alaszt\'asok egym\'ast\'ol f\"ug\-get\-le\-nek. Jel\"olje
$\bar T_n$ azon feles\'egek sz\'am\'at, akik a f\'erj\"ukkel
t\'ancolnak. Sz\'amoljuk ki az $E\binom{\bar T_n}k$ kifejez\'es
v\'arhat\'o \'ert\'ek\'et minden $1\le k\le n$ sz\'amra. Mutassuk
meg, hogy $\limm_{n\to\infty}E\binom{\bar T_n}k=\frac1{k!}$ minden
$k=1,2,\dots$ sz\'amra.
\item{} {\it Megold\'as:}\/ Vezess\"uk be minden
$1\le j_1<j_2<\dots<j_k\le n$ $k$ hossz\'us\'ag\'u sorozatra a
k\"ovetkez\H{o} $\bar\eta(j_1,\dots,j_k)$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot:
$\bar\eta(j_1,\dots,j_k)=1$, ha a $j_1$-ik, $j_2$-ik,\dots
$j_k$-ik feles\'egek mindegyike a f\'erj\'evel t\'ancol, \'es
$\bar\eta(j_1,\dots,j_k)=0$ egy\'ebk\'ent. Ekkor

$$
\binom {\bar T_n}k=\summ_{1\le j_1<\cdots<j_k\le n}
\bar\eta(j_1,\dots,j_k),
$$
ahonnan
$$
E\binom {\bar T_n}k=\summ_{1\le j_1<\cdots<j_k\le n}
E\bar\eta(j_1,\dots,j_k).
$$
Viszont
$E\bar\eta(j_1,\dots,j_k)=\frac1{n^k}$, ahonnan
$E\binom {\bar T_n}k=\binom nk\frac{1}{n^k}
=\frac1{k!}\frac{n(n-1)\cdots(n-k+1)}{n^k}$. Innen l\'athat\'o,
hogy $\limm_{n\to\infty}E\binom {\bar T_n}k=\frac{1}{k!}$.







