当前位置:首页 >> 数学 >>

4.1.2容斥原理(2)


五年师范学校统编教材《数学》

课题

容 斥 原 理 ( 2)

教学目标:1、知识目标:理解、掌握容斥原理,掌握补集的思想、遇难则反的思想方法。 2 、 能力目标:提高学生运用容斥原理解决实际问题的能力。 教学重点、难点:容斥原理及其应用 教学方法:讲授法、练习法 教学过程: 一、 设置情景:上节课我们学习了容斥原理在数论中的应用,这节课我们继续学习容斥原 理在排列中的应用。 二、 进行新课: 1.错排问题 问题:n 个有序的元素应有 n!个不同的排列,如若一个排列使得所有的元素不在原来的位置 上,则称这个排列为错排。

解:Dn=n!(1-1+1/2!-1/3!+……) = 2.二重错排问题 问题:n 个有序的元素 a1a2……an,如若一个全排列,使得 a1 不在位置 1,2 上,a2 不在位置 2, 3 上,…… an-1 不在位置 n-1,n 上 an 不在位置 n,1 上。则称这个排列为二重错排。

解: 方法一(棋盘多项式+容斥原理):较麻烦,略。 方法二(隔位组合+容斥原理): 1) 先解决有 k 个元素放错位置问题 相当与(1,2)(2,3)(3,4)……(n-1,n)(n,1)选 k 组 即 1,2,2,3,3,4,……n-1,n,n,1 中选 k 个隔位数方案 - 首位、末位同时选 1 的 k 个隔位数 方案(或直接用圆隔位组合公式,详见《可重组合,隔位组合与多重排列组合》一文)得 C (k, 2n-k+1) - C(k-2, (2n-4)-(k-2)+1) =C (k, 2n-k+1) - C(k-2, 2n-k-1) =(2n/2n-k) C(k, 2n-k)。 所以 n 个元素至少有 k 个元素放错位置的方案数为(2n/2n-k) C(k, 2n-k)×(n-k)!
1

五年师范学校统编教材《数学》

2) 根据容斥原理:全排列 - 1 个元素放错方案 + 2 个元素放错方案 - …… 化简可得解。 相隔圆排列问题 问题:设有 n 对夫妇(n 个男的、n 个女的)男女不必相间围成一圈,如果任何一对夫妇都不 相邻,问有多少种排法? 解:容斥原理 2n!/2n-C (n,1)(2n-1)!/(2n-1)×21+ C (n,2)(2n-2)!/(2n-2)×22……化简为

相隔二重排列问题 问题:设有 n 对夫妇(n 个男的、n 个女的)男女相间围成一圈,如果任何一对夫妇都不相邻, 问有多少种排法?

解: 方法一:1、先女人定位,园排列 n!/n=(n-1)!

2、再男人定位,即二重圆错排问题。 3、两数相乘 例 1 设是个不相同元素的一个给定的全排列,求每个元素都不再原位置的全排列的总数 三、 课堂练习:P181、2。 四、 小结、巩固: 五、 布置作业:P181、3。 六、 板书设计(略)

2



相关文章:
更多相关标签: