Problema degli accoppiamenti

Dato $(\Omega ,\mathbb{P})$ uno schema probabilistico. Sia $f:\{1,2,...,n\}\to \{1,2,...,n\}$ biettiva, allora $i\in \{1,2,...,n\}$ è un punto fisso se $f(i)=i$, calcolare la probabilità che una permutazione casuale non abbia punti fissi.

• $\Omega =\{({\omega }_1,{\omega }_2,...,{\omega }_n)\mid {\omega }_i\in \{1,2,...,n\}\wedge i\ne j⟹{\omega }_i\ne {\omega }_j\}⟹|\Omega |=n!$
• $\mathbb{P}$ è la probabilità uniforme su $\Omega$

Codifichiamo l'evento di cui si vuole calcolare la probabilità

$$E=\{({\omega }_1,{\omega }_2,...,{\omega }_n)\mid {\omega }_i\in \{1,2,...,n\}\wedge i\ne j⟹{\omega }_i\ne {\omega }_j\wedge {\omega }_i\ne i\}$$

Questo è un problema per cui il passaggio a complemento si pone come una buona soluzione, per cui

$$A=E^{\complement }=\{({\omega }_1,{\omega }_2,...,{\omega }_n)\mid {\omega }_i\in \{1,2,...,n\}\wedge \exists i\in \{1,2,...,n\}:{\omega }_i=i\}$$

Ora è possibile scrivere

$$A=\bigcup _{k=1}^n{A}_k\mid A_k=\{({\omega }_1,{\omega }_2,...,{\omega }_n)\mid {\omega }_i\in \{1,2,...,n\}\wedge i\ne j⟹{\omega }_i\ne {\omega }_j\wedge {\omega }_k=k\}$$

Dato che, per simmetria, gli eventi $A_k$ hanno la stessa cardinalità, basta calcolare $|A_1|$

$$\begin{gathered} A_1=\{({\omega }_1,{\omega }_2,...,{\omega }_n)\mid {\omega }_i\in \{1,2,...,n\}\wedge i\ne j⟹{\omega }_i\ne {\omega }_j\wedge {\omega }_1=1\}⟹ \\ ⟹|A_1|=(n-1)!⟹\mathbb{P}(A_1)=\frac{|A_1|}{|\Omega |}=\frac{(n-1)!}{n!}=\frac{1}{n} \end{gathered}$$

Il problema è che gli eventi $A_1,A_2,...,A_n$ non sono disgiunti, quindi bisogna usare il PIE per calcolare la cardinalità dell'unione, per cui servono le intersezioni

$$\begin{gathered} A_1\cap A_2= \\ =\{({\omega }_1,{\omega }_2,...,{\omega }_n)\mid {\omega }_i\in \{1,2,...,n\}\wedge i\ne j⟹{\omega }_i\ne {\omega }_j\wedge {\omega }_1=1\wedge {\omega }_2=2\}⟹ \\ ⟹|A_1\cap A_2|=(n-2)!⟹ \\ ⟹\mathbb{P}(A_1\cap A_2)=\frac{|A_1\cap A_2|}{|\Omega |}=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)} \end{gathered}$$

È possibile generalizzare per l'intersezione di $A_1,A_2,...,A_{\mu }$ eventi, con $\mu \le n$

$$\begin{gathered} A_{\mu }=\bigcap _{1\le l_1<l_2<\cdots <l_{\mu }\le n}{A}_{l_i} \\ =\{({\omega }_1,{\omega }_2,...,{\omega }_n)\mid {\omega }_i\in \{1,2,...,n\}\wedge i\ne j⟹{\omega }_i\ne {\omega }_j\wedge {\omega }_{l_i}=l_i\}⟹ \\ ⟹|A_{\mu }|=(n-\mu )!⟹ \\ ⟹\mathbb{P}(A_{\mu })=\frac{|A_{\mu }|}{|\Omega |}=\frac{(n-\mu )!}{n!}=\frac{1}{n(n-1)\cdots (n-\mu +1)} \end{gathered}$$

Ora è possibile usare il PIE per ricavare la sommatoria completa

$$\mathbb{P}(\mathbb{A})=$$

TODO: completare