所有自然数排成乱序的概率有多大 2011-08-06

所有的自然数参与排序,但都不在自己序号的位置(乱序)的概率。我们把上面这个问题具体化,并分为两步:n个球放入n个盒子内,要求是每个盒子内放且只放一个球,那么所有的球的编号和盒子的编号都不相同的概率是多少?当\(n\rightarrow\infty\)时这个概率是多大?

解法1

设f(n)为n个盒子放入n个球,且都不对号的方法种数。显然f(1)=0,f(2)=1,...下面研究f(n+1)的计算方法,考虑它与f(n)及f(n-1)的关系。

情况一:如果现有n个球已经按全部不对号的办法放好,放法种数为f(n)。取其中任意一种,将第n+1个球和第n+1个盒子拿过来,将前面n个盒子中的任一盒子(如第m个盒子)中的球(肯定不是编号为m的球)放入第n+1个盒子中,然后将第n+1个球放入刚才空出来的盒子中,这样的放法都是合理的,共有n*f(n)种。

情况二:在刚才的操作中,忽略了编号为m的球(它当时在第m个盒子中)放入第n+1个盒子中的情况!即第m个盒中编号为m的球放入第n+1个盒子中,且编号为n+1的球放入第m个盒子中,其余的n-1个球也都不对号。于是又有了n*f(n-1)种放法是合理的。

其他情况不可能有n个球中同时两个球对号入座了。而只调整一次,就使n+1个球全部不对号的。

综合以上f(n+1)=n*f(n)+n*f(n-1),f(1)=0,f(2)=1,递推可解出f(n)。

于是这个概率为f(n)/n!,当\(n\rightarrow\infty\)时,极限值为\(\frac{1}{e}\)

解法2

设n个球放入n个盒子中乱序的概率为p。(所有球不在其对应的盒子中)

那么,有任意个球放对了盒子的概率为1-p,又有如下

有1个球放对了盒子的概率为\(\frac{1}{1!}*p\)(剩下的球也是自然数那么多个)

有2个球放对了盒子的概率为\(\frac{1}{2!}*p\)(2个球有2!中方法,只有一种是全对号的)

$$\cdots\cdots$$

有n个球放对了盒子的概率为\(\frac{1}{n!}*p\)(n个球有n!种方法,只有一种是全对号的)

$$\cdots\cdots$$

一直到无穷,从而

$$\frac{1}{1!}\cdotp+\frac{1}{2!}\cdotp+\frac{1}{3!}\cdotp+\cdots+\frac{1}{n!}\cdotp+\cdots=1-p$$

从而变换得\(p=\frac{1}{e}\)

解法3

设\(p(n)\)为n个球乱序的概率,那么,对应地

$$1 = p(n)+\frac{1}{1!}p(n-1)+\frac{1}{2!}p(n-2)+\cdots+\frac{1}{(n-2)!}p(2)+\frac{1}{(n-1)!}p(1)+\frac{1}{n!}p(0)$$

$$1 = p(n-1)+\frac{1}{1!}p(n-2)+\cdots+\frac{1}{(n-3)!}p(2)+\frac{1}{(n-2)!}p(1)+\frac{1}({n-1)!}p(0)$$

$$\cdots\cdots$$

$$1 = p(2)+\frac{1}{1!}p(1)+\frac{1}{2!}p(0)$$

$$1 = p(1)+ \frac{1}{1!}p(0)$$

$$1 = p(0)$$

利用矩阵求逆易得\(p(n)=\sum_{k=0}^{n}\frac{(-1)^k}{k!}\rightarrow\frac{1}{e}\)



Powered by Jekyll on GitHub | ©2016 Meroa | Last modified: 2018-03-22