对全错位排列问题的拓展及新方法的探究

摘 要 全错位排列问题一直是组合数学中的经典问题，本文在前人研究的基础上，想出了一个新颖的计算方法——“相式”计算法，可单独利用“相式”进行计算，也可以将“相式”与前人已总结出的公式相结合，得到一个全新的计算表达式，该表达式适用于以往经典全错位排列模式以外的排列数计算，使全错位排列问题得到了进一步的解决。

关键词 全错位排列 拓展 新方法 探究

中图分类号：G623.5 文献标识码：A

1问题的提出

全错位排列问题，也称“伯努利-欧拉错装信封问题”，题意为：某人写了n封信及相应的n个不同信封，问他把这n封都装错信封的装法有多少种？

数学家欧拉给出了该问题的公式推导：他用A、B、C…分别表示n个信封，a、b、c…则分别表示n份相对应的信纸。把错装的总数记作F（n）。若把a错装进B，则该错误的错装法分两类：

（1）b装入A，有F（n-2）种错装。

（2）b装入A、B之外的信封，有F（n-1）种错装。

故a装入B，共F（n-2）+F（n-1）种错装。a装入C、D…同样有F（n-2）+F（n-1）种错装，故：

F（n）=（n-1）[F（n-1）+F（n-2）]

F（1）=0，F（2）=1

2“相式”原理及推导

有m个盒子和m个小球，盒子和小球都分别标着1，2，3...，其中m个小球中的n个小球编号分别与m个盒子中的n个盒子编号相同（剩余m-n个小球之间编号互不相同），若将m个盒子里放入这m个小球，要求小球编号与盒子编号不同的放法有几种？

先把与小球编号相同的其中一个盒子置于首位，将该盒子放入与其编号不同的小球，应有m-n种放法，在第一个盒子里的小球确定之后，剩下m-1个盒子里放入m-1个小球，其中这m-1个小球中有n-1个小球与盒子编号相同，我们把这n-1小球放入m-1个盒子中的排列数记作：

接下来将置于首位的盒子放入与盒子编号相同的小球（其中与首位盒子编号相同的小球不能放入），这时小球放入首位盒子的放法有n-1种，剩下m-1个盒子中有n-2个小球编号与之相同，同理，将这n-2个小球放入m-1个盒子中的排列数记作：

最后排列总数可表示为：

①

（m≥n）， ②

我们把含“”符号的等式称为“相式”。指把m个标有不同编号的小球（其中n个小球编号与盒子编号相同）放入m个标有不同编号的盒子，且要求小球与盒子编号不同的排列数。

例：现有编号为1，2，3，4的四个小球和编号为1，2，3，4的四个盒子，将这四个小球放入这四个盒子中，其中小球编号不能与盒子编号相同的放法有多少种？

根据题设条件得知：m=4，n=4，代入①、②式有：

再根据：

最终答案为：

假如上述例题中的四個小球编号分别是1，2，3，5将其放入编号分别1，2，3，4的盒子中，问小球编号与盒子编号不同的放法有多少种？

同理，知m=4，n=3，代入上述①、②式中：

，而，由于，故，得出：=11

在本题中发现递推公式不再适用，而“相式”则可算得结果。为便于计算作如下推导：当m=n时，有：

③

④

由于③、④式相等

得 ⑤

⑥

故 ⑦

⑧

令： ⑨

则 ⑩

若将上述例题用⑨⑩式，即m=4，代入得：

3结束语

错排问题是组合数学常遇到的问题，本文用“相式”对错排关系及排列数进行数学语言的表达，在前人研究的基础上，建立了能够解决大多数错排问题的计算公式，总之错排问题还有待进一步的探索。

推荐访问:错位 探究 对全 排列 及新