数学棒棒堂第四期之“计数问题2”大挑战

提起数学家丹尼尔·伯努利（Daniel Bernoulli）（1700年2月8日—1782年3月17日），他是18世纪一位重要的数学家，也是欧拉最亲密的朋友，也是竞争的对手。

在数学史上伯努利家族像是开挂了一样，在17世纪和18世纪，三代人里面涌现出了8名数学家。丹尼尔·伯努利就是著名的伯努利家族中最杰出的一位，他同欧拉一样获得过10次法国科学院的大奖。

1733年离开彼得堡之后，就开始了与欧拉之间的最受人称颂的科学通信，他曾经给欧拉写了一封信，讨论一个数学问题：“某人给五个朋友写信，邀请他们来家中聚会。请柬和信封交由助手去处理。粗心的助手却把请柬全装错了信封。请问：助手会有多少种装错的可能呢？”

看到了丹尼尔的问题，欧拉稍加思考，就把这个问题搞定了，这就是我们平常说的“装错信封问题”，专业一点称呼为“伯努利-欧拉错排问题”！

【上一期思考题】类似上面的题目，2封2箱全错排有几种投法？3封3箱全错排有几种投法？一定要自己动手画图试一试哦！

【解答】2封2箱全错排只有1种投法；3封3箱全错排有9种投法。

上节课我们说到利用树状图解简单的全错排问题，但随着信和信箱数量的增多，比如10个信箱10封信，用树状图的方法就会非常复杂。对于装错信封问题，发现其数学规律，并给出能理解的通用解法。咱们跟随欧拉的足迹，欣赏他的解法……

记n个信箱n封信全错排为Dn，由枚举得到D1=0，D2=1，D3=2，D4=9。现在我们就来展开分析D5这个这种情况：

【分析】我们先把信封投进邮箱、、或，这四种情况都是一样的，所以只分析信封投入邮箱来展开分析：

丢掉第二个已经配对好的邮箱之后，再来看信封可以投进哪些邮箱呢？没错，全都可以。但我们还是分成两类讨论：

1、当信封放在邮箱中：

此时发现剩下的三封信都是错排的情况，即D3；

2、当信封放在邮箱、或中：

此时发现四个信封都是错排的情况，即D4。

由加法原理可知，信封投进邮箱后，全错排的情况共有：D3+D4，则信封投进邮箱或、、后，全错排的情况共有：（D3+D4）×4。所以D5=（D3+D4）×4=（2+9）×4=44。

这种递推方法Dn=（Dn-2+Dn-1）×（n-1）是不是大大缩减了你的枚举方法呀，这就尝试一下n=6、7、8怎么计算：

D6=（D4+D5）×5=?

D7=（D5+D6）×6=?

D8=（D6+D7）×7=?

【解答】D6=265，D7=1854，D8=14833。

再解这个数字是不是就非常大啦！可千万别去背这个数列，否则你可能吐血啊~小朋友你们理解这种方法了吗？咳咳，又到我出题考考你们的时间了。

【例题】梯方班主任刘老师有7封信件要投送给7位小朋友家长的邮箱中，你知道刘老师投对2封投错5封有多少种情况吗？

【解答】一定有同学说，上面不是全错排吗，这里是不是和5邮箱5封信的情况一致呀？哎哎哎，能想到这一点，那么你离成功就不远了！这个题目确实投错5封信，但可有7个邮箱……

那我们利用乘法原理分步考虑，先挑出5个邮箱出来再全排错不就做出来了吗：

1、从7邮箱中挑出5邮箱：

2、5个邮箱5封信全错排：D5=44

即刘老师投对2封投错5封有21×44=924种情况。

这期我们跟随欧拉的足迹，根据数学规律慢慢推出通解方法，领略了数学之美。这位大神是不是即将变成你们崇拜的偶像啦，把这样的科学家当成你的爱豆才倍有面儿啊！