第一类夫妻问题的解法课件

《第一类夫妻问题的解法课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、夫妻问题研究12.2容斥原理的应用---夫妻问题n对夫妻围圆桌而坐，男女相间，每个丈夫都不和他的妻子相邻，有多少种可能的方案？第一类夫妻问题:圆桌座位有编号第二类夫妻问题:圆桌座位无编号2第一类夫妻问题第二类夫妻问题3夫妻问题—方桌形式n对夫妻在方桌的两边(每边各n个座位)而坐，男女相间，每个丈夫都不和他的妻子相邻，有多少种可能的方案？第三类夫妻问题:方桌座位有编号第四类夫妻问题:方桌座位无编号4第四类夫妻问题第三类夫妻问题②①③④⑥⑦⑤⑧5第六类夫妻问题(夫妻不相对

2、)第五类夫妻问题(夫妻不相对)②①③④⑥⑦⑤⑧62.1容斥原理定理2.2设S是有限集，A,B,C为S的子集，则：

3、A∪B∪C

4、=

5、A

6、+

7、B

8、+

9、C

10、-

11、A∩B

12、-

13、A∩C

14、-

15、B∩C

16、+

17、A∩B∩C

18、.定理2.1设S是有限集，A,B是S的子集，则：

19、A∪B

20、=

21、A

22、+

23、B

24、-

25、A∩B

26、.（容斥原理）容斥原理研究有限集合的交或并的计数。7定理2.3设S是有限集，A1,…,An均为S的子集，则：（1）（2）8第一类夫妻问题的解法第一步:设出已知集合设S是n对夫妻围圆桌而坐，男女相间的所

27、有坐法集合.设Ai是满足S的条件,而且第i对夫妻坐在一起的坐法集合,其中,1≤i≤n.9第一类夫妻问题的解法第二步:求出已知集合

28、S

29、用乘法原理:步骤一:步骤二:步骤三:先选n个不相邻的位置;将n位丈夫安排在这n个位置上;将n位妻子安排在剩余n个位置上;10第一类夫妻问题的解法第三步:求出集合用乘法原理:分四个步骤步骤一:先安排这k对夫妻以外的下标最小的一对夫妻中丈夫入座.步骤二:再安排这k对夫妻入座.步骤三:安排余下的n-k位妻子入座.步骤四:安排余下的n-k-1位丈夫入座.11第一类夫妻问题的解

30、法第四步:将所求数据代入公式12研究论文1.证明一个引理:引理:1至m的整数中选2k个数,使这2k个数构成k对相邻数的选法数等于2.解决其它类的夫妻问题13课程论文格式1.题目(居中)2.作者(居中)3.摘要4.关键词5.正文6.参考文献14