从错排问题谈组合计数方法

《从错排问题谈组合计数方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据基础及前沿研究帽科技信息2008年第15期cHlNAscI撇AND删N。LoGYINF洲ATJoNAug．2008越‰稚mm。“，；⋯☆?甜Ⅲ“％±。啦3l》。Ei"

2、々Mjj。☆h；mt矗“m“¨i础衅㈣一‰Ⅲk㈣黜从锚擦闻题谈组合计数方法张一倩1．21、山东大学计算机学院2500142、济南职业学院计算机系250105辆’妻，一一”’。⋯．”’一⋯谭一些计算机程序的重要理论基础是组合学算法，而组合计数是组合学研究的重要方面。对组合问题而言，求解工具的选取是很重要的。文章以错排问题为典型实例，简要介绍了几种计数的方法并对其做出了比较。蔫键谲。露组合计数；

3、错排问题；母函数；容斥原理；递推1．组合计数方法概述计算机目前的运算速度可以解决大型问题，但仍需要通过编程控制。一些程序的基础是求解问题的组合学算法。而组合计数问题是组合数学研究的重要方向，它不仅在人工智能、过程控制等学科领域有重要应用，同时在社会科学中也得到越来越广的应用，其思想方法正受到普遍重视。组合数学主要是研究某组离散对象满足一定条件的安排的存在性、构造及计数等问题。组合计数理论是组合数学中～个最基本的研究方向，主要研究满足一定条件的安排方式的数目及其计数问题。所谓组合计数，是指计算满足某种条件的排列或组合的总数。典型的解决策略是使用母函数、容斥原理等思想

4、。本文以错位排列问题为例，说明解决此类问题的方法。n个有序的元素共有n!个不同的排列，若一个排列中每个元素都不在原来的位置，则称此排列为错位排列，简称错排。即若(a。，a，，⋯，an)是{l，2，⋯，n}的一个错排，则a{≠i，i∈{1，2，⋯，n}。错排问题即计算{l，2，⋯，n}的错排个数，记为D。。2．普通递推算法递推关系是组合数学用以计数的有效工具。递推算法的思想是充分利用已经得到的信息由初始条件向终止条件推导，从而降低算法的时间复杂度，是一个较优化的算法。若数列{aiJi≥o}，把a。与其前若干项联系起来的等式对所有n≥k均成立(k为某个给定的自然数)，

5、则称该等式为{a．}的递推关系，记为0【n=F(o【n一1，仅n一2，⋯0cn—k)同时，称含有初始条件的递推关系为定解问题，其一般形式为f口H=F(d．_l，口。．2⋯．口和七)L％=以，口l=吐，．，口。l=钆普通递推算法的目的就是根据上式求an的与ao，al，⋯，a。一1无关的解析表达式。以错排问题为例，由定义得到初始条件：n=l时，错排数D．=O；n=2时，{l，2}的错排为(2，1)，错排数D2ln=3时，{l，2，3}的错排为(2，3，1)和(3，l，2)，错排数D，=2，考虑到n>3后，情况比较复杂，于是针对任一i∈{1，2，⋯，n}，将错排情况分两

6、类：1)i与其它某位互换?余下n一2位错排，有(n一1)D．一，种错排；2)i不动，其余n—l位错排后，i再与每位互换，有(n一1)D⋯种错排。以上两种分类得到的结果不会产生交集，所以D．的递推关系为：rD：=(n—1)(pH+D02){DI=oLD，=l反推得到D。=l。由以上关系得到：见一，t见．I=(一I)(见一i一(Ⅳ一1)见一2)=(一1)2(见一2一(疗一2)q一2)=(一1)“4【D2一DI)=(一1)”从而鲁=譬+鲁：绁+!监+世二+．．．+出押!(盯一1)!(”一2)121肋见=一m一吉+击一击+⋯±击，伽2·，3．母函数方法对于某些组合计数问题

7、，可以运用代数手段适当的引入母函数，通过这种形式上的变化得到解决。这里应用指数型母函数求解错排问题。指数型母函数是母函数的一种典型形式，基本思想是把离散的数列与幂级数一一对应，从而把离散数列间的关系转换为幂级数的运算。对于序列o【o，0【I，a2，⋯，称q(x)=‰+口．舌+色着+a，吾+¨。为序列{a；}的指数型母函数。令D(工)2萎见备，把D。作为备的系∞。Hv■数。由上面递推算法的中间结果D。一nD。=(一1)“得到启发：D(，)一xD(x)：现+(B—D0n+(拿一qn：+⋯=，一x+；；一；；+⋯，D(x)=(1一J+三；一要+⋯)(1+x+x2+，+⋯

8、)’从而Xn的系数是ct一古+刍一击+．．．±击，，见=州t一击+去一击+．．士去，。4．容斥原理方法容斥原理是解决组合计数问题的重要工具，由J．J．Sylv融er首先建立，基本思想是：计数时，先不考虑重叠的情况，把包含于某内容中的所有对象的数目计算出来，然后把重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。据此思想，又可具体应用逐步淘汰原理或棋盘多项式求解错排问题。4．1利用逐步淘汰原理求解集合S的子集A，具有性质P，，子集A，具有性质P，，．．．子集A。具有性质P。，则S不具有性质P．，P，⋯．只之一的元素个数满足p—njzn⋯nj一

9、=l爿一∑14l

10、+∑14n