容斥原理

姓名：杨猛志 学号：1307022019 班级：应数二班

摘要：在解决计数问题时，用间接计数的方法往往比直

接计数来得容易，所以我们将讨论计数常用的间接计数方法-----容斥原理及其在几个问题上的应用。

关键词：容斥原理，容斥原理的应用。 正文：

定理：设S是有限集合，p1,p2,,pm是同集合S有关的m

个性质，设Ai是S中具有性质Pi的元素构成的集合(1im)，Ai是S中不具有性质Pi的元素构成的集合(1im)，则S中不具有性质

p1,p2,,pm的元

m素个数为

A1A2AmsAii1,m1,2,的2组合AiAjm1,2,,m的3组合AiAjAk(1)A1A2Am由此定理还能得出一个推论

推论：设S是一有限集合，p1,p2,,pm是同S有关的m个性质，

记Ai为S中具有性质Pi的元素所构成的集合(1im)，则S中至少具有一个性质Pi的元素个数为

A1A2AmAii1m,m1,2,的2组合AiAj,m1,2,的3组合AiAjAk

(1)m1A1A2Am知道容斥定理后，我们紧接着来看一下容斥定理的应用。 1.具有有限重数的多重集合的r组合数。 2.错排问题

定理：对任意正整数n，有

1111Dnn!1(1)n

n!1!2!3! 3.有禁止模式的排列问题。

定理：对任意正整数n，有

n1n1Qnn!(n1)!(n2)!12

n1(1)n11!n1 4.实际依赖于所有变量的函数个数的确定

知道了容斥原理和其应用之后，我们就通过一些例题来更好的理解容斥原理。

例1.求S=3?abc的组合数。解：令S·a,?则有S的组合数为10+3-112==66.102设集合A是S的10组合全体，则A=66，现在要求在10组合中a的个数小于或等于3,b的个数小于或等于4,c的个数小于或等于5的组合数。定义性质集合P=P1,P2,P3,其中P1：10组合中a的个数大于或等于4；P2：10组合中b的个数大于或等于5；P3：10组合中c的个数大于或等于6.将满足性质Pi的10组合全体记为A（i1i3).那么A1中的元素可以看作是由S的10-4=6组合再拼上4个a构成的，所以10-4+3-18A1===28.10-46类似地，有105317A221,1055106316A315,10641045313A1A23,104511046312A1A31,10460A2A30,A1A2A30.而a的个数小于或等于3,b的个数小于或等于4,c的个数小于或等于5的10组合全体为A1A2A3.由容斥原理知，他的元素个数为A1A2A3=AA1A2A3A1A2A1A3A2A3A1A2A366(282115)(310)00