论文总字数：6287字
摘 要
容斥原理是组合数学中一个重要原理，在计数研究中占有重要地位.本文介绍了它在数论、图论、排列组合中的广泛应用，并给出了它在不同学科中的运用实例以及方法，并对一些常见题型作了相关探讨.关键词：容斥原理，推论，实例，方法
Abstract: The indusion-exdusion principle is an important principle in combinatorics, which occupies an important position in the counting methods. This paper introduces its widespread use in the number theory, the graph theory and permutations and combinations, which gives many actual examples and methods in different subjects and discusses some common questions.
keywords: permutations principle, inference, case, method
目 录
1 前言...........................................................4
2 容斥原理的定理及推论...........................................4
2.1 德摩根定理...................................................4
2.2 容斥原理.....................................................4
3 容斥原理的应用.................................................8
3.1 欧拉函数的应用...............................................8
3.2 图着色问题...................................................8
3.3 整数解的上界.................................................9
3.4 组合恒等式的证明............................................11
3.5 概率问题....................................................11
3.6 排列问题....................................................12
3.6.1 全错位排列................................................12
3.6.2 部分错位排列..............................................12
绪论............................................................14
参考文献........................................................15
致谢............................................................16
1 前言
容斥原理是组合数学中一个古老的原理，它产生于排列问题，并逐渐推广，广泛应用于几何，代数等众多领域，并用以解决各类数学学科中的实际问题，意义深远．
2 容斥原理的定理及推论
2.1 德摩根定理 若和是集合的子集 则
1）=
2）=
德摩根定理的推广 设为的子集 则
1）=
2）=
2.2 容斥原理
定理2.2.1 设是有限集合 是同集合有关的个性质 设是集合中具有性质的元素构成的集合 是中不具有性质的元素构成的集合 则中不具有性质的元素个数为
=--
推论
例1 用0到9这10个数字作不允许重复的全排列，要求排除125，572，438，632，49数字的出现，求满足这些条件的排列数.
解 令分别为出现125 572 438 632 49的排列构成的集合 出现125数字的排列相当于将125作为一个单元参加的排列 故 类似地
由于125与572不在同一排出现 故
类似地有
由于125 572 438不可能在同一排出现 故
同理
=
故所求数为
例2 1与1000之间不能被5,7,8整除，但能被6整除的整数有多少个？
解 令 记分别为1与1000之间能被5 7 8 6整除的整数集合 表示既能被5 又能被6整除的数
剩余内容已隐藏，请支付后下载全文，论文总字数：6287字
该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找;
