运筹与组合-201009.doc

（注意：本文件的显示、打印需要公式编辑器的支持。）运 筹 与 组 合山东大学计算机学院二O一O年九月前言先修课程要求：离散数学、高等数学课程内容与学时分配： 1运筹学 共14学时线性规划 6学时整数规划 2学时动态规划 6学时2组合数学 共20学时排列组合 2学时鸽巢原理及应用 4学时容斥原理及其应用 4学时母函数方法 3学时递推关系 3学时Polya 计数定理 2学时对弈论 2学时参考文献:1. 刁在筠等，运筹学，高等教育出版社，20012. Richard A. Brualdi, Introductory Combinatorics, Printice Hall, Inc., 19993. 卢开澄，组合数学，清华大学出版社4. 朱大铭，算法设计与分析，高教出版社。目录第一篇运筹学1第一章线性规划11线性规划问题及数学模型12图解法63单纯形法解LP问题84对偶线性规划13第二章整数规划171整数线性规划问题172整数线性规划问题解法18第三章动态规划201最优化原理202用最优化原理解非线性规划问题223动态规划算法设计23第四章网络分析301图及网络302网络上的优化问题31第二篇组合数学43第五章排列组合431和、积的原则432排列443重复排列464组合515组合等式及意义546排列与组合的生成54第六章容斥原理与鸽巢原理571容斥原理572鸽巢原理623有重复元素的圆排列问题66第七章母函数与递推关系711用母函数解递推关系712用母函数解整数拆分问题763用指数型母函数解错排问题79第八章Polya 计数定理821Burnside引理822Polya定理8896第一篇 运筹学第一章 线性规划1线性规划问题及数学模型例1设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如下表所示，运费与运量成正比，建立运费最省的供给方案。地产费运地销ABCD甲21 25 7 15乙51 5137 15例2某工厂用3种原料P1，P2，P3生产3种产品Q1，Q2，Q3。已知的条件如下表所示，制定出总利润最大的生产计划。需原料kg单位产品所原料品产Q1 Q2 Q3原料可用量（kg /日）P12301500P2024800P33252000单位产品利润(千元)354线性规划（LP）问题的一般形式（等式不都在前面怎么办？非负变量不都在前面怎么办？）目标函数价值系数，价值向量决策变量，决策向量约束，约束矩阵右端向量Ax = ? b非负约束自由变量可行解、可行点满足约束的点可行域D最优解LP问题的规范形式一般形式中p=0, q=n 时，称为规范形式。一般形式与规范形式的转化将化为令例：将下面的线性规划转化为规范形式解：，LP问题的标准形式一般形式中p=m, q=n 时，称为标准形式。一般形式与标准形式的转化对，令这里的称为剩余变量。例：将下面的线性规划转化为标准形式解：，2图解法例1用图解法解线性规划x1+x2=5x1-2x2=22x1-x2=-2-x1+x2=0(5,0)(0,5)(2,0)(0,-1)x1x2(0,2)(-1,0)z在(1,4)点达到最大值3。例2用图解法解线性规划x1+2x2=8x1-x2=4x1-5x2=0(4,0)(0,-4)x1x2(0,4)(8,0)例3用图解法解线性规划无最优解关于可行域D与最优解的讨论：D，无解、不可行；D，无界；D，有最优解。3单纯形法解LP问题1单纯形方法考虑标准形式的LP问题设r(A)=m，A的前m列为线性无关。(注意各向量、矩阵的维数)将A分为左右两块，左边m列为可逆方阵B，右边记为N。(左面m列是不是一定可逆？)对应将价值向量c和决策向量x的前m行与后n-m行分开，令，则，且。原LP问题变形为若取，则得一个满足等式约束的解，其对应的指标值为。B称为基，B的列称为基向量，称为基本解，时称为基本可行解，此时B称为可行基时称为非退化的基本可行解。下面假设我们要讨论的LP问题对所有的可行基B，都有。定理若标准LP问题有可行解，则必有基本可行解；若有最优解，则一定存在一个基本可行解是最优解。(证明略)定理若，则是最优解。证。定理若的第k个分量，且，则该LP问题无界。这里Ak表示矩阵A的第k列。证取，（这是一个n维的列向量，第k个分量为1，其余分量为0。）令取(下面说明此x是可行解，且其指标值要多小有多小。)定理若的第k个分量，且中存在正分量，则，使得且。证令（见前面定理中的定义，这里但不能任意取。）1）可以适当取使得为可行解：由知道；要使得即，只需，设由等知道取即可。2）这里，但因为不能任意取大数，所以指标不能任意小。4对偶线性规划1对偶线性规划 是约束矩阵A的第i行，Aj是约束矩阵A的第j列。规范形式的对偶问题为标准形式的对偶问题为2对偶理论定理如果一个LP问题有最优解，则它的对偶问题也有最优解，且它们的最优解值相等。定理对偶的对偶为原始的LP问题。3对偶LP的来历将一般形式化为标准形式，其中，令，则改写为，即，展开为，第二章 整数规划1整数线性规划问题要求变量值取整数值的线性规划问题称为整数线性规划，其中变量只取0或1的线性规划称为0-1规划。投资决策问题总金额B万元，n个项目，第j项目所需资金bj，利润cj，应该选哪些项目使总利润最大。房产投资地产面积3000 M2，甲类房产每幢250M2，可收利润10万元，可建设不超过8幢，乙类房产每幢400M2，可收利润20万元，可建设不超过4幢，应该建设甲乙各几幢使得利润最大？货朗问题从v0出发，恰好经过v1，v2，vn各一次回到v0，从vi到vj路程为dij，（diiM充分大），怎么走最近？背包问题n个物品，体积分别为v1，v2，vn，价值分别为p1，p2，pn，一个容积为V的包，取哪些物品放入包内，使包内物品总价值最高。2整数线性规划问题解法1 图解法图解法求解下面的ILP问题2 分枝定界法(1.5, 2.5)(1, 1.5)(2, 1.5)第三章 动态规划动态规划是多阶段决策问题，相对地，线性规划、非线性规划问题称为静态规划问题。1最优化原理全局最优，则局部最优。（如何理解）最短路问题cb7243647132516438u02edagf货郎问题设表示从vi出发，经过V中的所有点恰一次后回到v0的最佳路线总长度，则所求的就是。例：2用最优化原理解非线性规划问题就下面的非线性规划问题，讨论最优化原理解题思想，并具体求解该题解得：，故3动态规划算法设计填表的思想及优势fn=fn-1+fn-2 f100 f1=1 f2=11 1 2 3 5 8 13 21 .1博弈论中的一个问题甲乙两人对弈，胜算概率相同，求“甲再胜i盘胜利，乙再胜j盘胜利”时甲胜利的概率。2划分问题用动态规划思想，设计填表法，求解下面的划分问题在集合Aa1，a2，an上定义正整数函数s，令，问是否存在，使得。3背包问题背包问题n个物品，体积分别为v1，v2，vn，价值分别为p1，p2，pn，一个容积为V的包，取哪些物品放入包内，使包内物品总价值最高。4排工问题n个工件，每个工件都要按顺序经过A、B两个机床进行加工，工件i在A、B两个机床上加工时间分别为ai，bi，确定n个工件的加工顺序，使得总加工时间最短。例：N1N2A42B13先加工N1，所需总时间为4239，先加工N2，所需总时间为2417。定理最优加工方案当工件在A、B机床上加工顺序相同时达到（证略）。状态(X,t)：X中是还没有经过A机床加工的工件，t是B机床加工X外的工件还需要的时间，如果取为下一个放在A上加工的工件，则i在A上完成加工时达到下一个状态(Xi，zi(t)，其中ABiXtai状态（X，t）ABiXiZi(t)bi状态（Xi，zi(t)）令f(X,t)为处于状态(X,t)时剩余的最优排工时间，则f(X,t)是t的单调上升函数，且，f(1,2,n,0)即为n个工件的最优加工时间。在状态(X,t)时对于X中的两个工件i, j，下面讨论应该先加工i还是先加工j才能使得剩余加工时间最少。如果先加工i，则剩余最优加工时间记为，如果接着下一个加工j，则最优加工时间为，其中同理，如果状态(X,t)时先加工j，再加工i，则最好加工时间为，由f(X,t)是t的单调上升函数，要想，只要，即，只需要即可。算法：1、2、3、4、例：12345A37457B62734加工顺序为13542。第四章 网络分析 1图及网络图，点集，点，边集，边，平行边，自环 定义1设V是一个非空集合，E是一个V中元素的无序对构成的多重集，有序对GV，E称为一个图，其中，V称为顶点集，其元素称为顶点或点，E称为边集，其元素称为边。以上定义的图也称为无向图。相邻，关联，度，握手定理，通路，简单通路，初级通路回路，圈，连通，连通分支，单连通，强连通关联矩阵，邻接矩阵子图，生成子图，边割，割集树，2网络上的优化问题1 最短路问题在实际问题当中，图的边往往与某种数量相联系，例如，在铁路交通图中，根据所讨论的问题，每条边上可以标上其代表的铁路的长度，或标上修建该铁路所需的费用等，一般地，引入如下定义定义1设G是一个图，若对G中每条边e都规定一个非负实数w(e)，则称G为赋权图（或权图），w(e) 称为边e的权G的边与非负实数的这种对应关系(用w表示)称为权函数例如，设G是铁路交通图，对G中每条边e规定w(e)为e所代表的铁路的长度，则得到一权图，若规定w(e)为修建e所代表的铁路所需费用，则又得到另一权图再如，设G是秘密通讯图，对边e规定w(e)为泄秘可能性则得到一权图，又若规定w(e)为维护e所需费用，则又得到另一权图按照通常惯例，当u，v不相邻时，规定w(uv)定义设G是一个权图，是G的子图，中各边的权之和称为子图的权，记为w()，即w()由于权图中的权常常代表某种耗费，许多最优化问题都是要在一个权图中找出某类具有最小权的子图，其中之一就是最短路问题定义设G是一个权图，路P的权w(P)称为P的长度，两点u，v之间最短路的长度称为u，v之间的距离，记为(u，v)，即定义设G是一个权图，u0V(G)，SV(G)，u0到S内各点的所有路中长度最小者，称为u0到S的最短路，其长度称为u0到S的距离，记为(u0，S)现在我们就来讨论在权图G中寻找最短路的问题，为此，先做几点假设1)显然，只要讨论简单图的问题就够了，所以下面假设G是简单图2)因为当w(uv)时，我们认为u，v重合，所以我们不妨假定所有边的权均为正数下面介绍的算法是Dijkstra在1959年提出的，这个算法可以求出G中一点u0到其余各点的最短路及距离，它至今是解最短路问题的最好算法之一Dijkstra算法基于如下基本原理假设S是V的真子集，u0S，令SVS，若Pu0是从u0到S的最短路，则显然，且P的(u0，)节必然是最短(u0，)路，所以利用该公式，便可按如下过程求最短路首先，确定距u0最近的一个顶点令S0u0，由于距u0最近的顶点必为u0的邻点，故只需求出u1使w(u0u1)minw(u0v)|v，即u0u1是与u0关联的最短边，显然，u0u1便是最短(u0，u1)-路又令S1u0，u1，且用P1表示路u0u1，一般地，若Sku0，u1，uk以及相应的最短路P1，P2，Pk已经确定，则可用(1)式来计算，并选取顶点uk+1使d(u0，uk+1)这时，d(u0，uk+1)d(u0，uj)w(ujuk+1)对某个k成立将边uj uk+1连接到路Pj上，即得最短(u0，uk+1)-路Pk+1，再令Sk+1u0，u1，uk，uk+1，这样一直下去，直到，即可求出u0到G中任意一点的最短路为了说明上述过程，考察图3.1，u0到任一点的最短路用粗黑线表示（带圈的数字、表示该过程中边加入最短路的顺序）在上述过程中，若每一步都通过搜索来计算(1)式的最小值，则必定会有大量的重复比较，为避免重复并保留从每一步到下一步的计算信息，采用如下的标号方法：在整个算法中，每个顶点v给以标号l(v)，它是d(u0，v)的一个上界，开始时，l(u0)，l(v)(vu0)，在算法进行时，这些标号不断修改，当求出Si时，l(u)d(u0，u)，ui，并且，b,?cdae272436471?32?5164?38u0?2?,?图3.1f,?g,Dijkstra算法 令l(u0)，l(v)(vu0)，S0u0，i 对每个，用minl(v)，l(ui)w(uiv)代替l(v)，计算minl(v)| ，并把达到这个最小值的一个顶点记为ui+1令Si+1=Siui+1 若i1，则停止，若i1，ii1，转入2当算法结束时，d(u0，v)由标号l(v)的终值给出如上所述，Dijkstra算法仅确定了从u0到所有其他顶点的距离，而并未给出实际最短路，然而，只要附加某些指令，不难获得这些最短路以上算法的计算量为(2)，因此是一个有效算法2 最小生成树问题定义1若图G的生成子图T是树，则称T为G的生成树定理1G是连通图当且仅当G有生成树证明充分性若G有生成树T，则由于T是连通的，易知G必是连通的必要性设G是连通图，若G中无回路，则G本身就是一棵树，从而有生成树若G中有回路，从回路中去掉一边，得到的图G1仍然连通，若G1中无回路，则G1是G的生成树，若G1中有回路，从回路中删去一边，一直下去，最后必得到一个图Gk，Gk是连通的且无回路，从而Gk是G的生成树显然，一个图G可能有多棵生成树，特别地，在赋权图当中，生成树的权一般也是不相同的，由于赋权图中的权往往代表着某种花费，寻找权最小的生成树，便有一定的实际意义权图G中带权最小的生成树称为最小生成树或最优树，看下面例子我们设想要建筑一个连接若干城市的铁路网，已知建造直接连接城市u与v的铁路费用为Cuv，试设计一个铁路网，要求建造费用最小将每个城市作为顶点，在顶点u，v之间连接一条权为Cuv的边，则得到一个权图G，显然，我们建造的铁路网应该是连通的，且必定没有回路，因而，我们面临的问题便是求G的最小生成树下面介绍最小生成树的Kruskal算法，先来介绍一下其直观思想设有赋权图G，既然我们要寻找G的最小生成树，我们所取边的权当然是越小越好，采用贪心策略，我们首先找到G的权最小的边，并取出来然后，在剩下的边中再找出权最小且与已选出的边不构成回路的，再把它取出来，一直下去，直到选不出边在上述过程中，我们得到的图是无回路的进一步地，我们可证明我们最终得到的是一棵最小生成树将以上直观思想叙述成算法，即是Kruskal算法设G是简单连通权图，w是其权函数(1) 选取G的一边e1，使w(e1)minw(e)|eE，令E1e1，(2) 若已选出Eie1，ei，那么，从EEi中选取一边ei1，使() Eiei1的导出子图中不含回路；() w(ei1)minw(e)| eEEi , Eie的导出子图无回路(3) 若ei1存在，令Ei1Eiei1，i1i，转(2)；若ei1不存在，则输出Eie1，ei，算法停止可以证明，如上算法所得到的边集的导出子图T*(就称其为算法得到的子图)，即为G的最小生成树定理Kruskal算法得到的图T*是G的最小生成树证明由算法可知，T*必包含了G的所有顶点且是连通、无回路的，从而可知T*是生成树因而，若设G有n个顶点，则T*中也必有n个顶点，从而T*中必有n1条边，于是，T*是边集En1e1，e2，en1的导出子图，这里，e1，e2，en1依次是算法产生的边下面用反证法证明T*是最小生成树若不然，取所有最小生成树中与T*具有最多公共边者为T1，则边集E(T*) E(T1)，设ek是T*中第一条不在T1中的边，即e1，e2，ek1E(T1)，E(T1)由树的性质，T1ek必有回路C由于T*中无回路，C中的边必有不在T*中者，设回路中的边ek E(T*)，显然T2(T1ek)ek也是一棵生成树，且 w(T2)w(T1)w(ek)w(ek)因为e1，e2，ek1，ek E(T1)，故这k条边不构成回路，由Kruskal算法中ek的取法知w(ek)w(ek)所以，w(T2)w(T1)，因此T2也是一棵最小生成树，且与T*的公共边多于T1，与T1的定义矛盾这样就证明了T*必为最小生成树3 最大流问题设NV，U为一个加权的有向图，权值为非负整数，若存在 X，YV，满足XY=，X中所有顶点的入度均为0，Y中所有顶点的出度均为0，则称有向图N为网络，并将X中的点称为源点，将Y中的点称为聚点（汇点），N中其他顶点称为中间点，N上的权函数c也称为容量函数一条弧ai，j的权值称为a的容量，记为c(a)或c()或c(i,j)我们主要讨论|X|=|Y|=1的情况，即假设网络中恰有一个源点x和一个聚点y，并总是将中间点集合记为I设NV,U为恰含有一个源点和一个聚点的网络，f为N的弧集U上的实数值函数，V1，V2V，用V1，V2表示起点在V1中，终点在V2中的弧的集合，记，当 V1=i时可以将f(V1,V2)简记为f(i,V2)定义1 设f为网络NV,U的弧集U上的实数值函数，如果函数f满足(1) 容量约束：0f(i,j)c(i,j)， i，jU，(2) 守恒条件：f(i,V)f(V, i)， i I，则称函数f为网络N的一个容许流，简称为流；当N的源点为x，聚点为y时，称f(x,V)为流的值，简记为f x, y由定义2可以证明定义2设函数f为网络NV,U的一个流，aU，如果f(a)=0，则称弧a是f -零的；如果f (a)0，则称弧a是f 正的；如果f (a) c (a)，则称弧a是f 不饱和的；如果f (a)= c (a)，则称弧a是f 饱和的4 最大匹配定义1设图GV，E，M E，如果M中任意两条边在G中均不相邻，则称M是G的一个匹配M中一条边的两个端点称为在M下是配对的定义2若匹配M的一条边与顶点v关联，则称M饱和v，或称v是M-饱和的，否则称v是M-不饱和的定义3如果M是G的一个匹配，对G的任意匹配M ，有 | M | | M |，则称M是G的最大匹配例1图4.1中，v1v2, v5v4, v7v8和v1v2, v3v4, v5v6, v7v8均是匹配，其中 v1v2, v3v4, v5v6, v7v8是一个最大匹配定义4设M是G的一个匹配，边在E(G)- M和M中交错出现的路称为M-交错路，起点和终点都是M-不饱和点的M-交错路称为M-增广路例2图4.2中v3v2v7v6v1是一条M-交错路，v4v5v10v9v3v8是一条M-增广路定理1图G的一个匹配M是最大匹配的充要条件是G不包含M-增广路证明设M是G的一个最大匹配，若G包含一条M-增广路v0v1v2v2m+1，设M = (M v1v2，v3v4，v2m-1v2m) v0v1，v2v3，v2mv2m+1 ，显然，M E，且M 是G的一个匹配因 |M |M|1，与M是最大匹配矛盾因而，G不包含M-增广路反之，设G不包含M-增广路，若M不是最大匹配，令M 是G的一个最大匹配，设H是由M M导出的G的子图，则H的每个顶点在H中的度只能是1或2，因此H中的每一个分支或是一个边在M和M 中交错的偶圈，或是边在M和M 中交错的路由 | M |M|，H包含的M 的边多于M的边，因此必有H中的一条路P开始于M 的边且终止于M 的边，故在H中被M 所饱和的P的起点和终点在图G中就是M-不饱和的，于是P是G的一条M-增广路，矛盾因而，M是最大匹配定义5设V0是图G的任一顶点子集，G中与V0的顶点相邻的所有顶点构成的集合称为V0的邻集，记为NG(V0)定理2设G是一个二分图，V1，V2是G的一个二划分，G含有饱和V1所有顶点的匹配的充要条件为| NG(V0)| V0|, V0V1证明设G含有匹配M，它饱和V1的每个顶点，并设V0V1由于V0的顶点在M下和NG(V0)中相异顶点配对，故|NG(V0)|V0|反之，| NG(V0)| V0|, V0V1假设G不含饱和V1所有顶点的匹配设M*是G的一个最大匹配，根据假设，M*不饱和V1的所有顶点设u是V1的一个M*不饱和顶点，并设Q表示通过M*交错路与u连接的所有顶点的集合由于M*是最大匹配，由定理1知u为Q中唯一M*不饱和点设V0=QV1，V 0= QV2，显然，V0u中的顶点在M*下与V 0中的顶点配对，因此| V 0 |=| V0|-1，又NG(V0)V 0 ，所以，| NG(V0)|=| V0|-1| V0|，矛盾定义6设G含有匹配M，如果G的每一个顶点都是M-饱和的，则称M是图G的一个完美匹配定理3设G是一个k-正则二分图，则G有完美匹配证明设V1，V2是G的一个二划分，则k|V1|=|E|=k|V2|，|V1|= |V2|设V0V1，用E1和E2分别表示与V0和NG(V0)中顶点关联的边的集合，则E1E2，故k|NG(V0)|=|E2|E1|=k| V0|，所以|NG(V0)| V0|,由定理2及|V1|=|V2|得证 我们用O(G)表示图G含有奇数个顶点的连通分支的个数，则有定理4图G有完美匹配的充要条件为O(G- V0)| V0 |, V0V(G)证明略第二篇组合数学第五章 排列组合1和、积的原则在排列和组合中，有两个最基本的简单法则：一是和的法则，一是积的法则。和的法则：如果一个事件可能以p种方式出现而另一个事件可能以q种方式出现，则这两个事件之一可能出现的方式数为p+q。换言之，如果S1和S2是两个集合，且|S1S2|0，则从SS1S2中选取一个代表的可能的方式数等于S1中选一个代表的方式数加上S2中选一个代表的方式数。例如一个班级有30名男生，20名女生，在这个班级选一名代表的方式数为50，等于在男生中选一名代表的方式数（30）与在女生中选一名代表的方式数（20）之和。积的法则：如果一个事件可能以p种方式出现，而另一个事件可能以q种方式出现，则这两个事件同时出现的可能方式数为pq。换言之，如果S1和S2是两个集合，且|S1|p，|S2|q，则第一个元素在S1内，第二个元素在S2内的有序对总数为pq。例如，一个班里有30名男生，20名女生，要选一名男生代表和一名女生代表，有多少种可能的选取结果？因为选一名男生代表有30种可能的结果，选一名女生代表有20种可能的结果，因此，搭配起来共有3020=600种可能的结果。容易看出，上述和的法则与积的法则，可推广到m个集合的情况。2排列什么是排列？排列是集合中元素的一个有序选取。两个排列是不同的，当且仅当它们的元素不同或者它们的排列顺序不同。n个元素集合S的一个r-排列，是从S中取出r个元素的有序排列。令P(n, r)表示S的所有r-排列的总数。例如，将红、白、蓝三个球放进10只编了号的箱子里。如果每一只箱子最多装一个球，那么将这三个球放到10只箱子里共有多少不同的放法？如果将10只编了号的箱子，视为10个不同元素的集合S，三个不同的球放进三只箱子里，视为从S中选取三个元素的一个排列，因此，不同放法的总数，等于S中所有3-排列总数P(10,3)。因为将三个球放进10只箱子里，可以把球一个一个地放入箱子里，将红球放入箱子里，有10种可能，放完红球后，只有9只空箱子，因此白球有9种可能的方法。白球放好后，只有8只空箱子，放蓝球只有8种可能的放法。所以根据积的法则，三个不同的球放入10只编了号的箱子，共有1098720种不同的放法。一般的情况是，n个中的r-排列总数，等于从n个元素中选取r个元素，放进r个编了号的空位置上不同放法的总数。往空位子上放元素可以一个空位子一个空位子的放。第一个空位子的元素有n种可能的选取方式，第二个空位子上元素有（n-1）种可能的选取方式，第r个空位子上元素有（n-r+1）种选取方式。因此，根据积的法则，P(n, r)n（n-1）（n-2）（n-r+1）。注意，上述讨论的r-排列，是将r个元素按一定顺序排成一行，若两个排列元素相同，但其顺序不同，也是不同的排列，例如（a，b，c，d）和（b，c，d ，a）是两个不同的4-排列。现在，考虑r-循环排列。一个r-循环排列，是将r个元素按一定顺序排成一个圆圈。两个r-循环排列是不同的，当且仅当一个r-循环排列，不能经过旋转来得到另一个r-循环排列。例如（a，b，c，d）和（b，c，d ，a）是两个相同的4-循环排列。但（a，b，c，d）和（d，c，b，a）是两个不同的4-循环排列。对给定n个元素集合S，其中有多少个r-循环排列？注意到，一个r-循环排列，对应着r个r-排列。例如，排列（a，b，c，d），（b，c，d，a），（c，d，a，b）和（d，a，b，c）是对应于同一个4-循环排列（a，b，c，d），因此，n个元素的集合S，有P(n, r)个r-循环排列。在有些情况下，如四个不同的珠子，做成一个手镯。此时，（a，b，c，d）和（d，c，b，a）完全是同一个手镯。因为，手镯不仅可以旋转，还可以翻转。因此，（d，c，b，a）翻转以后就成了（a，b，c，d）。两个r-翻转循环排列是不同的，当且仅当这两个r-翻转循环排列的元素不同，或者一个排列不能经过翻转和旋转而得到另一个。给定一个n个元素集合S，那么S有多少个r-翻转循环排列呢？易见，它恰有P(n, r)个不同的r-翻转循环排列。3重复排列前面讨论的是一个集合的r-排列数。现在讨论一个多重集（*） 一个多重集，定义为一些对象的总体，但这些对象不必不同，如Sa，a，a，b，b，c就是一个多重集。在多重集里，一个元素的重数，定义为它在该集合中出现的次数，如在Sa，a，a，b，b，c中，a的重数为3，b的重数为2。r个（不必不同）元素的排列总数的问题。可分两种情况讨论之。一重数无限的多重集让我们讨论，以5为首的四位数的电话号码有多少个。因为第一位数固定为5，而第二傔数有10种可能的选取方式，第三位也有10种可能的选取方式，第四位数可能的选取方式也有10种。因此，根据积的法则，以5为首的四位数字电话号码共有103个。象这样允许数字重复出现的排列，称为重复排列。一般地，设S是n个不同元素组成的多重集，其中每个元素的重数都是无限大。S的一个r-重复排列定义为S中r个（不必不同）元素按一定顺序排成一行。两个r-重复排列（a1，a2，ar）和（b1，b2，br）是不同的，当且仅当存在某个i，使ai bi。S的一个r-重复排列，可以理解为有r个编了号的空位子，从S中取出r个（不必不同）元素，将它们放在r个空位子上。由于元素可以重复出现，所以每个空位子上可以放n个不同元素中的任何一个，即是说，每个空位子上的元素有n种可能的选取方式。因此，根据积的法则，不同的r-重复排列数为nr。一个等价的提法是：有n个不同的箱子（相当于n个不同的元素）和r个不同颜色的球（相当于r个空位子）。如果每一个箱子都可以放无限个球（即每一个元素有重数是无限大），那么将r个球放入箱子里，共有多少不同的放法（等价于取出r个（不必不同）元素放在r个空位子上的方式数）？因为每个球可以放到n个箱子中的任何一个，而一个球放入一个箱子，可以视为从n个箱子中选出一个箱子，二个球放入同一个箱子，可以视为这个箱子被选了两次。放r个球的一种放法就对应于（n个箱子的）一个r-重复排列。所以，按积的法则，不同放法的总数为nr。二重数有限的多重集设S是n个不同元素组成的多重集，第i个元素重数为ki，令，则S的不同的k-重复排列数为。对于S中的k-重复排列，如果交换该排列中两个相同元素的位置，则该排列不变。而交换两个不同元素的位置，则可得一个新的k-重复排列。如果将S视为k个元素的集合，其k-排列总数为P(k, k)k!。同理，若S1视为k1个元素的集合，则S1的k1-排列排列总数为k1!，Si视为ki个元素的集合，则Si的ki-排列排列总数为ki!，, Sn视为kn个元素的集合，则Sn的kn-排列排列总数为kn!，于是S中一个k-重复排列与k1!k1!kn!个k-排列相对应。所以S中k-重复排列总数为。例1.3.1 设S是n种不同颜色的球之多重集，第i种颜色的球有ki个，i1，2，n。则共有球数为，那么将k个球放到r个（其中rk）编了号的箱子里，使得每一个箱子最多装一个球，试问共有多少种不同的放法？首先注意，这里的两种放法是不同的，当且仅当存在一个i，使得或者在第i个箱子里的球的颜色不同，或者球的数量不等（一个是一个，一个是零个）。我们构造一个多重集，其中I是第n+1种颜色的集合，且有kn+1rk。则是n+1个不同颜色球的多重集。中的球数为krkr。于是的r-重复排列与S的k-重复排列是一一对应的。而的r-重复排列总数为,这就是所要求的k个球不同的放法。例1.3.2 有一个68的棋盘，如下图示。如果要求只能向正东和正北方向（沿水平和垂直的格子线）行走，那么从A到B有多少条不同的最短路？从A到B的每条最短路都要经过水平方向的8个格子和垂直方向的6个格子。换言之，若每个小格子宽为x，高为y，那么从A到B每条最短路恰有8个x和6个y。反之，8个x和6个y的任何一个重复排列，都对应一条自A到B的最短路，因此，自A到B的最短路的条数为S（多重集）的重复排列数，即。例1.3.3 从A点到B点的最短路中，不通过(x,x)点的有多少？CABD第一步只能右行，到C点。做“C到B的、过某(x,x)点的路”与“D到B的路”的一一对应。则所求的路数为“C到B的路” -“D到B的路”.D到B的路的条数为C(5+8,5)一一对应方法：给定D到B的一条路P，P与对角线的最后一个交点设为S，P在D与S之间的一段关于对角线对称一下，得到C与S间一条路，该路与P上S与B间的一段连接。* (Catalan数，a1a2a3an乘法次序数，n个1和n个0组成2n位的数，从左至右扫描，要求1的个数不小于0的个数。)例1.3.4 n个有标号的顶点，能构成nn-2棵不同的树。树 n-2位的排列（取最小叶节点，删除，记其邻点，重复，直至剩下两个点，则记下了n-2位）123458679 1 3 4 6 7 5 2 892 2 2 5 5 2 8 1 2 3 4 5 6 7 892 2 2 5 5 2 8 1234567894组合什么是组合？组合就是集合中元素的一个无序的选取。设集合S有n个不同的元素，S的一个r-组合就是S中r个元素的一个集合。例Sa，b，c，则a，b是S的一个2-组合。关于S的r-组合的个数，有下述结果：设S是n个元素的集合，则S的r-组合数为。证：因为一个r-组合，可以产生P(r, r)r!个r-排列；另一方面每一个r-排列，都是S中的唯一一个r-组合的一个排列。从而有。例1.4.1将r个相同的球，放到n个不同的箱子里，假如每个箱子最多放一个球，那么有多少种放法？把n个不同箱子的集合记为S，则r个球的一种放法相当于从n个箱子里取出r个箱子。所以r个相同的球放到n个不同箱子里方法的总数为。例1.4.2由0和1组成长度为32的序列中，恰好包含7个1的序列有多少？此例可视为将7个相同的球放到32个不同的箱子里，每种放法就对应于一个包含7个1长度为32的序列。所以包含7个1的长度为32的不同序列个数为。例1.4.3从1到9中选取6个（不同）数字组成六位数中具有4个奇数和2个偶数的六位数有多少个？因1到9中，奇数有5个，偶数有4个。故按积的法则，取4个奇数和2个偶数的组合数为，而每一个这样的组合有P(6,6)个不同的数。所以，所求的六位数共有个。例：1400的正因子个数有多少个？ 1400=23*52*72l*5m*7n l:0,1,2,3 m:0,1,2, n:0,1例：m个人从n个入口进入车站，有多少种不同的进入车站的方式？ 123 | | |12|3| |21|3| m n 1324 | 56 | 789 (m+(n-1)!/(n-1)!例：含数字6、能被3整除的5位整数有多少个？P1P2P3P4P5P5=6 6 3*103 0 3,6,91 2,5,82 1,4,7P56 P4=6 6 3*9*102P56 P46 P3=6 6 3*92*10P56 P46 P36 P26 P1=6 3*930 0,3,91 2,5,82 1,4,7例：从1到300中取3个(不同的)数，其和能被3整除，有多少种取法？1,4,7,2982,5,8,2993,6,9,3003C(100,3) + 1003 可重组合从n个不同元素中可重复地选取出r个来做组合，共可以做C(n+r-1, r)个不同的组合。1 C1 C2 C3 Cr n 1 C1C2+1C3+2Cr+r-1n+r-15组合等式及意义C(m, r)=C(m, m-r)(1-x)n6排列与组合的生成1排列的生成字典序法123456789,123456798123456879123456897,987654321349687521 22634321 a1 右面比a1小的多少个349687521349786521349712568算法：对P1P2P3Pn，从右向左找最长降序子列Pi+1 Pn，记下Pi，找比Pi大的最右边一位Pk，交换Pi和Pk，将Pk右侧子列倒排。P1P2P3PnP1P2P3Pi-1 Pi Pi+1 PnP1P2P3Pi-1 Pi Pi+1 Pk-1 Pk Pk+1PnP1P2P3Pi-1 Pk Pi+1 Pk-1 Pi Pk+1PnP1P2P3Pi-1 Pk Pn Pk+1 Pi Pk-1Pi+1序数法让一个排列P1P2P3Pn 对应一个“序数”：an-1an-2a1 ， 让序数从初值开始递增，对应出所有排列来。序数an-1an-2a1初值为000，0 ai i, 最大序数为(n-1)(n-2)21, 共有n!个序数。000 001 010 011 020 021 100由排列P1P2P3Pn 对应序数an-1an-2a1的规则为：ai：i+1的右边比i+1小的数字的个数例：排列349687521对应序数为64332221，该序数递增1得到下一个序数为64332300，新序数对应排列为 4 1 9 6 8 7 5 2 3.2组合的生成字典序法1234567的4组合1234 1235 1236 12371245 1246 12471256 125712671345 1346 13471356 135713671456 14574567C1C2C3Crr Crnr-1Cr-1n-1r-1 Ci n-r+i算法：对C1C2C3Cr从右向左找第一个Ci n-r+i，对其增加1，其右侧元素递增1。第六章 容斥原理与鸽巢原理1容斥原理一、 容斥原理定理|AB|=|A|+|B|AB|即具有性质A或B的元素的个数等于具有性质A的元素个数与具有性质B的元素个数之和,减去同时具有性质A和B的元素个数.如下图: 定理|ABC|=|A|+|B|+|C|AB|AC|BC|ABC|例一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修 数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学 校共有多少学生？解令M为修数学的学生集合；P 为修物理的学生集合；C 为修化学的学生集合；定理设A1,A2,.,An是有限集合,则定理设Ik是1,2,n的所有k元子集构成的集合，则.又NA，其中N是全集U的元素个数，即不属于A的元素个数等于全集的元素个数减去A的元素的个数。一般有这就是通常所说的容斥原理。（不是容斥原理的一般形式。）二、 错排问题错排问题就是n个元素依次给以标号1，2，n，n个元素的全排列中，求每个元素都不在自己原来位置上的排列的个数。设Ai为数i在第i位上的全体排列，i1,2,n。因数字i不动，故：Ai(n1)!，i1,2,.,n同理AiAj(n2)!，i，j1，2，n，i j每个元素都不在原来位置上的排列数为：12n= n!C(n, 1)(n-1)!+ C(n, 2)(n-2)!+(-1)nC(n, n)0!=n!( 1-1/1!