For $1\le i_1,i_2,…,i_k\le N$ denote
$$p_{i_1,…,i_k}=\Pr(A_{i_1}\cap A_{i_2}\cap\dots\cap A_{i_k}),$$
$$S_k=\sum\limits_{1\le i_1\le\dots\le i_k\le N}p_{i_1,\dots,i_k}.$$Show that the probability $P_{[m]}$ that exactly $m$ among the $N$ events $A_1,\dots,A_N$ occur simultaneously is given by
$$P_{[m]}=S_m-\binom{m+1}{m}S_{m+1}+\binom{m+2}{m}S_{m+2}-\dots (-1)^{N-m}\binom{N}{m}S_{N}.$$
We've already proven the inclusion exclusion formula: $$\Pr\left(\bigcup\limits_{i=1}^NA_i\right)=S_1-S_2+S_3-\dots (-1)^{N-1}S_N,$$
but the problem is the factors $\binom{m+1}{m}…$ before $S_i$'s, I cannot really show that.
Best Answer
Define $B_{m,N}:=\left\{\omega,\sum_{j=1}^N\mathbf 1_{A_j}(\omega)=m\right\}$ and denote $[N]:=\{1,\dots,N\}$ and $|J|$ the cardinal of a subset of $[N]$. We first use pointwise equalities of indicator functions. We have, using at the second step the pointwise equality which leads to the inclusion exclusion formula,
\begin{align} \mathbf 1\left(B_{m,N}\right)&=\sum_{\substack{J\subset [N]\\ |J|=m}}\mathbf 1\left(\bigcap_{j\in J}A_j\right)\cdot \left(1-\mathbf 1\left(\bigcup_{j\in J^c}A_j\right)\right)\\ &=\sum_{\substack{J\subset [N]\\ |J|=m}}\mathbf 1\left(\bigcap_{j\in J}A_j\right)\cdot \left(1- \sum_{l=1}^{N-m}(-1)^{l-1}\sum_{\substack{K\subset [N]\setminus J\\ |K|=l}}\mathbf 1\left(\bigcap_{k\in K}A_k\right)\right)\\ &=\sum_{\substack{J\subset [N]\\ |J|=m}}\mathbf 1\left(\bigcap_{j\in J}A_j\right) +\sum_{l=1}^{N-m}(-1)^l\sum_{\substack{J\subset [N]\\ |J|=m}}\sum_{\substack{K\subset [N]\setminus J\\ |K|=l}}\mathbf 1\left(\bigcap_{j\in J\cup K}A_j\right). \end{align} Now, we take expectations: the first term is $S_m$. For $1\leqslant l\leqslant N-m$, notice that a subset of $l+m$ elements of $[N]$ can be written in $\binom{m+l}m$ ways as the union of two disjoint elements of cardinality $m$ and $l$ respectively, hence $$\sum_{\substack{J\subset [N]\\ |J|=m}}\sum_{\substack{K\subset [N]\setminus J\\ |K|=l}}\mathbb P\left(\bigcap_{j\in J\cup K}A_j\right)=\binom{m+l}mS_{m+l}.$$