第三章排列与组合排列与组合的知识是组合计数的基础。从这一章开始我们将系统地介绍组合计数理论。组合计数所要解决的中心问题是求满足某些条件的方案总数。比如：（1）在全系100名学生中选出3名同学去参加ACM比赛，有多少种方案（2）一棵有个结点的树共有多少种不同构的形式？（3）将8个皇后放在一张棋盘上，使得没有两个处于互相攻击的位置，共有多少种放置方法？排列与组合的知识就是解答诸如上面这类问题的。组合计数理论最初的应用是概率的计算。Laplace（1749—1827）首先定义了概率的概念。他说，如果一个确定的集合中总共个对象，并且有一个具有个对象的有利子集。那么，随机地从这个全集中选取出有利对象的概率是。为了从这个定义计算概率，我们必须能够计算出有利对象的数目与可能情况的总数。这就涉及到组合计数问题。3.2分拆与置换的表示3.2.1分拆的表示定义3.3排列记为=，，一个排列是到的一个双射，一般用表示。一个由个元素组成的排列可以写成如下的形式例如：5个元素组成的排列可以写成可以进行圈的分解，我们可以将上面的排列写成，这种圈的分解与是一一对应的，的圈之间是无序的。令=，表示上满足圈的个数为的排列的个数。我们可以得到如下的定理：定理3.3=证明首先证明=任给上的一个排列，当单独一个圈时，对应上个排列；否则，在圈中，有个位置，对应上1个排列，等式成立。对用数学归纳法。当=1时，易知等式成立。假设时命题成立，现证时结论成立。由假设=综上可知，定理成立。定义3.4集合的一个分拆是的一些非空子集构成的集族，满足，且，其中每个称为此分拆的一个块。设表示上的分拆个数，称为数。定理3.4=，其中定义=1。证明在对进行分拆时，考虑所在块的情况。从中选出个与组成一个块，剩余个元素的分拆数为，由=知，定理成立。3.2.2置换的表示定义3.5设，对进行圈分解，按如下规则可得排列：（1）在的每个圈中，将此圈中的最大元放在首位。2（2）再将的所有圈按照各圈中最大元单调递增的顺序排列，并去掉圈表示的括号。如此得到的排列称为的标准表示。例3.6=4271365=，则的标准表示为2416753。反之，我们已知的标准表示为，依次找出第一个比大的，第一个比大的，以此类推，可得到的圈表示。定义3.6设，=，称为的降集。例3.7=4271365，则=。定义3.7函数，其中称其为函数。定义3.8置换的标号递增二叉树表示设=，首先找到1所在的位置，将分成两段和，分别将其置于标号1的左边和右边，然后递归地做下去，生成的树称为的标号递增二叉树。3.3排列与组合的生成算法在许多场合中，我们经常生成一些元素的特定排列与组合。本节给出一些常见的排列与组合生成算法。3.3.1—排列生成算法我们采用回溯法来生成从个元素中取出个元素的所有排列情况。其中个元素用表示。在程序中，过程递归的层数表示当前正在生成排列中第个位置的数。过程执行时，首先判断是否在该排列以前的位置上出现过。若已经出现过，那么则说明不可能出现在当前位置上，此时值增1重复以上判断，=时回溯；若没有在该排列以前的位置上出现，则该位置上的值就是，这时判断递归的层数与的值是否相等。若=，输出一个新的排列并回溯；若，则继续进行递归。参考程序3.1：programexample3_3_1;varn,r:integer;flag:setofbyte;{记录在生成一个排列的过程中出现过的元素}data:array[1..20]ofinteger;{记录相应位置上的元素的值}procedureout;{输出一个新的排列}vari:integer;begin3fori:=1tordowrite(data[i],'');writeln;end;proceduredone(i:integer);{递归的层数i表示正在生成第i个位置上的元素}varj:integer;beginforj:=1tondoifnot(jinflag)thenbeginflag:=flag+[j];data[i]:=j;if(i=r)thenoutelsedone(i+1);flag:=flag-[j];end;end;beginread(n);read(r);done(1);end;3.3.2错位排列生成算法错位排列生成算法与—排列生成算法的不同之处在于：在生成错位排列第个位置上的元素时，必须保证该元素不等于。下面给出生成错位排列的程序。参考程序3.2：programexample3_3_2;varn,r:integer;flag:setofbyte;{记录在生成一个排列的过程中出现过的元素}data:array[1..20]ofinteger;{记录相应位置上的元素的值}pr...