物理

欧拉--伯努利装错信封问题（错排问题）

适用轮次：基础轮+

隶属于：排列组合

(@^^)/

  欧拉和伯努利那个时代还没有互联网，于是两人就写信聊天。但是这两位大数学家太有名气了，每天给他们写信的人不计其数，导致两人经常把信寄错。

  某一天，欧拉突发奇想：“诶！我有一计！_/↑”如果我的每一封信都寄给了错的人，那么一共有多少种寄法？

  于是把这个问题简化为数学模型之后，便有了以下定理：

  假设有①②③......N个格子，要填入1，2，3......n这n个正整数，要求每个方格的标号与所填数字均不相同

  若假设有${A}_{n}$种填法，则存在以下递推公式：

     ${A}_{n} =（n-1）（A_{n-1}+A_{n-2}）$，其中${A}_{1}$=0，${A}_{2}$=1

证明：

  观察以下格子：①②③......N，易得①中有n-1种填法，不妨假设其填入了2

  （1）.若②中也填入了1，此时①②互相成为闭环，剩余的格子为n-2阶错排问题，共${A}_{n-2}$种填法；

  （2）.若②中未填入1，则此时问题转化为

            “②③④......N中需错排填入1，3，4......n，其中②不能填入1” 

  这与“②③④......N中需错排填入2，3，4......n，”并无任何区别，为一个n-1阶错排问题，共${A}_{n-1}$种填法

   由加法与乘法原理可知${A}_{n}＝(n-1)(A_{n-1}+A_{n-2})$

这虽然只是排列组合一个定理的证明，但是其中的思想非常巧妙，这种将方法的种数转化为某某阶的原问题，以此来求递推公式的思想会一直沿用到竞赛中，非常重要