摘 要：容斥原理是组合数学中一个重要原理，在计数研究中占有重要地位.本文介绍了它在数论、图论、排列组合中的广泛应用，并给出了它在不同学科中的运用实例以及方法，并对一些常见题型作了相关探讨.56239

毕业论文关键词：容斥原理，推论，实例，方法

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  设 是有限集合   是同集合 有关的 个性质  设 是集合 中具有性质 的元素构成的集合    是 中不具有性质 的元素构成的集合   则 中不具有性质 的元素个数为

 = -  -        推论      源'自:优尔-'论/文'网"www.youerw.com

例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整除的数    

同理而 表示能同时被5  6  7整除的数     故         

由容斥原理  1与1000 之间不能被5  7  8 整除  但能被6整除的整数个数有     

    在这里  例1是容斥公式的直接运用  而例2实际已是容斥原理的一种变式  我们