第2章 容斥原理.pptVIP

§3.4 有限制排列定理7 有限制排列 定理 3.7 当n≥2时，Qn=Dn+Dn-1 。 有限制排列 §3.4 有限制排列例1 有限制排列 例 题 例1、有n名儿童围坐在一个旋转木马上，问有多少种方式改变他们的座位，使得每个儿童有一个不同的儿童坐在他们前面。 有限制排列 解：令{1,2,…,n}的所有圆排列的集合为S，有|S|=(n-1)!。令Ai(i= 1,2,…,n)为具有形式i(mod(i+1,n)) 的圆排列的集合， 故所求为方式数为 。由于Ai表示具有形式i(mod(i+1,n))的圆排列的集合，相当于i(mod(i+1,n))作为一个元素出现，|Ai|=(n-2)! (i=1,2,…,n)。而Ai∩Aj可分为(不妨设i＜j)：①mod(i+1,n)=j，相当于i(mod(i+1,n))(mod(i+2,n))作为一个元素出现；②mod(i+1,n)＜j ，相当于i(mod(i+1,n)), j(mod(j+1,n)) 分别作为一个元素出现，均有|Ai∩Aj|=(n-3)!(i,j=1,2,…,n;i≠j)。一般地，n个数字中有k个数字i1,i2,…,ik具有形式i(mod(i+1,n))(j=1,2,…,k;k=1,2,…,n)，相当于n-k个元素的圆排列，有 。而对于k=1,2,…,n，在n个数字中取k个共有 方法。 由乘法法则和容斥原理得 §3.4 有限制排列例2 不含连续对的排列问题 例 题 例2、求集合A={a,b,c,d,e,f,g,h}的全排列中，abc和efgh均不出现的全排列个数。 解：设S为集合A的所有全排列的集合，令A1, A2分别表示出现abc和efgh的排列集合。 根据题意有|S|=8!，A1的排列相当于集合{abc,d,e,f,g,h}的排列，有|A1|=6!，同理|A2|=5!，|A1∩A2|=3!。 根据容斥原理，所求的全排列个数为 |S|-(|A1|+|A2|)+|A1∩A2|=39486 §3.4 有限制排列例3 不含连续对的排列问题 例 题 例3、在重集{4*x, 3*y, 2*z}的全排列中，求不出现xxxx、yyy、zz图像的排列数。 解：设S为重集合的所有全排列的集合，令A1, A2, A3分别表示出现xxxx, yyy, zz的排列集合。 根据题意有|S|=9!/(2!3!4!)，A1的排列相当于集合{X,3*y,2*z}（把4个x看作一个X）的排列，有|A1|=6!/(2!3!)，同理|A2|=7!/(4!2!)， |A3|=8!/(4!3!)，|A1∩A2|=4!/2!，|A2∩A3|=6!/4!，|A3∩A1|=5!/3! ， |A1∩A2∩A3|=3! 。 根据容斥原理，所求的全排列个数为 |S|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A2∩A3|+|A3∩A1|)-|A1∩A2∩A3|=871 §3.5 棋盘排列概念 一般有限制排列 概 念 棋盘（子）多项式 n个元素的排列可看作n个棋子（車）在n×n棋盘C上的一种布局，布子规定称无对攻规则，即同一行（列）有且仅有一个棋子。 棋盘C可推广为任意形状，令rk(C)表示k个棋子布列棋盘C上的方案数，称 为棋盘C的棋盘多项式，规定r0(C)=1，包括C=Φ时。 如r1( )=1，r1( )=2，r1( )=2，r2( )=1 R( )=1+x， R( )=1+2x， R( )=1+2x+x2 §3.5 棋盘排列加法 一般有限制排列 概 念 棋盘（子）多项式 设C(i)为C的某一指定格子所在行与列去掉后的所得棋盘，C(e)为C是仅去掉该格子后的所得棋盘。如 C： C(i)： C(e)： 显然有rk(C)=rk-1(C(i))+rk(C(e))，R(C)=xR(C(i))+R(C(e))。 如R( )=1+x， R( )=xR(Φ )+R( )=x+(1+x)=1+2x， R( )= xR( )+R( )=x(1+x)+(1+x)=1+2x+x2 * §3.5 棋盘排列乘法 一般有限制排列 概 念