组合数学教案第9讲

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

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

3、算集合1,2, ···, n 的且不 允许出现 12,23,34, ···, n 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 中

4、具有性质 j p 的排列组成的集合。于是S 中不具有性质 121,., , -n p p p 的排列的集合为 121. -n 。 因而有121. -=n n Q讲稿授 课 内 容备注由容斥原理有121. -=n n Q -=+-=ji ji n i i A A A S 111211. 1(. -+-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 j 1,., 3, 2(

5、-=n j 又由于 j i A A 表示 S 中同时具有性质 j i p p , 的排列所组成的集合。 于是 21A A 中的一个排列可以看作是具有 2(-n 个元素123, 4, 5, ···n 的一个排列,因此有!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 总结:相对位置上有限制的错排也是错排的问题,可以

6、看作是错排 问题的一种特殊情况。定理 2:当 2n 时,有1-+=n n n D D Q 例 有 n 名儿童坐在一旋转木马上,问有多少种方式改变他们的座次,能使得:每个儿童有一个不同的儿童坐在他们的前面。解:问题的实质是求集合 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,

7、 1(n i A i =表示 S 中具有性质 i p 的元素组成的集合,则 n . 21就表示 S 中不具有性质n p p p ,., , 21的元素组成的集合。由容斥原理=+-=ji ji ni i n A A A S 121. nn j i k j iA A A 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 =一般地,对于 11-n k ,有! 1(. 21-=k n A A A k i i i 1. 21=nA A A 故所求方式数为.! 2(1! 1(. 21+-=n n n n 1 1(! 01 1(1 -+ -+-n n n n n n 四、作业和习题布置 课本中 1855-P 。五、归纳总结本节介绍相对位置上有限制的排列问题和相对位置上有限制的排 列问题与错排问题的关系,在应用时技巧性较强,需多加练习。讲 授 课 内