装错信封问题.doc

《装错信封问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、装错信封问题组合学中有这样一个问题：某人给五个朋友写信，邀请他们来家中聚会。请柬和信封交由助手去处理。粗心的助手却把请柬全装错了信封。请问：助手会有多少种装错的可能呢？这个问题是由18世纪初的法国数学家蒙摩提出来的。瑞士数学家欧拉按一般情况给出了一个递推公式：用Ａ、Ｂ、Ｃ……表示写着ｎ位友人名字的信封，ａ、ｂ、ｃ……表示ｎ份相应的写好的信纸。把错装的总数为记作f(n)。假设把ａ错装进Ｂ里了，包含着这个错误的一切错装法分两类：（１）ｂ装入Ａ里，这时每种错装的其余部分都与Ａ、Ｂ、ａ、ｂ无关，应有f(n-2)种错装法。　　　　（２）ｂ装入Ａ、Ｂ之外的一个信封，这时的装信工作实际是把（除ａ之外的）

2、　　份信纸ｂ、ｃ……装入（除Ｂ以外的）ｎ－１个信封Ａ、Ｃ……，显然这时装错的方法有f(n-1)种。总之在ａ装入Ｂ的错误之下，共有错装法f(n-2)+f(n-1)种。ａ装入Ｃ，装入Ｄ……的ｎ－２种错误之下，同样都有f(n-2)+f(n-1)种错装法，因此:f(n)=(n-1){f(n-1)+f(n-2)}　　这是递推公式，令ｎ＝１、２、３、４、５逐个推算就能解答蒙摩的问题。f(1)=0f(2)=1f(3)=2f(4)=9f(5)=44答案是４４种。一般地，当ｎ＞２时f(n)=