特殊排列组合.docVIP

特殊排列组合 一、特殊排列 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 （1－1/1! + 1/2! -1/3! +1/4! - … + (-1)n*/n!） 证明：设S是由｛1，2, …，n｝构成的所有全排列的集合，则|S|＝n！。 设Ai是在｛1，2, …，n｝的所有排列中由第i个位置上的元素恰好是i的所有排列组成的集合，则有：|Ai|＝（n－1）！ 同理可得，|Ai ∩ Aj|＝（n－2）！。 …… 一般情况下，有：|Ai1 ∩ Ai2 ∩…… ∩ Aik|＝（n－k）！ 因为Dn是S中不满足性质P1，P2，…，Pn的元素的个数，所以由容斥原理得： ＝n！－C（n，1）*（n－1）！＋C（n，2）*（n-2）！－……＋(-1)n*C（n，n）*0！ ＝n！x （1－1/1! + 1/2! -1/3! +1/4! - … + (-1)n*/n!） 定理4’：D（n）＝ （n－1）（D（n-1）＋D（n－2）） 证明：原问题等价于把编号 1n的小球放到编号1n的盒子里n个球全放错的情况1号盒子可以选n，? 共（n-1）种选择不妨设1号盒选择2号球1） 2号盒选择1号球，剩下 （n-2）个球去错排，有 （n-2）种情况2 2号盒不选择1号球，则后面总有一个盒子选择1号球，我们可以把1号球换成2号球，对问题没有影响，此时就相当于对（n-1）个球去错排，有（n-1）种情况于是(n)=(n-1)?（D（n-1）+（n-2）n个不同的元素分成k组的组合称为n个不同元素的k—组合。 定理5：对于一个n个不同元素的k—组合，若第i组有ni个元素（i=1, 2, …，k），则不同的分组方法数为 证：我们把分组的过程安排成相继的k个步骤。第一步，从n个不同元素中选n1个，有种方法；第二步，从n－n1个元素中选n2个有种方法；…；第k步，从n－（n1+n2+…+nk－1）个元素中选nk个元素，有－（n1+n2+…+nk－1）种方法，再由乘法原理得证。 6．可重组合 定义6：从n个不同元素中任取r个允许元素重复出现的组合称为n个不同元素的r—可重组合。 定理6：n个不同元素的r—可重组合的个数为Crn+r－1 . 证：设（a1 , a2 ,…，ar）是取自{1，2，…，n}中的任一r可重复组合，并设a1≤a2≤…≤ar .令 bi=ai+i－1(1≤i≤r). 从而b1=a1 , b2=a2+1 , b3=a3+2,…, br=a+r－1r . 显然下面两组数是一对一的：a1≤a2≤a3≤…≤ar , 1≤a1a2+1a3+2…ar+r－1≤n+r－1. 设 A={（a1 , a2 ,…，ar）| ai∈{1，2，…，n }，a1≤a2≤…≤ar }， B={（b1, b2,…，br）| bi∈{1，2，…，n+r－1 }，b1 b2…br}. 则由A、B之间存在一一对应，故|A|=|B|=Crn+r－1 . 三、组合公式 公式1：C（n，r）＝ C（n，n－r） 公式2：C（n，r）＝ C（n－1，r）＋ C（n-1，r-1） ｛杨辉三角，PASCAL公式｝ 公式3：C（n，0）＋C（n，1）＋…＋C（n，n）