组合数学教案第9讲..

1、教案教研室:数学分析教研室 教师姓名：授课时间：课程名称专业课选讲 授课专业和班级 数学 0603 授课内容 3.4 相对位置上有 限制的排列问题 授课学时 2 学时教学目的应用容斥原理解决实际问题教学重点总集 S 及各个子集iA 的建立教学难点涉及的集合中的元素的个数的求法教具和媒体使用板书教学方法讲授法、讨论法教学过程包括复习旧课、引入新课、重点难点讲授、作业和习题布置、问题讨论、归纳总结及课后辅导等内容时间分配（90 分钟一、复习旧课重集的r 组合错排问题二、引入新课三、重点难点讲授1、相对位置上有限制的排列问题2、有限制的排列问题与错排问题的关系3、应用四、作业和习题布置五、归纳总结1

2、0 分 5 分 30 分 20 分 15 分 5 分 5 分板书设计 3.4 相对位置上有限制的排列问题1、相对位置上有限制的排列问题2、有限制的排列问题与错排问题的关系3、应用讲授新拓展内容课后总结教研室主任签字年月曰讲稿授课内容备注一、复习旧课1、重集的-r 组合 2、错排问题 二、引入新课1n 个小学生列队散步，除第一个学生外，每个学生前面都有另一个学生,由于学生们不喜欢每天排在自己前面的同学总是一个人，他们希望每天都要改变一个排在自己前面的那个人，问有多少种方式改变他们 的位置。三、重点难点讲授这个问题实质上是一个相对位置上有限的排列问题。将它抽象成一般的数学问题:对于给定的正整数 n

3、 ,计算集合1,2,；n 的且不允许出现 12,23,34, ； n 1(-的全排列个数 n Q。对于这个问题，有下列定理，其结论就是该问题的解。定理 1:对于 1n 有! 2(21! 1(11! -? -+-? -=n n n n n Q n ! 1111(. 1? ? -+-n n n 证明:设 S 是集合1,2,；n !n S =令 1,., 2, 1(-=n j p j 表示 S 中的排列具有形式 1(+j j 出现这一性 质。 而 j A 1,.,2, 1(-=n j 表示 S 中具有性质 j p 的排列组成的集合。于是S 中不具有性质 121,., , -n p p p 的排列的集

4、合为 121. -n。因而有21. -=n n Q稿授课内容备注由容斥原理有121.二n n Q 2Z2=+-=ji ji n i i A A A S 1112111(.-工并+-刀 n n j i k j iA A A A A A由于 j A 表示 S 中具有性质 j p 的排列所组成的集合。于是 1A 中的一个排列可以看作是具有 1(-n 元素12, : n 的一个排列，有1(1-=n A 同理1(-=n A j1,. ., 3, 2(-=n j 又由于 j i A A 表示 S 中同时具有性质 j i p p ,的排列所组成的集 合。于是 21A A 中的一个排列可以看作是具有 2(-n

5、 个元素123, 4, 5, 的一个 排列,因此有!2(21-=n A A 同理! 2(31-=n A A !2(-=n A A ji 一般地，有!(.21k n A A A ki i i -=将以上值代人 n Q 表达式可得! 2(21! 1(11! -? -+-? -=n n n n n Q n讲稿授课内容备注111 1(. 1? -+-n n n 总结:相对位置上有限制的错排也是错排的问题，可以看作是错排 问题的一种特殊情况。定理 2:当 2r 时,有1-+=n n n D D Q 例有 n 名儿童坐在一旋转木马上，问有多少种方式改变他们的 座次,能使得:每个儿童有一个不同的儿童坐在他们

6、的前面。解:问题的实质是求集合n，,2, 1 的圆排列中不出现 12, 23,；n n 1(-, 1n 的 圆排列个数。设 S 是集合n，,2, 1 的所有圆排列组成的集合，则!1(-=n S 又设 i p 1,., 2, 1(-=n i 表示 S 中圆排列具有 1(+i i 形式这一性质。n p 表示圆排列具有 1n 形式这一性质。令,.,2, 1(n i A i =表示 S 中具有性质 i p 的元素组成的集合，则 n21 就表示 S 中不具有性质n p p p ,., , 21 的元素组成的集合。由容斥原理i ni i n A A A S 121. . nn j i k j iA A A

7、 A A A. 1(. 21-+-刀工耨于 1A 是所有圆排列中出现 12 的圆排列的集合,故 1A 的一个圆排列可以看成是具有 1-n 个元素的集合n ,., 3, 12 的一个圆排列，因此有讲稿授课内容备注!2(1-=n A 同理!2(-=n A i ni ,., 3, 2-类似,21A A 中的一个圆排列可以看成是具有2-n 个元素的集合n，,4, 123 的一个圆排列，故有3(21-=n A A 同理! 3(-=n A A j i，2, 1, ; (n j i j i = 一般地，对于半 l-wwn 有! 1(. 21-=k n A A A k i i i 1. 21=nA A A 故所求方式数为! 2(1! 1(. 21+-? -=n nn n 1 1(! 01 1(1? ? -+? -+-n nn nn n 四、作业和习题布置 课本中 1855-P。五、归纳总结本节介绍相对位置上有限制的排列问题和相对位置上有限制的排列问题与错排问题的关系，在应用时技巧性较强，需多加练习。讲授课内容参