教案
教研室:数学分析教研室 教师姓名:授课时间: 课程名称 专业课选讲 授课专业和班级 数学 0603授课内容 §3.4相对位置上有限制的排列问题 授课学时 2学时 教学目的 应用容斥原理解决实际问题
教学重点 总集 S 及各个子集 i A 的建立
教学难点 涉及的集合中的元素的个数的求法 教具和媒体使用 板书 教学方法 讲授法、讨论法
教 学 过 程 包括复习旧课、引入新课、重点难点讲授、置、问题讨论、归纳总结及课后辅导等内容 时间分配 (90分钟
一、复习旧课 ①重集的 r 组合 ②错排问题
二、引入新课
三、重点难点讲授
1、相对位置上有限制的排列问题
作业和习题布
2、有限制的排列问题与错排问题的关系
3、应用
四、作业和习题布置
五、归纳总结
10分 5分 30分 20分 15分 5分 5分
板 书 设 计 §3.4相对位置上有限制的排列问题
1、相对位置上有限制的排列问题
2、有限制的排列问题与错排问题的关系
3、应用 讲授新 拓展内容 课后总结
教研室主任签字 年 月 日 讲 稿 授 课 内 容 备注
一、复习旧课
1、重集的 -r 组合
2、错排问题
二、引入新课
n 个小学生列队散步,除第一个学生外,每个学生前面都有另一个
学生,由于学生们不喜欢每天排在自己前面的同学总是一个人,他们希 望每天都要改变一个排在自己前面的那个人,问有多少种方式改变他们 的位置。
三、重点难点讲授
这个问题实质上是一个相对位置上有限的排列问题。将它抽象成一 般的数学问题:对于给定的正整数 n ,计算集合{1,2, ···, n }的且不 允许出现 12,23,34, ···, n n 1(-的全排列个数 n Q 。
对于这个问题,有下列定理,其结论就是该问题的解。 定理 1:对于 1≥n 有 ! 2(21! 1(11! -⎪⎪⎭ ⎫
⎝⎛-+-⎪⎪⎭⎫ ⎝⎛--=n n n n n Q n ! 111 1(...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 的排列的集合为 121...-n 。 因而有 1 21...-=n n Q
讲 稿 授 课 内 容 备注
由容斥原理有 1 21...-=n n Q ∑∑≠-=+-=j i j i n i i A A A S 1 1 1 211...1(...--≠≠-++- ∑n n j i k j i A 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(-=n j 又由于 j i A A 表示 S 中同时具有性质 j i p p , 的排列所组成的集合。 于是 21A A 中的一个排列可以看作是具有 2(-n 个元素{123, 4, 5, ···n }的一个排列,因此有
! 2(2 1-=n A A 同理 ! 2(31-=n A A ! 2(-=n A A j i 一般地,有 ! (...21k n A A A k i i i -= 将以上值代人 n Q 表达式可得 ! 2(21! 1(11! -⎪⎪⎭ ⎫
⎝⎛-+-⎪⎪⎭⎫ ⎝⎛--=n n n n n Q n 讲 稿 授 课 内 容
备注 ! 111 1(...1⋅⎪⎪⎭ ⎫
⎝⎛---+--n n n 总结:相对位置上有限制的错排也是错排的问题,可以看作是错排 问题的一种特殊情况。
定理 2:当 2≥n 时,有 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, 1(n i A i =表示 S 中具有性 质 i p 的元素组成的集合,则 n ...21就表示 S 中不具有性质 n p p p ,..., , 21的元素组成的集合。由容斥原理 ∑∑≠=+-=j
i j i n i i n A A A S 1 21...n n j i k j i A A A A A A ...1(...21-++- ∑≠≠由于 1A 是所有圆排列中出现 12的圆排列的集合, 故 1A 的一个圆排 列可以看成是具有 1-n 个元素的集合 { }n ,..., 3, 12的一个圆排列,因此有 讲 稿 授 课 内 容 备注 ! 2(1-=n A 同理 ! 2(-=n A i n i ,..., 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=n A A A 故所求方式数为 ...! 2(1! 1(...21+-⎪⎪⎭ ⎫
⎝⎛--=n n n n 1 1(! 01 1(1⋅⎪⎪⎭
⎫ ⎝⎛-+⎪⎪⎭⎫ ⎝⎛--+-n n n n n n
四、作业和习题布置 课本中 1855-P 。
五、归纳总结
本节介绍相对位置上有限制的排列问题和相对位置上有限制的排 列问题与错排问题的关系,在应用时技巧性较强,需多加练习。
讲 授 课 内 容 参考教材： 稿 备注
1、教材：孙世新 编 组合数学（第三版） 电子科技大学出版社出版 1999
2、孙淑玲 编 组合数学引论 中国科学技术大学出版社
3、卢开澄 编 组合数学 清华大学出版社
4、杨振生 编 组合数学及其算法中国科学技术大学出版社
