容斥原理的推广及其在奥数中的应用

《容斥原理的推广及其在奥数中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第30卷第l期成都师范学院学报2014年1月V01．30JOURNALOFCHENGDUNORMALUNIVERSITYJan．2014容斥原理的推广及其在奥数中的应用古传运(四川文理学院数学与财经学院，四川达州635000)摘要：组合计数理论是组合数学中一个最基本的研究方向．它主要研究满足一定条件的安排方式的数目及其计数问题．所用到的基本原理和方法主要有：容斥原理、二项式原理、多项式原理、母函数、递归关系、Polya计数定理以及反演原理等．文章着重介绍了一种基本而且应用广泛的方法——容斥原理方法，同时讨论了它在数学竞

2、赛有关计数问题中的若干应用。关键词：组合计数；容斥原理；数学竞赛；奥数doi：10．3969／j．issn．2095—5642．2014．01．118中图分类号：0157文献标志码：A文章编号：2095-5642(2014)01-0118-04组合数学中的计数问题，是历年来各级数学竞赛命题的热点之一，同时容斥原理方法是解决数学竞赛中计数问题的重要工具．-l掌握它们，就可巧妙而合理地变换纷繁复杂的问题情境，抽象出一个更为明确的数学模型，给以解决．本文主要的工作是在已有结果的基础上，给出了容斥原理的两个推广定理并给以证明，

3、然后讨论了它们在奥数中的应用．1容斥原理1．1基本思想容斥原理是由十九世纪英国数学家西尔维斯特(J．J．Sylvester)首先建立的．我们知道加法原理的基础是分划．但是，要找到一个分划且使其中的所有子集都是易于计数的，有时是困难的，更何况对某些问题也并非一定要这样去做．我们可以把加法原理加以推广，即把有限集合A分成若干个彼此相容的子集A，A，⋯，A．这时显然有IAI

4、，就应设法加回去．如此，我们应做“多退少补”的工作，而完成这项工作的基本思想就是容斥原理．1．2容斥原理的初等形式我们知道，有限集合A，日的并AuB的元素数目IAUBI的计数公式为jAUBl=IAI+lI—IAOBI．对于三个有限集合，B，C的并AuuG，同样有相应的公式，即lAUBUCI=IAI+1BI+Icl—IAnBI—IAncI—tBnCl+lAn曰ncI．类似的，对于有限集合A，，也有fAOBf=IAI+ff—fAUBf．对于三个有限集合A，，C，也有收稿日期：2013437—15基金项目：四川文理学院校级科

5、研项目(2012Z004Z)作者简介：古传运(1982一)，男，河南周口人，助教，硕士，研究方向：应用数学。118第30卷(总第251期)古传运：容斥原理的推广及其在奥数中的应用iAnncJ=lAl+iJ+IcI—lAUBJ—fAucf—IBUCI+iAUBUC1．1．3容斥原理的一般形式1．3．1已有结果定理1。，设A。，A2，⋯，A是有限集合S的子集，

6、s=A1u2u⋯uA，则ls】=lAuAu⋯uAl=IaI一磊lnI+∑=．t／∑>zk∑>jJAnA；nAf一‘+(一1)IanA：n⋯nI(2)定理2’设A，A

7、，⋯，A是有限集合s的子集，则lA1nA2n⋯nAl=IsI_耋+磊nl_㈦EE叫EIAhAnnAI+(一1)IA,NA：n⋯nAl(3)1．3．2主要结果定理3设A，A：，⋯，A是有限集合．s的子集，则lA1nAn⋯nAl=IaI—磊IaUA,-I+磊舌UAsUAI一+(一1)Ia-UA：u⋯uAnI(4)i定理4设A，A：，⋯，A是有限集合．s的子集，则IA1uA2u⋯uI=Isl—壹(5)i=1I+磊lAul一毫磊舌lAUAjUAI+(一1)Ia，uAzu⋯uAl1．3．3主要结果的证明定理3的证明用数学归纳法证

8、明．已知F／,=2时有IAuA2I=IA。I+lA2l—lAnA2l所以IA，nAI=IAl+lA：l—fAuA21．假设fl,一l时有IAlAA2n⋯NA一1ln-I=l4I—XXlAul+n-I磊舌iUAiUAI一·+(一1)～IA,UA2U"'"UA1：i·．．IAnA2n⋯nA一nAI=I(A1nA2n⋯nA一)nAI=IAnA2n⋯RA一ll+IAl—I(A1nA2n⋯nA一)uA但．(A1NA2n⋯nA一1)uA=(A1uA)n(A2uA)n⋯n(A一1uA)·．．1(A1nA2n⋯nA一1)uAI=l(A

9、luA)n(2uA)n⋯n(A一1uA)l=}AuAl+lA2uAl+⋯+jA一uAl一1A。uAuAl一1AuA3uAl一⋯一JA一2uA一1uAl+⋯+(一1)“一IA1uA2u⋯uAlIiuAI—n∑-1IaUA：=_∑IAiuAl—l∑∑AU，UAI+⋯+(一1)一IaA1UA2U⋯uAl，11ll1>l。即AlnA2n⋯