信封题目(错排题目)

陆子525630

来历：知乎
题目描写： 有 n 个分歧信封逐一对应 n 个分歧的函件，现将这 n 个函件打乱，随机放入 n 个信封里面，问：任何的信都没被正确装入的几率？

一、 常规思维

易得样本空间 \Omega 中样本点数为 n! 个，现斟酌错排的样本数：
界说 n 个数字排在 n 个位置上，没有一个位置上的数字与位置对应的排法总数记做 D_n; D_1=0,D_2=1 ，例如：斟酌 n=3 的情况， \Omega_3=\{(3,1,2),(2,3,1)\};D_3=2 也就只要这两种错排的方式。
斟酌第一个数字 1 ，它在错排里可以有 \color{fuchsia}{(n-1)} 种位置，即除了第一个位置，它哪儿都能去：
无妨记 1 到了第 k 位 (1\ne k\leq n) ，
①： 1 和 k 对换了。 (k,...,1,...)
比如说 k=2 ,也就是说1 和 2 对换，那末这类情况下的错排序列前两个数字就是 (2,1,...) ，酱紫，还剩下 (n-2) 个数字的整体错排。总数也就是 \color{blue}{D_{n-2}}
②： 1 并未和 k 对换。 (...,1,...)
这样，还剩下 (n-1) 个空位， (n-1) 个数字，要留意这里要解除 k 和 1 对换的情况，由于前面已经斟酌过了，回首 D_n 的界说： n 个数字，都不在「原本的位置」，即肆意的 i 都不在第 i 位。由于还剩下 (n-1) 个数字和空位，除了 k 之外，其他 (n-2) 个数字的以及它们的位置都没被占据（我们晓得这类情况下，最少有 D_{n-2} 种排法被包括）， 由于这类情况下 k 不能呆在第 1,k 号位，其他肆意数字 i 也都不能排在 i,k 号位置，无妨将第 1 号位当做 k 的初始位置(归正大师伙都不能去 k  号位了)，这类情况下实在就是 (n-1) 个数字的错排，有 \color{purple}{D_{n-1}} 种。
是以，可以得出：
D_n = \color{fuchsia}{(n-1)}( \color{purple}{D_{n-1}}+ \color{blue}{D_{n-2}})
不丢脸出，这个数列经太重新整理，获得
\begin{eqnarray*} D_n-nD_{n-1}&=&(-1)[D_{n-1}-(n-1)D_{n-2}]\\ &=&(-1)^{n-2}(D_{2}-2D_1)\\ &=&(-1)^{n} \end{eqnarray*}
欲获得一般表达式，经过简单的1次迭代发现：：
\begin{eqnarray*} D_n&=&nD_{n-1}+(-1)^{n}\\ &=&n[(n-1)D_{n-2}+(-1)^{n-1}]+(-1)^n \end{eqnarray*}
为找到迭代纪律，整理上式获得
D_n=n(n-1)D_{n-2}+n(-1)^{n-1}+(-1)^n
所以找到了迭代纪律以下：(迭代的成果分为两个部分，红色和粉色)
\begin{eqnarray*} D_n&=&\color{fuchsia}{n(n-1)···2*D_1}+\color{red}{(-1)^n+n(-1)^{n-1}+n(n-1)(-1)^{n-2}+...+n···3*(-1)^2}\\ &=&n!  \color{blue}{  [\frac{(-1)^n}{n!}+\frac{(-1)^{n-1}}{(n-1)!}+...+\frac{(-1)^3}{3!}+\frac{(-1)^2}{2!}]} \end{eqnarray*}
至此， D_n 我们就算出来了，不难发现，蓝色部分实在就是 e^x 在 0 处的泰勒展开，即
e^{-1}=\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!} \quad \quad (n\rightarrow \infty)
故，当人数越来越多的时辰，全数排错的几率会收敛至 e^{-1} 即：
P=\frac{\text{card}\{D_n\}}{\text{card}\{\Omega\}}=e^{-1}  \quad \quad (n\rightarrow \infty)
二、小捷径

记 A_i 为「第 i 封信被争取地装入了」这一事务，不难发现：
P(A_i)=\frac{1}{n};P(A_j|A_i)=\frac{1}{n-1}\Rightarrow P(A_iA_j)=\frac{1}{n(n-1)} \quad (i\ne j)
那末我们立马就晓得：
P(A_1A_2···A_n)=\frac{1}{n!} 且
P(\bigcap_{i=1}^k A_{x_i})=\frac{1}{n(n-1)···(n-k+1)}
按照几率的加法公式：
P(\bigcup_{i=1}^\infty A_i)=\sum^{n}_{i=1}P(A_i)-\sum_{1\leq i<j\leq n}P(A_iA_j)+...+(-1)^{n-1}P(A_1A_2...A_n)
可以获得
1-P(\bigcup_{i=1}^n A_i)  =1-\binom{n}{1}\frac{1}{n}+\binom{n}{2}\frac{1}{n(n-1)}+...+(-1)^{n}\frac{1}{n!}=e^{-1}

原文地址：https://zhuanlan.zhihu.com/p/519994119
免责声明：本帖内容由机械人自动收集于互联网，如加害了您的权益，请联系我们【E-Mail:cb@yoyodoc.com】 我们会实时删除侵权内容，给您带来未便，深感歉意！

绣绣仙女酌

计较标记公式PDF天生器你值得具有[酷]