组合数学专题

1目录组合数学专题.........................................................................................................................................1一、加法原理和乘法原理.............................................................................................................1二、集合的排列和组合.................................................................................................................1三、整数的分拆.............................................................................................................................2四、容斥原理.................................................................................................................................3五、递推关系.................................................................................................................................5六、Polya计数理论.......................................................................................................................71组合数学专题一、加法原理和乘法原理加法原理：假设事件A有m种选取方式，事件B有n种选取方式，则选A或B共有m+n种方式。加法原理的一般形式：设有n个有限集合S1,S2,…,Sn满足)1(njiSSji，则niinSSSS121乘法原理：假设事件A有m种选取方式，事件B有n种选取方式，则选A及B共有m×n种方式。乘法原理的一般形式：设有n个有限集合S1,S2,…,Sn满足)1(njiSSji，则niinSSSS121※当某一计数问题可以分组考虑时，可运用加法原理；当某一计数问题可以分步考虑时，可运用乘法原理。例1从1~300之间选取3个数，要求这3个数的和能够被3整除，问有多少种选取方案？解：将1~300的数分成如下三组：A={1,4,7,…,298}，即被3除都余1；B={2,5,8,…,299}，即被3除都余2；C={3,6,9,…,300}，即被3除都余0，能被3整除。3个数之和能被3整除只有如下两种情况：（1）3个数被3除的余数均相同，即或均能整除，或均余1，或均余2；（2）3个数中一个被3除尽，一个余1，另一个余2。则3个数同属于A、B或C的方案数为C(100,3)，分别属于A、B或C的方案数为1003，根据加法原理，取3个数使其相加之和能被3整除的方案数为：3C(100,3)+1003=1485100二、集合的排列和组合排列：从n个不同的元素中，有次序地选取r个元素，称为从n中取r个的排列，其排列数记为P(n,r)或rnP。当r=n时，称此排列为全排列。对于满足r≤n的正整数n和r，有)!(!)1()1(),(rnnrnnnrnP圆排列：从n个不同元素中取出r个元素，仅按元素间的相对位置而不分首尾地围成一圈，这种排列称为圆（环状）排列。n个元素的r圆排列数为：)!(!),(rnrnrrnP，特别地，n个元素的n圆排列数为(n-1)!。2例2有4个中国人和4个美国人围桌而坐，要求同一国的人不相邻，求共有多少种坐法？解：先让4个中国人隔位坐下，属于圆排列问题，共有P(4，4)/4=3！=6种坐法，然后4个美国人插空而坐，这实际上是4个人的全排列问题，因为这4个人已经让中国人隔开了，共有4!种坐法，运用乘法原理，共有3!×4!=144种坐法。组合：从n个不同元素中选取r个元素而不考虑其次序时，称为从n中取r个的组合，其组合数记为rnC，C(n，r)或rn。对于满足r≤n的正整数n和r，有)!(!!!),(),(rnrnrrnPrnC。例3某火车站有6个入口，每个入口每次只能进一个人，则9个人共有多少种进站方案？解：因9个人进站时在每个入口都是有序的，则（1）先构造9个人的全排列，共有9!个；（2）选定一个全排列，加入5个分隔符，将其分成6段，则第i段对应着第i个入口的进站方案，例如：＊＊△＊△＊＊＊△＊△＊△＊（△表示分隔符＊表示一个人）则进站方案为：760,485,726!9!5!14!9)5,14(!9C※生成排列和组合的程序。三、整数的分拆正整数n的一个k分拆是把n表示成k个正整数的和，即n=n1+n2+…+nk（k≥1）。如果等式右边k个正整数的不同次序被看作是不同的分拆，则称为有序分拆。正整数的有序拆分可以理解为n个相同的球放进k个有区别的盒子，每个盒子可以多于一个球，每种方案就是对正整数n的一种拆分。例4把m个同样的苹果放在n个同样的盘子中，允许有空盘子，问有多少种不同的方法。解：令f(m,n)表示把m个同样的苹果放在n个同样的盘子中的方案数，下面分情况讨论：（1）当m=1时，只有一种放法：把1个苹果放在其中任意一个盘子中，由于题目说明盘子是同样的，所以，不管这个苹果放在哪个盘子中，都属于一种放法；（2）当n=1时，只有一种放法：把所有苹果都放在这个盘子中；（3）当mn时，由于最多有m个盘子能放到苹果，其余的盘子都是多余的（空盘子），即m=n1+n2+…+nm+0+…+0（n1≥n2≥n3≥……≥nm≥0）实际上就是将整数m进行至多m分拆，也就是f(m,m)；（4）当m=n时，此时可分为两种情况：①没有空盘子，即每个盘子里放一个苹果；②至少有一个盘子是空的，即f(m,n-1)；（5）当mn时，此时可分为两种情况：①没有空盘子，可以每个盘子里先放一个苹果，再将剩下的苹果放到盘子里，即f(m-n,n)；②至少有一个盘子是空的，即f(m,n-1)。综上所述，得到如下递推关系式：共m项1当m=1或n=1f(m,m)当mn1+f(m,n-1)当m=nf(m-n,n)+f(m,n-1)当mnf(m,n)=3四、容斥原理容斥原理实际上是一种间接的计数方法。例5求{1,2,…,n}的1不在第一个位置上的全排列的个数。解：设i1i2…in是{1,2,…,n}一个全排列，因1不在第一个位置上，所以i1≠1，下面分别用直接计数和间接计数两种方法来计算此类排列的个数。（1）直接计数：将i1≠1的所有全排列按照i1的取值分成n-1类：若i1=k∈{2,3,…,n}，则i2…in是{1,…，k-1,k+1,…,n}的一个全排列，所以{1,2,…,n}的使i1=k的全排列个数为(n-1)!。由于k可取2,3,…,n，由乘法原理，i1≠1的全排列数为(n-1)(n-1)!。（2）间接计数：{1,2,…,n}的全排列数为n!，若i1=1，则i2…in是{2,3,…,n}的全排列，共有(n-1)!，所以i1≠1的全排列数为：n!-(n-1)!=(n-1)(n-1)！容斥原理：设集合S的子集A1具有性质P1，A2具有性质P2，…，An具有性质Pn，则集合S至少具有性质P1,P2,…,Pn之一的元素个数为：|A1∪A2∪…∪An|=(|A1|+|A2|+…+|An|)-(|A1∩A2|+|A1∩A3|+…+|A1∩An|+(|A2∩A3|+…|A2∩An|+…|An-1∩An|)+(|A1∩A2∩A3|+…+|An-2∩An-1∩An|)……+(-1)n-1|A1∩A2∩…∩An|即|ninniijjkkjiniijjiniiniiAAAAAAAAA11111)1(则集合S不具有性质P1，P2，…，Pn的元素个数为：nnnAAASAAAAAA212121即：niijnnjkkjiniijjiniiiniAAAAAAAAASA121111)1(有禁止位置的错排问题：集合S={1,2,…,n}的一个错排是该集合的一个满足条件的i≠ri的全排列i1i2…in，即集合{1,2,…,n}的没有一个数字在它的自然顺序位置上的全排列。通常用Dn表示集合S的错排个数。例如，n=1时，集合{1}没有错排D1=0；n=2时，集合{1,2}有1个错排D2=1，为21；n=3时，集合{1,2,3}有2个错排D3=2，为231,312；n=4时，集合{1,2,3,4}有个9错排D4=9，分别是：2143,2341,2413,3142,3413,3431,4123,4312,4321。定理1对于任意正整数n，有)!1)1(!31!21!111(!nnDnn。证明：设Ai表示ri=i的全排列（i=1,2,…,n），由于ri已确定，所以|Ai|=(n-1)!同理|Ai∩Aj|=(n-2)!，……，|A1∩A2∩…∩An|=14则12121212111(1)!(1)!(2)!(1)0!121111!(1(1))1!2!3!!nnnnnnnniijijkniijiijikjnnDAAAAAASAAASAAAAAAAAAnnnnnnnnn例66人参加会议，入场时随意的将帽子挂在衣架上，走时再顺手戴一顶走，问没一人拿对的概率？解：P=!66D=1-11!+12!-13!+14!-15!+16!≈0.368不相邻的排列：集合S={1,2,…,n}的不相邻的排列是该集合上不出现12,23,…,(n–1)n这些模式的全排列。通常用Qn表示集合S的不相邻的排列个数。例如：n=2时，Q2=1，21是唯一满足要求的全排列；n=3时，Q3=3，213,321,132是3个满足要求的全排列；n=4时，Q4=11，4132,4213,4321,3142,3241,3214,2143,2413,2431,1324,1342是11个满足要求的全排列。定理2对于任意正整数n，有：111!(1)!(2)!(1)1!121nnnnnQnnnn证明：设S为{1,2,…,n}的全排列，则|S|=n!，定义性质集合P={p1,p2,…,pn}，其中Pi：出现i(i+1)模式（1≤i≤n–1）则Ai：S中满足性质Pi的全排列的集合Ai中每个排列是集合{1,2,…,i–1,i(i+1),i+2,…,n}的一个全排列，则|Ai|=(n–1)!。同理，Ai∩Aj中每个排列是集合{1,2,…,i–1,i(i+1),i+2,…,j(j+1),…,n}的一个全排列，则|Ai∩Aj|=(n–2)!（1≤i≠j≤n–1）。一般的有：|Ai1∩Ai2∩…∩Aik|=(n–k)!（1≤Ai1≠Ai2≠…≠Aik≤n–1)则12111!(1)!(2)!(1)1!121nnnnnnQAAAnnnn例7某班有8位学生排成一队，第2天再排队时，所有同学都不希望他前面的同学与前一天相同，问有多少种排法？解：问题即是求S={1