[挑战]再看傻子坐飞机问题，看看你能达到的高度！
近来一道傻子坐飞机问题，引起版内众多朋友的关注，本帖的目的是构造性解决此问题，有兴趣的朋友可以耐心的看下。当然，如果你连最后一个上飞机坐在自己位置上的概率恒为1/2都没还搞清楚，就不用浪费时间看此帖了~~。
先把题目抄下：
100个人排队乘坐有100个座位的飞机，正常情况时每个都都会对号入坐，但是，第一个上飞机的是个傻子，他随机坐了一个位子，接下来的人上飞机时，如果自己座位被人坐了就会随机找个座位坐下，否则就坐自己坐位。
用大写N表示常量：总共上飞机的人数，下同。
设p(k;N)表示第k个人上飞机后坐在自己座位上的概率，则：
1/N （k=1)
p(k;N)=
(N-k+1)/(N-k+2) (2 <=k <=N)
易见，原题要证明的结论就是,当k=N时候，概率表达式退化为1/2。
因为我的证明是构造性的，步骤比较多，我得先把我的证明过程做一个简单的概括，让大家先明白我的思路：
1、用图论的思想对题目做一数学抽象。
2、定义占座链{k1,k2,---,1},其中k1 <k2 <---,其数学含义为第1个人（傻子）占了第k1个人的座位，第k1个人占了k2的座位，等等。
3、每一个上飞机可能的序列与占座链一一对应。
4、存在2^(N-1)种不同的上飞机序列的可能性（这些可能性并不等概率出现）
5、第k人坐在自己的座位上，当且仅当占座链中不含k。
6、在所有2^(N-1)种上飞机序列中，k出现在其中的概率刚好为一半。
7、求p(k;N),就是计算k不出现的2^(N-2)项的概率和，公共分母为N!
*8、当k> =2时，证明：
(N-1)/N (k=2)
p(k;N)=
p(k-1;N)*((N-k+2)^2-1)/(N-k+2)^2 (k> 2)
由8的递归条件和初始条件，可以直接推出我要证明的结论。
因为概率表达式子的和式的项成几何增长，我在举例说明的时候以N=4。
证明
1、假设p是满足题目要求的一个N全排列，如1234表示第一个人做1号位置,以此类推，傻子编号为1,全部满足题目要求的排列集合为{p};
1-1、当第k个人上飞机的时候，他不可能做到编号为2到k-1的座位上。
证明：假设他能坐到第i个坐位上（2 <=i <=k-1),则表示，第i个人上飞机的时候，第i个座位是空着的，那么他就该坐到第i个座位上，则第k个人不可能坐到i号上。
推论1：第N个人上飞机的时候，他只能坐在1号或者N
1-2、用k1,k2等表示第n个人，若Pi占了Pj的座位，则做有向边ki-> kj.形成有向图G,满足:
G中任意顶点的度：入度和出度同为1或度为0
G中最多存在一个连通分部（G ')，包含2个或2个以上的顶点，且k1属于G '
由以上两点，可知若G '存在，则构成一单向连通的循环链,若不存在,则补充 定义G '只包含P1.
2、定义p中的一个错排序列s,满足：
（1）第一个元素在序列头，1在序列中结尾
（2）除1外，序列中其他元素单调递增加
（3）p中不存在比s更长的满足定义的序列
举例：p=1234,s=1;
p=2134,s=21
p=3214,s=31
p=2314,s=231
p=2341,s=2341
易见，s的实际意义就是一个排列中，没有坐在自己座位上的的人的一个“循环占坐链”，在排列2314中，s=231，表示第1个人占了2号座位，第2个人占了第3个座位，而第3个人占了1号座位。也就是2中定义的单向循环链G '
3、p和s存在一一对应关系。
p-> 唯一s,已经在2中证明了,s-> p,也很显然，因为N中不在s中的数字，必然要在自己原来的位置上，这个排列当然是唯一的。
4、所有可能上飞机序列的个数：
由s的产生，可知s为2到N的一个全组合并上{1},由二项定理，可知对于N,满足的组合总数为2^(N-1)
5、第k人坐在自己的座位上，当且仅当占座链中不含k。
结论显然。k没有坐在别人座位上，当然只能坐在自己的位置上。
6、在所有2^(N-1)种上飞机序列中，k出现在其中的概率刚好为一半。
依然是利用组合原理，在n个数的全组合中，k出现的次数刚好为一半。
7、由6可知，k不出现的情况共有2^(N-2)项，计算这些项的和及为k坐在自己座位上的概率。
*8、当k> =2时，证明：
(N-1)/N (k=2)
p(k;N)=
p(k-1;N)*((N-k+2)^2-1)/(N-k+2)^2 (k> 2)
呵呵，关键的地方到了，这一步的证明比较复杂，我怕说不清楚，以N=4举例证明，先给出N=4时所有可能的上飞机的序列：
1234 {1}
2134 {2,1}
3214 {3,1}
4231 {4,1}
2314 {2,3,1}
3241 {3,4,1}
2341 {2,3,4,1}
{}给出的是对应的占座序列，从概率的角度出发，很容易得到每个序列的概率表达式为:
1/n-i+1
p(s)=∏（ki)
1
其数学含义是，如果ki在占座链中，那么他就在剩下的n-k+1个座位中随便找个坐下，如果没有，他就以概率1坐在自己的座位上。为方便通分，将1表示为(n-i+1)/(n-i+1),任意序列的出现概率分母为N!,分子为一连乘，其分子连乘的个数满足q：
q+|s|=N,|s|为占座链中包含的元素个数。
要直接计算这2^(N-2)项的和是十分困难的，但我们还有一个条件可以利用，就是第2个人坐在自己座位上的概率为(N-1)/N;
当N=4时，计算p(2;4)和p(3;4),表达式为：
p(2;4)=(3!+3*2+3*1+3)/4!;
P(3;4)=(3!+3*2+2*1+2)/4!;
易见，p(k;N)中分子的每一项均有（N-k+1);
可以证明，p(k;n)表达式就是将p(k-1;n)中同时含有N-k+1和N-(k-1)+1的项不动（它的实际意义是什么，想一想~~），将p(k-1;n)不含有N-k+1的项目中，所有N-(k-1)+1替换为(N-k+1)。
这一步可以有两种证明：实际意义和组合原理，实际意义比较烦琐，组合原理可以看到这2^(N-2)项构成其实是对{N-1}/k这N-2个数做一次全组合，将每种组合的数连乘后在累加，再下一次组合的时候，就是将k替换为k+1。
在p(k;N)中，含n-(k+1)+1的项占一半（再次运用组合原理），其部分和占p(k;N)的(n-(k+1)+1)/((n-(k+1)+1)+1)=(n-k)/(n-k+1)
故p(k;N)=p(k-1;N)*((n-(k-1))/(n-(k-1)+1)+(n-k+1)*((n-k+1)/(n-k+2)))
简化后，得p(k;N)=p(k-1;N)*((N-k+2)^2-1)/(N-k+2)^2。
式子比较复杂，还是以数字举例
p(2;4)=(3!+3*2+3*1+3)/4!;
P(3;4)=(3!+3*2+2*1+2)/4!;
在p(2;4)中有2（N-(k+1)+1)的项为3！和3*2，其和占p(2;4)的2/（1+2），在计算p(3;4)的时候，这部分是共有的，故：
p(3;4)=p(2;4)*(2/3+1/3*(4-3+1)/(4-3+2))
=p(2;4)*8/9
=3/4*8/9
=2/3;
证毕。
[解决办法]
呵呵，有那么复杂么？
假设，n个人，第一个人随机作，最后一人正确作的概率为P(n)
则， P（n)=[p(n-1)+p(n-2)+....+p(1)]/(n-1)
又p(1)=0,p(2)=1/2
易知P（n)=1/2
[解决办法]
有点难度，研究一下
[解决办法]
哇～～
楼主 数学挺强！！
[解决办法]
学习下..
[解决办法]
恩，果然是1/2
这句话：“接下来的人上飞机时，如果自己座位被人坐了就会随机找个座位坐下，否则就坐自己坐位。”
当时考虑了所有人都随机的情况
[解决办法]
不管有多少人 都可以看成 三个部分
傻子 最后一个人 其他人
其他人作为一个整体
傻子作到 其他人的 位子 则 其他人 中必有一人 坐傻子或 最后一个人的位子
可以简化问题
答案 是 1/2
[解决办法]
这个问题早已经在版内详细解答过了，没有必要
[解决办法]
看了LZ的分析 ，我的头好晕啊。。。。。。。
个人觉得wjt2000(堂堂正正做男人) 说的有道理：
其实说白了 就是3个位置 ， 傻子 ， 中间人 ， 最后一个人 ， 其他的97人都是烟雾弹迷惑人的，因为98个人里面只要有1个人坐到傻子的位置上 ，那么最后一个人就会坐到自己的位置上，所以我认为是1/2的概率。
[解决办法]
wjt2000(堂堂正正做男人)说的非常对，非常佩服，当然上面证明一大堆应该也是正确的，数学也是超强呀！！！
[解决办法]
主要是看所有可能的坐法里面最后一个人坐到自己的位置的坐法有多少
傻子恰好坐到自己的位置，则只有一种坐法，这时最后一个人会坐到自己的位置；
傻子恰好坐到最后一个人的位置，也只有一种坐法，这时最后一个人会坐不到自己的位置；
傻子坐到第二个人的位置时，第二个人就变成了傻子(这时可以把第一个傻子的位置看成第二个傻子本来应该坐的位置)，以此类推。
设人数为 n，分别记为：
1 2 3 ... n-2 n-1 n
各人坐到谁的位置就用谁的位置号表示，则所有可能的坐法如下：
1 2 3 ... n-2 n-1 n
n 2 3 ... n-2 n-1 1
2 1 3 ... n-2 n-1 n
2 n 3 ... n-2 n-1 1
2 3 1 4 ... n-2 n-1 n
2 3 n 4 ... n-2 n-1 1
......
2 3 4 5 ... n-1 1 n
2 3 4 5 ... n-1 n 1
3 2 1 4 ... n-2 n-1 n
3 2 n 4 ... n-2 n-1 1
......
n-1 2 3 ... n-2 1 n
n-1 2 3 ... n-2 n 1
看最后一列，很明显几率是 1/2
[解决办法]
to:dkight(黑剑)
哦，何以见得？：）
-------------------
呵，那你问上帝好了！：（
--------------------------
写下我的写的公式：
1*（2*2...*2）/2*（2*2*....*2）括号里边的都是99个相乘
说明下，为什么是这样的结果
1。首先要知道的是最后一个人Z只能出现在第一个位置跟最后一个位置
证明：假设Z坐到了第i个位置，那么i以前的位置都是随机的(也就说说I只能坐到i以后的位置）当I做到了i以后的位置，那么最终有一个Z以前的人坐到了Z的位置，这个人只能有傻子，不然的话，Z以前的人坐到了Z的位置而Z坐到了以前的人的位置！
所以Z坐到自己位置的事件总数是p(1,1)乘以（第Z-1人） 的所有事件总数
[解决办法]
提个简单的方法，大家看看对不对：
首先，我们可以把它看成是一个傻子接力的问题，看最有一个人接到傻子的概率；
那么，我不管有多少个人，我只关心最后两个人(A、B。B是最后一个)，传到他们两个当傻子的概率都是1/2;
1/2可能传到A 当传到A 1/2可能 A 座对 则 B座对 =〉1/2 * 1/2 = 1/4;
1/2可能传到B 当传到B 1/2可能 B 座对 =〉1/2 * 1/2 = 1/4;
综合 1/4 + 1/4 = 1/2；
所以最后一个人座对的概率是 1/2；
[解决办法]
上面的回复让我当了一回傻子，纠正一下：
我们可以把它看成是一个挑选傻子的问题，n个人中有一个傻子，每次随即选一个拿出去，当选到傻子的时候，游戏结束。游戏结束的时候，拿出去的人的期望应该是n/2；所以任何一个人已经被拿出去的概率都是1/2;也就是座错座位的概率，也就知道了座对的概率。
[解决办法]
补充一点，这种方法只适用算最后一个人的概率！
[解决办法]
本来就是一增的机率嘛，要不坐对，要不坐错
