|
|
来历：知乎
一、错位全排列题目
什么是错位全排列题目？实在很简单，在生活中能够城市碰到：
“装错信封题目”是由那时最著名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(Danid Bernoulli，1700－1782)提出来的，大意以下：
一小我写了 n 封分歧的信及响应的 n 个分歧的信封，他把这 n 封信都装错了信封，问都装错信封的装法有几多种？ 为领会决这个看似简单的题目，我们从数学的角度动身，尝试几个常用的方式。
记装错 n 封信的品种为 D_n ，而且有 n 封信 a_1,a_2,...,a_n
（1）列举法（Enumeration method）计较种数
当 n 的值较小时，可以操纵列举法：
n=1 时，不成能装错信，则 D_1=0 ；
n=2 时，明显装错信时，只能够为两者更调位置，则 D_2=1 ；
n=3 时，有 (a_2,a_3,a_1) ， (a_3,a_1,a_2) 两种装法，则 D_3=2 ；
n=4 时，装法以下：
(a_2,a_1,a_4,a_3) ， (a_2,a_3,a_4,a_1) ， (a_2,a_4,a_1,a_3) ，(a_3,a_1,a_4,a_2) ， (a_3,a_4,a_1,a_2) ， (a_3,a_4,a_2,a_1) ，(a_4,a_1,a_2,a_3) ， (a_4,a_3,a_2,a_1) ， (a_4,a_3,a_1,a_2) ，则 D_4=9 。
当 n 的值越来越大时，列举会变得异常复杂。可以斟酌用排列数（Permutation）和组合数（Combination），来获得错位全排列的计较公式。
（2）排列组合计较种数
明显， n 封信的组合方式共有 A_n^n=n! 种装法，接下来我们要做的就是扣掉其中反复的品种，保证计数“不重不漏”。
假定第一封信装对，即为剩下的 n-1 个元素的一个全排列（All permutation），则有 A_{n-1}^{n-1}=(n-1)! 种装法；而且当第二封信装对时，也有 A_{n-1}^{n-1}=(n-1)! ，以此类推，每一封信装对时，都有 (n-1)! 种装法。
可是并不是只需扣掉装对一封信的情况。当第一封信和第二封信同古装对的时辰，就出现反复了。要扣掉反复的元素，就需要利用到高中课本中没有提到的“容斥道理”。
注：在部分材料上，排列数 A_n^m 也被写作 P_n^m 。
二、容斥道理（Principle of inclusion-exclusion）
在计数时，必须留意没有反复，没有遗漏。
为了使堆叠部分不被反复计较，人们研讨出一种新的计数方式，这类方式的根基思惟是：
先不斟酌堆叠的情况，把包括于某内容中的一切工具的数目先计较出来，然后再把计数时反复计较的数目排挤进来，使得计较的成果既无遗漏又无反复，这类计数的方式称为容斥道理。 容斥道理一般用在计较调集（Aggregate）的元素个数中。
（1）两个调集的容斥道理
设有两个非空调集 A,B ，记 |S| 为调集 S 中元素的个数，则有以下关系：
|A\cup B|=|A|+|B|-|A\cap B|
这在文氏图（Venn diagram）中实在是明显的：要计较调集 A\cup B 的元素的个数，首先把两调集 A 和 B 的元素个数相加。可是中心出现了反复的部分，也就是调集A\cap B 的元素个数，要从中扣除。
是以便有公式 |A\cup B|=|A|+|B|-|A\cap B| 。
（2）三个调集的容斥道理
推行到三个调集的情况下，公式要略加变形：设有三个非空调集 A,B,C ，则有以下关系：
|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B \cap C|
参照上面的分析，这个关系也是明显的，可是多斟酌到了调集 A\cap B \cap C 的元素个数。
（3）多个调集的容斥道理
推行到 n 个调集 A_1,A_2,...,A_n 中，有以下关系：
|A_1\cup A_2\cup ...\cup A_n|=\sum_{1\le i\le n}|A_i|-\sum_{1\le i < j \le n}|A_i\cap A_j|+...+(-1)^n|A_1\cap A_2\cap...\cap A_n|
在这里记 \bigcup_{i=1}^{n}A_i=A_1\cup A_2\cup ...\cup A_n ， \bigcap_{i=1}^{n}A_i=A_1\cap A_2\cap...\cap A_n
简化后获得 |\bigcup_{i=1}^{n}A_i|=\sum_{k=1}^{n}(-1)^{k-1}\cdot \sum_{1\le i_1<i_2<...<i_k\le n}|\bigcap_{j=1}^{k}A_{i_{j}}| ，此即为容斥道理。
三、一般计较公式
容斥道理是在调集合利用的，是以我们需要将“错位全排列”题目“翻译”一下。
设元素 a_1,a_2,...,a_n 的一个排列为 t_1,t_2,...,t_n ，使 t_i=a_i 的全排列的调集记为 A_i ，则 D_n=n!-|\bigcup_{i=1}^{n}A_i| ，接下来只要算出 |\bigcup_{i=1}^{n}A_i| 即可。
留意到当有一个元素“排对”时，剩下的 n-1 个元素停止全排列获得 |A_i|=(n-1)! ，而且这样满足要求的调集组共有 C_n^1=n 个；
当有两个元素“排对”时，剩下 n-2 个元素停止全排列获得 |A_i\cap A_j|=(n-2)! ，而且这样满足要求的调集组共有 C_n^2 个；
以此类推，到最初全数“排对”时，|A_1\cap A_2\cap ...\cap A_n|=0!=1 ，这样满足条件的调集组只要 C_n^n=1 个。
是以 |\bigcup_{i=1}^{n}A_i|=C_{n}^1(n-1)!-C_n^2(n-2)!+...+(-1)^{n-1}\cdot C_n^n0!
留意到对于 1\le i \le n ， C_n^i(n-i)!=\frac{n!}{i!}
是以 |\bigcup_{i=1}^{n}A_i|=\frac{n!}{1!}-\frac{n!}{2!}+...+(-1)^{n-1}\frac{n!}{n!}
=n!(\frac{1}{1!}-\frac{1}{2!}+...+(-1)^{n-1}\frac{1}{n!})=n!\cdot \sum_{i=1}^n\frac{(-1)^{i-1}}{i!}
所以 D_n=n!-|\bigcup_{i=1}^{n}A_i|=n!(1-\frac{1}{1!}+\frac{1}{2!}-...+(-1)^n\frac{1}{n!})
=n!(\frac{1}{2!}-...+(-1)^n\frac{1}{n!})
从上面我们获得的 D_n 的公式就会发现，为了计较错位全排序，还需要计较屡次阶乘。
当 n 越来越大的时辰，计较器凡是城市受不了，能否有方式可以简化计较？
四、级数（Series）与麦克劳林公式
留意到在上面的公式傍边，出现了这样的式子： 1-\frac{1}{1!}+\frac{1}{2!}-...+(-1)^n\frac{1}{n!} 。
记 S_n=1-\frac{1}{1!}+\frac{1}{2!}-...+(-1)^n\frac{1}{n!} ，我们用计较器来估量一下 S_n 的值。
当 n=3 时， S_3=\frac{1}{3}\approx0.3333 ；当 n=5 时， S_5=\frac{11}{30}\approx0.3667 ；
当 n=10 时， S_{10}\approx0.3678 。
当 n=50 时， S_{50}\approx0.3678794412 ，取对数得 \ln S_{50} \approx -1 ，是以 S_{50}\approx\frac{1}{e} 。
当n 的值越来越大的时辰， S_n 的值也会越来越接近 \frac{1}{e} 。
究竟上，在高档数学傍边，函数 f(x)=e^x 的麦克劳林公式（Maclaurin&#39;s series）以下：
e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x^n}{n!}+...
麦克劳林公式是泰勒公式（Taylor&#39;s formula）的一种特别形式。
数学中，泰勒公式是一个用函数在某点的信息描写其四周取值的公式。假如函数充足平滑的话，在已知函数在某一点的各阶导数值的情况之下，泰勒公式可以用这些导数值做系数构建一个多项式来近似函数在这一点的邻域中的值。泰勒公式还给出了这个多项式和现实的函数值之间的误差。
泰勒公式得名于英国数学家布鲁克·泰勒。他在1712年的一封信里初次论述了这个公式，虽然1671年詹姆斯·格雷高里已经发现了它的惯例。拉格朗日在1797年之前，最早提出了带不足项的现在形式的泰勒定理。 在原本的公式中，本应当不足项，暗示估量的误差巨细：
e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x^n}{n!}+R_n ，当 n 增大时，余项 R_n 趋近于 0 。
代入 x=-1 得： \frac{1}{e}=1-\frac{1}{1!}+\frac{1}{2!}-...+\frac{(-1)^n}{n!}+...
即 \lim_{n \rightarrow +\infty}{S_n}=\frac{1}{e} ，是以 S_n \approx \frac{1}{e} ，从这里动身，可以获得以下的估量公式。
五、估量公式
由以上的级数，可以获得 D_n \approx\frac{n!}{e} ，可是由于麦克劳伦公式是有一个“余项”存在的，总会有一定的误差。那末误差有多大呢？
记 f(n)=\frac{n!}{e},n\in N^+ ，接下来一样借助计较器来估量误差。
当 n=1 时， D_1=0 ，而 f(1)=\frac{1}{e}=0.3678...
当 n=2 时， D_2=1 ，而 f(2)=\frac{2}{e}=0.7357...
当 n=3 时， D_3=2 ，而 f(3)=\frac{6}{e}=2.2072...
当 n=4 时， D_4=9 ，而 f(4)=\frac{24}{e}=8.8291...
当 n=5 时， D_5=44 ，而 f(5)=\frac{120}{e}=44.145...
当 n=6 时， D_6=265 ，而 f(6)=\frac{720}{e}=264.87...
当 n=7 时， D_7=1854 ，而 f(7)=\frac{5040}{e}=1854.1...
从上面的数据可以看出，D_n 的值现实上是 f(n) 四舍五入的成果。是以可以将 D_n 改写成：D_n=[f(n)+\frac{1}{2}] ，其中 [x] 暗示不跨越 x 的最大整数。
所以获得估量公式：D_n=\left[ \frac{n!}{e}+\frac{1}{2} \right] 。
在平常计较傍边，利用此公式可以大大收缩计较时候，很是便当。
六、一点小补充
批评区有人提到，在求 D_n 的时辰可以用到递推的方式。
当 n\geq3 时，斟酌 n 个元素 a_1 ， a_2 ， \cdots ， a_n ，按照题目要求，我们晓得 a_n 不能放在第 n 个位置，故一共有 n-1 种挑选。假定 a_n 放在第 i 个位置，斟酌元素 a_i ，有两种情况。
若 a_i 与 a_n 更调位置，则只需斟酌剩下 n-2 个元素错位全排列的情况。
若 a_i 不放在第 n 个位置，则 a_i 也没法放在第 i 个位置，是以只需斟酌剩下 n-1 个元素错位全排列的情况。按照加法道理和乘法道理，可以获得： D_n=(n-1)\cdot(D_{n-1}+D_{n-2}) 。
又 D_1=0 ， D_2=1 ，因而可以用数学归纳法证实 D_n=n!\cdot(\frac{1}{2!}-...+(-1)^n\frac{1}{n!}) 。
或是可以采用以下方式： D_n=(n-1)\cdot(D_{n-1}+D_{n-2})
\Leftrightarrow (\frac{D_n}{n!}-\frac{D_{n-1}}{(n-1)!})=-\frac{1}{n}\cdot(\frac{D_{n-1}}{(n-1)!}-\frac{D_{n-2}}{(n-2)!}) ，令 x_n= \frac{D_{n+1}}{(n+1)!}-\frac{D_{n}}{n!} ，则 x_1=\frac{1}{2} ，且 x_{n}=-\frac{1}{n+1}\cdot x_{n-1} ，迭代得 x_n=(-1)^{n+1}\cdot\frac{1}{(n+1)!} 。
是以 \frac{D_{n+1}}{(n+1)!}-\frac{D_{n}}{n!}=(-1)^{n+1}\cdot\frac{1}{(n+1)!} ，累加得 \frac{D_{n+1}}{(n+1)!}=\sum_{k=2}^{n+1}(-1)^{k}\cdot\frac{1}{k!} ，是以可以获得通项公式为D_n=n!\cdot(\frac{1}{2!}-...+(-1)^n\frac{1}{n!}) 。
别的，@酱紫君 指出，近似计较的话间接对 \frac{\Gamma(1 + n, -1)}{e} 渐近展开, 0 阶是 \sqrt{2 \pi } e^{-n-1} n^{n+\frac{1}{2}} , 一阶是 \frac{1}{6} \sqrt{\frac{\pi }{2}} e^{-n-1} (12 n+1) n^{n-\frac{1}{2}}+\frac{(-1)^n}{n} ，留意到\sqrt{2 \pi } e^{-n-1} n^{n+\frac{1}{2}} 和 \frac{n!}{e}+\frac{1}{2} 的斯特林展开是等价的，也可以获得上面类似的成果。
原文地址：https://zhuanlan.zhihu.com/p/35318996
免责声明：
1、文章部分图片源于收集，均为表示图；
2、一切文章、图片、音频视频文件等材料版权归版权一切人一切；
3、因非原创文章及图片等内容没法和版权者联系，如原作者或编辑以为作品不宜上网供阅读，或不应无偿利用，请实时告诉我们，以敏捷采纳适当办法，避免给双方形成不需要的经济损失；
4、本页面内容由爬虫法式自动收集于互联网，如无意中加害了媒体或小我的常识产权，请电邮【E-Mail:cb@yoyodoc.com】告之，我们将于24小时内删除。 |
|
|Archiver|手机版|小黑屋|小悠文档创作分享社区
( 粤ICP备11072215号 )|网站地图
发表于 2023-2-22 19:47:10