摘 要
全错位排列问题是组合数学中的经典问题，本文综合叙述了解决此问题的多种方法，如递推、容斥原理等，并在文章最后提到了一种较为新颖非组合数学类的解决方法，即DNA计算方法。
【关键词】全错位排列问题 容斥原理 DNA计算
解决错排问题的方法有很多，比如利用递推关系、利用容斥原理等等。本文给出一些组合数学中常用的方法以及其他学科领域的方法来解决全错位排列问题。
1 全错位排列数的一般解法
递推关系、容斥原理等方法是组合数学在计算中常常利用的基本方法，下面我们将分别利用上述方法求解全错位排列数Dn的表达式。
1.1 利用递推关系
2 全错位排列数的其他解法
以上本文简单地叙述了由组合数学的常规方法计算得到的错排问题的解。为了加深对错排问题的理解，这里再对错排问题的其他一些较为新颖的解法进行简单的介绍。
DNA计算是生物技术同计算机、数学等领域交叉形成的十分有研究潜力并且计算十分高效的新型计算方法，这种计算方法是组合数学中错排问题的一种很好的解决方式。DNA计算的实现方式主要有三种：试管、表面、芯片。在文献[5]中，作者分别就错排问题的DNA计算方法的实现、基于表面的DNA计算、基于芯片的DNA计算进行了详细的阐述。
DNA计算的基本思想是[5]：利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码把要运算的对象映射成DNA分子链在生物酶的作用下生成各种数据池（data pool）然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程最后利用分子生物技术如聚合链反应PCR超声波降解亲和层析克隆诱变分子纯化电泳磁珠分离等检测所需要的运算结果。
3 结束语
全错位排列问题是组合数学以及各学科应用领域中常常碰到的问题，长期以来人们总结出很多求解错排问题计数公式的算法，以及对具体错排问题的解构造各类数学模型并运用一些高级算法进行求解，而且很多人通过错排问题引申出更多更具有实际意义的错排，如二重错排等。可见研究好错排问题在组合数学领域乃至其他领域具有十分重要的意义。
参考文献
[1]南基洙.组合数学[M].北京：高等教育出版社，2008.
[2]张一倩.从错排问题谈组合计数方法[J].中国科技信息.2008，Vol 15：36-38.
[3]周国平.由错排问题引出的两个排列数公式[J].杭州师范学院学报（自然科学版）. 2003，1Vol 2（1）：77-79.
[4]房亮，冯增哲.错排问题的一种有效解法[J].山东科技大学学报（自然科学版）. 2005，6Vol 24（2）：84-87.
[5]孙侠，殷志祥.错排问题的DNA计算方法[J].科技广场.2005.3：64-65.
作者简介
许斌龙（1989-）男，浙江省诸暨市人。硕士研究生。研究方向为网络与信息安全。
作者单位
安徽理工大学计算机科学与工程学院 安徽省淮南市 232001
相关热词搜索： 错位 排列 若干 解决 方法