關於“乘飛機的旅客領錯行李”問題的非遞歸解答。

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) 個旅客領錯了行李。

完。

所有跟帖： 

• 可用逐步淘汰原則,立得答案. -jinjing- ♀ (162 bytes) () 12/18/2010 postreply 08:37:28

• 謝！修正一下 2） -皆兄弟也- ♂ (451 bytes) () 12/18/2010 postreply 12:08:59

• 謝. -jinjing- ♀ (42 bytes) () 12/18/2010 postreply 12:43:00