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

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


相关文章:
习题4 容斥原理
第四章 容斥原理 93 习 4-1 题 四 的正整数中素数的个数。 试求不超过 ...2 n , R3 = A1 A2 A3 = 1 由逐步淘汰原理( 由逐步淘汰原理(4.1.2)知...
02 真题解析2012 知识树结构整理
? ?3.3.2多元不等式(考点) ? ? ? ? ? ?4.1.1基础计算(考点) ? ? ...? ?5.4.2方阵问题(考点) ? ? ? ?6.1.1二集合容斥(考点) ? ? ?6.1...
容斥原理2
容斥原理练习题2 1页 免费 2容斥原理及其应用... 38页 20财富值 容斥原理二 20页 5财富值 4.1-4.2容斥原理 42页 免费喜欢此文档的还喜欢 3第三章...
四年级奥数讲义之:容斥原理(2)
四年级数学讲义 奥数:容斥原理( 奥数:容斥原理(2) 教学目标: 教学目标:1、理解容斥原理,会画图分析其中关系,正确的找出答案。 2、培养学生的逻辑思维和数学思考...
第二十讲 容斥原理
十讲 容斥原理(2) [知识提要] 前面讲述过简单的容斥原理, “容”就是...(2)至少能被 2,3,5 中一个数整除的数有多少个? 19、分母是 385 的最简...
第五章 递推关系
第二章 鸽巢原理 第三章 基本计数问题1 第四章 容斥原理1/2 相关文档推荐 ...? D1 = 0 (n ≥ 2), (4 .1.2 ) 等式(4.1.1)和等式(4.1.2)都是...
趣味数学二十五(较复杂的容斥原理)
趣味数学十五(较复杂的容斥原理)_学科竞赛_小学教育_教育专区。趣味数学十...2、90 位外语教师中,有 75 位懂法语,83 位懂英语,65 位懂日语,懂这三种...
4容斥
习题4 容斥原理 6页 1财富值 4.1.2容斥原理(2) 暂无评价 2页 20财富值 ...精锐教育网站:www.1smart.org 2 中小学 1 对 1 课外辅导专家 练习一一个班...
容斥原理 2
13、年前父亲年龄是儿子的7倍,10年后,父亲年龄是儿子的2倍。求父亲、儿子各...2容斥原理及其应... 38页 2下载券 4.1-4.2容斥原理 42页 免费 容斥...
第五讲 二阶容斥原理
2容斥原理及其应用... 38页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
更多相关标签:
容斥原理 | 容斥原理公式 | 三集合容斥原理公式 | 三集合容斥原理 | 容斥原理公式大全 | 三容斥原理非标准公式 | 容斥原理非标准型公式 | 小学奥数容斥原理 |