关于“乘飞机的旅客领错行李”问题的非递归解答。

n个旅客，一人一件行李。下飞机后，一人各领取行李一件。问：有多少领取法，使n个旅客全都领错了行李？有多少领取法，只使m (m<=n) 个旅客领错了行李？

解：

设领取方法集合是U，领取方法个数，|U|= n!。

设X:“n个旅客全都领错了行李”的领取方法集合，Y:“n个旅客中有旅客领取了自己的行李” 的领取方法集合，则X 和 Y 是互不相容事件，X ⋂ Y = Æ。并且 X ⋃ Y = U。所以，|X|+|Y|=|U|= n!。

现在题目要求|X|，我们通过求|Y|来求|X|，|X|  = n! - |Y|。

将n个旅客从1到n编上号。

设Yi:“第i个旅客领取了自己的行李”的领取方法集合，这里1 <= i <= n。

则Y = ⋃[i=1 to n]Yi。

1 <= i1<= n，若第i1个旅客领取了自己的行李,其他n-1个旅客可以任取行李，则“第i1个旅客领取了自己的行李”的领取方法数 |Yi1| = (n-1)! 。一共有n个旅客，所以， ∑[i1]|Yi1| =  n*|Yi1| = n* (n-1)! = n!。

i1¹ i2，1 <= i1, i2 <= n，若第i1, i2个旅客领取了自己的行李,其他n-2个旅客可以任取行李，则“第i1, i2个旅客领取了自己的行李”的领取方法数 |Yi1⋂Yi2| = (n-2)! 。一共有C(n,2)旅客对，所以，∑[(i1,i2)]|Yi1⋂Yi2|  =  C(n,2)*|Yi1⋂Yi2| = n* (n-1) (n-2)! / 2! = n! / 2!  。

···

(i1, …, ik)是一组任意k个不同的数，1 <= i1, …, ik<= n，若第i1, …, ik个旅客领取了自己的行李，其他n-k个旅客可以任取行李，则“第i1, …, ik个旅客领取了自己的行李”的领取方法数  |⋂[j∈{i1, …, ik}]Yj| = (n-k)! 。一共有C(n,k) 个k-元旅客组，所以，∑[(i1, …, ik)]|⋂[j∈{i1, …, ik}]Yj| = C(n,k)* |⋂[j∈{i1, …, ik}]Yj| = n* (n-1)*… * (n-k+1) * (n-k)! / k! = n! / k!  。

多个集合的并集的元数等于所有集合的元数之和减去所有二个集合交集的元数之和加上所有三个集合交集的元数之和···减去所有偶数个集合交集的元数之和加上所有奇数个集合交集的元数 之和···

根据上述有关“多个集合的并集的元数”的公式，

|Y| = | ⋃[i=1 to n]Yi |

      =  ∑[i1]|Yi1| - ∑[(i1,i2)]|Yi1⋂Yi2|  +   … + (-1)^k+1 * ∑[(i1, …, ik)]|⋂[j∈{i1, …, ik}]Yj| +

          …+ (-1)ⁿ⁺¹ * ∑[(i1, …, in)]|⋂[j∈{i1, …, in}]Yj|  

      = n! - n!/2! + n!/3! - … + (-1)^k+1 * n!/k!   +…+ (-1)ⁿ⁺¹ * n!/n!  

      = n! *

∑[k=1 to n](-1)^k+1/ k!

 

|X| = n! - |Y|

      = n! - n! *

∑[k=1 to n](-1)^k+1/ k!

 

      = n!*(1-

∑[k=1 to n](-1)^k+1/ k!

 )

      = n!*

∑[k=0 to n](-1)^k/ k!

 

答案一：有n!*

∑[k=0 to n](-1)^k/ k!

领取法，使n个旅客全都领错了行李。

*********************

如前所述，k个旅客领取了自己的行李，其他n-k个旅客可以任取行李。现在有n-m个旅客领取了自己的行李，其他m个旅客全都领错了行李。一共有C(n, n-m) 个(n-m)-元的旅客组，他们领取了自己的行李；根据答案一，有m!*

∑[k=0 to m](-1)^k/ k!

领取法，使m个旅客全都领错了行李。所以，有

 C(n, n-m)*

∑[k=0 to m](-1)^k/ k!

  =

(n!/(n-m)!)*∑[k=0 to m](-1)^k/ k!

。

答案二：有  (n!/(n-m)!)*∑[k=0 to m](-1)^k/ k! 领取法，只使m (m<=n) 个旅客领错了行李。

完。