特殊排列组合.doc

特殊排列组合一、特殊排列1圆排列定义1：从几个元素中任取r个不同元素，仅按元素之间的相对位置而不分首尾排成一个圆圈，这种排列称为n个不同元素的r圆排列。r圆排列数记为.定理1：证：对n个不同元素取r个的任一圆排列，均有r种不同的方式展开成r个不同的直线排列，且不同的圆排列展开的直线排列也彼此不同，故有r=，得证。2重复排列定义2：从n个不同元素中允许重复的任取r个元素排成一列，称为n个不同元素的r可重复排列.定理2：n个不同元素的r可重排列数为nr.证：在按顺序选取的r个元素中，每个元素都有n种不同的选法，故由乘法原理有，其排列数为nr.3不全相异元素的全排列定义3：设n个元素可分为k组，每一组中的元素是相同的，不同组间的元素是不同的，其中第i组的元素个数为ni(i=1, 2, , k ), n1+n2+nk=n . 则这n个元素的全排列称为不全相异元素的全排列。定理3：n个元素的不全相异元素的全排列个数为证：先把每组中的元素看做是不相同的，则n个不同元素的全排列数为n!，然后分别将每个组的元素还其本来面目看成是相同的，则在这n!个全排列中，每个排列都重复出现了n1！n2!nk！次，所以不全相异元素的全排列数4错位排列 定义4：设（a1，a2，an）是1，2，n的一个全排列，若对于任意的i 1，2，n，都有a2 i，则称（a1，a2，an）是1，2，n的一个错位排列。一般用Dn表示1，2，n的错位排列的个数。定理4：Dn n！x （11/1! + 1/2! -1/3! +1/4! - + (-1)n*/n!）证明：设S是由1，2, ，n构成的所有全排列的集合，则|S|n！。设Ai是在1，2, ，n的所有排列中由第i个位置上的元素恰好是i的所有排列组成的集合，则有：|Ai|（n1）！同理可得，|Ai Aj|（n2）！。一般情况下，有：|Ai1 Ai2 Aik|（nk）！因为Dn是S中不满足性质P1，P2，Pn的元素的个数，所以由容斥原理得： n！C（n，1）*（n1）！C（n，2）*（n-2）！(-1)n*C（n，n）*0！ n！x （11/1! + 1/2! -1/3! +1/4! - + (-1)n*/n!）定理4：D（n） （n1）（D（n-1）D（n2）证明：原问题等价于把编号 1，2，n的小球放到编号1，2，n的盒子里，n个球全放错的情况。1号盒子可以选2，n， 共（n-1）种选择。不妨设1号盒选择2号球，则：1） 2号盒选择1号球，剩下 （n-2）个球去错排，有 D（n-2）种情况2） 2号盒不选择1号球，则后面总有一个盒子选择1号球，我们可以把1号球换成2号球，对问题没有影响，此时就相当于对（n-1）个球去错排，有D（n-1）种情况，于是D(n)=(n-1)（D（n-1）+D（n-2）例1：对于键盘输入的n（n17）个不同的字母，用它们组成长度为n的字符串，但每个字母不允许重复使用，并且每个字母都不能出现在自己序号的位置上。计算并输出有多少种符合条件的字符串。二、特殊组合5多组组合定义5：将n个不同的元素分成k组的组合称为n个不同元素的k组合。定理5：对于一个n个不同元素的k组合，若第i组有ni个元素（i=1, 2, ，k），则不同的分组方法数为证：我们把分组的过程安排成相继的k个步骤。第一步，从n个不同元素中选n1个，有种方法；第二步，从nn1个元素中选n2个有种方法；第k步，从n（n1+n2+nk1）个元素中选nk个元素，有（n1+n2+nk1）种方法，再由乘法原理得证。6可重组合定义6：从n个不同元素中任取r个允许元素重复出现的组合称为n个不同元素的r可重组合。定理6：n个不同元素的r可重组合的个数为Crn+r1 .证：设（a1 , a2 ,，ar）是取自1，2，n中的任一r可重复组合，并设a1a2ar .令 bi=ai+i1(1ir).从而b1=a1 , b2=a2+1 , b3=a3+2, br=a+r1r .显然下面两组数是一对一的：a1a2a3ar ,1a1a2+1a3+2ar+r1n+r1.设 A=（a1 , a2 ,，ar）| ai1，2，n ，a1a2ar ， B=（b1, b2,，br）| bi1，2，n+r1 ，b1 b2br.则由A、B之间存在一一对应，故|A|=|B|=Crn+r1 .三、组合公式公式1：C（n，r） C（n，nr）公式2：C（n，r） C（n1，r） C