加载中…
个人资料
ty1108
ty1108
  • 博客等级:
  • 博客积分:0
  • 博客访问:1,105
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

容斥原理的猜测与证明

(2010-10-19 19:08:31)
标签:

校园

容斥原理的猜测与证明

 

摘要:容斥原理研究的是若干个有限集合的并集所包含的元素的个数,是一个为了计数有限集合中元素的个数而得到的结论,与集合的性质用以解决一类有限集合元素个数的问题。本文主要通过两个集合的容斥原理,猜测并证明三个集合和n个集合的容斥原理。

 关键词:容斥原理  猜测 证明

 

前言 

我们已经学习过两个集合的容斥原理,猜测并证明三个集合和n个集合的容斥原理。

.两个集合的容斥原理  n(AB)=n(A)+n(B) -n(AB)

.三个集合的容斥原理的猜测和证明

21由两个集合的容斥原理  n(AB)=n(A)+n(B) -n(AB)猜测三个集合的容斥原理。

猜测公式1n(ABC)=n(A)+n(B)+n(C) -n(AB)-n(BC)-n(AC).

反例证明:A={a},  B={a,b},   C={a,b,c}

则有公式1n(ABC)=n(A)+n(B)+n(C) -n(AB)-n(BC)-n(AC)=1+2+ 3-1-2-1=2

很明显,n(ABC)=3

所以,公式不正确

原因分析:由于所举反例中,ABC={a}≠Ф ,所以会使该类元素在运用公式计算中被全部除去,考虑到这一点,推出猜测公式2

 

猜测公式2n(ABC)=n(A)+n(B)+n(C) -n(AB)-n(BC)-n(AC).+n(ABC)

22三个集合的容斥原理 

n(ABC)=n(A)+n(B)+n(C) -n(AB)-n(BC)-n(AC)+n(ABC)

证明:n(ABC)=n((AB)C)

M=AB

则原式=n(MC)

      =n(M)+n(C)-n(MC)

= n(AB)+n(C)-n((AB)C)

= n(A)+n(B)-n(AB)+n(C)-( n(A)+n(B)-n(AB))C

= n(A)+n(B)-n(AB)+n(C)-n(AC)-n(BC)+n(ABC)

         整理得:n(ABC)

                =n(A)+n(B)+n(C) -n(AB)-n(BC)-n(AC) +n(ABC)

  n(ABC)=n(A)+n(B)+n(C) -n(AB)-n(BC)-n(AC)+n(ABC)

.n个集合的容斥原理的猜测与证明

31   n个集合的容斥原理的猜测

假设有集合A1A2A3A4……An,由对三个集合的容斥原理的猜测、证明过程可知,求几个集合所包含的元素的个数,可以先将其中每个集合的元素个数全部相加,得到a所求元素个数。

显然,如果所有集合的之间任意若干个集合的交集均为Ф,那么a即为n(A1A2A3……An), 但如果这些集合中存在若干集合同时有的元素,那么所得a就多加了某些元素,所以在a的基础上减去一些被重复计数的元素。

   假设在A1An这些集合中,只有任意两个集合存在相同的元素,即AiAj≠Ф(i,j=1,2,3……,ij),在任意三个或三个以上的集合中不存在这些集合均有的相同元素,那么,

n (A1A2A3A4……An)

= n (A1)+n (A2)+n (A3) ……+ n (An)

-n(A1A2)- n(A1A3) ……- n(A1An)- n(A2A3)- ……-n(An-1An)     (1)

   如果不符合上述要求,即在任意三个或三个以上不同集合中存在这些集合均有的元素,那就意味着在(1)式中,有一部分元素又被重复减去了,需要重新加上。

   所以,以此类推,综上所述,为了便于计数,得出了n个集合的容斥原理。

n (A1A2A3A4……An)

= n (A1)+n (A2)+n (A3) ……+ n (An)-n(A1A2)- n(A1A3) ……- n(A1An)- n(A2A3)- ……-n(An-1An)+n(A1A2A3)+ n(A1A2A3)+ ……+ n(An-2An-1An)- ……+……+(-1)n-1.n(A1A2A3……An)
3
2   n个集合的容斥原理的证明

证明:n (A1A2A3A4……An)

= n (A1)+n (A2)+n (A3) ……+ n (An)-n(A1A2)- n(A1A3) ……- n(A1An)- n(A2A3)- ……-n(An-1An)+n(A1A2A3)+ n(A1A2A3)+ ……+ n(An-2An-1An)- ……+……+(-1)n-1.n(A1A2A3……An)

用数学归纳法进行证明
 
设:S1= n (A1)+n (A2)+n (A3) ……+ n (An)

S2= n(A1A2)+ n(A1A3) ……+ n(A1An)+ n(A2A3)+ ……+n(An-1An)

S3= n(A1A2A3)+ ……+ n(An-2An-1An)

……

Sn =n(A1A2A3……An)
  
求证:A=n(A1
A2A3A4……An)= S1-S2+ S3+……+(-1)n-1Sn

证明:当n=2时,A=n(A1A2)=n(A1)+n(A2) -n(A1 A2)= S1-S2

假设:当n=k(k>=2)时,A=n (A1A2A3A4……Ak)= S1-S2+ S3+……+(-1)k-1Sk 等式成立。

n=k+1时,

A= n( (A1A2A3A4……Ak) Ak+1)

 = n (A1A2A3A4……Ak)+n(Ak+1)-n((A1A2A3A4……Ak) Ak+1)

= n (A1A2A3A4……Ak) +n(Ak+1)-n((A1Ak+1) (A2Ak+1) (A3Ak+1) (AkAk+1))

∵ 当n=k时,等式成立

A= n (A1A2A3A4……Ak) +n(Ak+1)-(n (A1Ak+1)+ n (A2Ak+1)+ ……+n(AkAk+1)-n(A1A2Ak+1)-n(A1A3Ak+1) -……- n(Ak-1AkAk+1)+ ……+(-1)k.n(A1A2A3……Ak+1)

    = S1-S2+ S3+……+(-1)k-1Sk+n(Ak+1)-(n (A1Ak+1)+ n (A2Ak+1)+ ……+n(AkAk+1)-n(A1A2Ak+1)-n(A1A3Ak+1) -……- n(Ak-1AkAk+1)+ ……+(-1)k.n(A1A2A3……Ak+1)

     = S1-S2+ S3+……+(-1)kSk+

综上所述,当n>=2,n (A1A2A3A4……An)

= n (A1)+n (A2)+n (A3) ……+ n (An)-n(A1A2)- n(A1A3) ……- n(A1An)- n(A2A3)- ……-n(An-1An)+n(A1A2A3)+ n(A1A2A3)+ ……+ n(An-2An-1An)- ……+……+(-1)n-1.n(A1A2A3……An)

 

结束语

  我们在学习过程中,通过所学知识,触类旁通,不断探索,我们不仅能掌握所学知识,而且还会有新的收获,能更一步激发我们学习数学的兴趣。

 

 

 

作者:

高一(11)

费晔 马嫣砾 徐轶舟 潘宁馨 朱今雨 *田园

0

阅读 评论 收藏 转载 喜欢 打印举报
前一篇:永远的诺贝尔
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇永远的诺贝尔
      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有