组合数学(第五章_容斥原理)讲解.ppt

组合数学课件 制作讲授：王继顺 目录（1） 目录（2） 第5章 包含排斥原理 §5.1 包含排斥原理 教学目标： 1．记住容斥原理的内容，理解其证明方法； 2．能运用容斥原理解决具有有限重复数的多重集合的r组合数问题、错排问题、有禁止模式的排列问题； 3．掌握棋子多项式的形式，能运用棋子多项式的形式解决有限制位置的排列问题。 教学重点：容斥原理的内容及其证明方法；运用容斥原理解决具有有限重复数的多重集合的r组合数问题、错排问题、有禁止模式的排列问题； 教学难点：容斥原理的内容及其证明方法;有禁止模式的排列问题。 §5.1 包含排斥原理 §5.1 包含排斥原理定理1-1 §5.1 包含排斥原理定理1-2 §5.1 包含排斥原理定理3 §5.1 包含排斥原理定理3 §5.1 包含排斥原理定理4 §5.1 包含排斥原理例2 §5.1 包含排斥原理例9 §5.1 包含排斥原理例4 §5.1 包含排斥原理例7 §5.1 包含排斥原理例8 §5.1 包含排斥原理例8 §5.1 包含排斥原理例3 §5.1 包含排斥原理 例1 §5.2 重集的r-组合 §5.2 重集组合例1 §5.2 重集的r-组合 第5章 习题 §5.3 错排问题定理5 §5.3 错排问题例1 §5.3 错排问题例2 §5.3 错排问题例3 §5.3 错排问题例4 §5.3 错排问题例5 §5.3 错排问题推论1 §5.3 错排问题推论2 §5.4 有限制排列概念 §5.4 有限制排列定理6 §5.4 有限制排列定理7 §5.4 有限制排列例1 §5.4 有限制排列例2 §5.4 有限制排列例3 §5.5 棋盘排列概念 §5.5 棋盘排列加法 §5.5 棋盘排列乘法 §5.5 棋盘排列概念 §5.5 棋盘排列加法 §5.5 棋盘排列乘法 §5.5 禁区排列概念 §5.5 禁区排列定理8 §5.5 禁区排列例1 §5.5 禁区排列例2 §5.6 广义容斥原理概念 §5.6 广义容斥原理定理9 §5.6 广义容斥原理例1 §5.6 广义容斥原理例2 第5章 小结 第5章 习题 结束 §5.4 有限制排列 概 念 如{a1,a2,…,an}为{1,2,…,n}的一排列，计算其不允许出现12,23,…,(n-1)n的全排列个数，即相对位置有限制的排列数，记为Qn 。 注：错排限制是对元素排列位置的限制，计算的是绝对禁用位置； 有限制排列讲的是相对禁用位置，它限制的是对元素之间的相邻关系的限制 。 5.4.1 有限制排列 §5.4 有限制排列 定理 3.6 当n≥1时，有Qn=n!-C(n-1,1)×(n-1)!+C(n-1,2)× (n-2)!+…+(-1)n-1C(n-1,n-1)×1! 3.4.1 有限制排列 证明：令{1,2,…,n}的所有排列集合为S，有|S|=n!。令Ai(i=1,2,…, n-1)为具有形式i(i+1)的排列的集合，故有 。由于Ai表示具有形式i(i+1)的排列的集合，相当于i(i+1)作为一个元素出现，|Ai|=(n-1)!(i=1,2,…,n-1)。而Ai∩Aj可分为（不妨设i＜j）：①i+1=j，相当于i(i+1)(i+2)作为一个元素出现；②i+1＜j ，相当于i(i+1)、j(j+1)分别作为一个元素出现，均有|Ai∩Aj|=(n-2)! (i,j=1,2,…,n-1;i≠j)。一般地，n个数字中有k个数字i1,i2,…,ik具有形式ij(ij+1)(j=1,2,…,k;k=1,2,…,n-1)，相当于n-k个元素的排列，有 。而对于k=1,2,…,n，在n-1个数字中取k个共有 方法。由乘法法则和容斥原理得 §5.4 有限制排列 定理 3.7 当n≥2时，Qn=Dn+Dn-1 。 3.4.1 有限制排列 §5.4 有限制排列 例 题 例1、有n名儿童围坐在一个旋转木马上，问有多少种方式改变他们的座位，使得每个儿童有一个不同的儿童坐在他们前面。 3.4.1 有限制排列 解：令{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))作为一个元