频道栏目
读书频道 > 其他 > 组合数学(原书第五版)
1.6 例子:相互重叠的圆
2012-10-07 17:15:39     我来说两句
收藏   我要投稿

本文所属图书 > 组合数学(原书第五版)

本书系统地阐述组合数学基础、理论和方法,侧重于组合数学的概念和思想,论述了鸽巢原理、排列与组合、二项式系数、容斥原理及应用、递推关系和生成函数、特殊计数序列、二分图中的匹配、组合设计、图论、有向图...  立即去当当网订购

考虑平面上以普通位置相互重叠的n个圆γ1,γ2,…,γn。说到相互重叠(mutually overlapping),我们指的是每一对圆相交于两个不同点15(因此,不允许不相交和相切的圆)。而说到普通位置(general position),我们指的是不存在只有一个共同点的三个圆1。这n个圆在平面内构建若干区域。我们的问题是确定如此构建的区域的数量。

设hn等于构建的区域数。容易计算出h1=2(圆γ1的里面和外面两个区域),h2=4(这就是两个集合的维恩图),h3=8(这就是三个集合的维恩图)。因为从刚才的计算可以看出区域数量好像是成倍增加,因此猜测h4=16。然而,一张图可以很快说明h4=14(参见图1-8)。


 

解决这一类计数问题的一个方法就是尝试着确定当从n-1个圆γ1,γ2,…,γn-1变到n个圆γ1,γ2,…,γn时出现的区域变化。用更一般的语言表述如下:我们尝试着确定hn的一个递推关系,即用前面的值表示hn。

于是,我们假设n≥2而且在平面上已经画出普通位置下相互重叠的圆γ1,γ2,…,γn-1,它们构建了hn-1个区域。然后加入第n个圆γn使得在普通位置下有n个相互重叠的圆。前n-1个圆中的每一个圆都与第n个圆相交出两个点,因为这些圆都处于普通位置上,所以我们得到2(n-1)个不同点P1,P2,…,P2(n-1)。这2(n-1)个点把圆γn分割成2(n-1)条弧:P1和P2之间的弧,P2和P3之间的弧,…,P2(n-1)-1和P2(n-1)之间的弧,以及P2(n-1)与P1之间的弧。这2(n-1)条弧中的每一条弧都把由前面n-1个圆γ1,γ2,…,γn-1构成的区域分成两个区域,创建出额外2(n-1)个区域。因此,hn满足下面的关系:


 

利用递推关系(1.4)可以得到由参数n表示的hn的公式。通过反复利用(1.4)2,我们得到


 

因为h1=2,且1+2+…+(n-1)=n(n-1)/2,我们得到


 

当n=1时,这个公式是成立的,因为h1=2。我们可以用数学归纳法给出这个公式的形式证明。
_____________________________________________
1 不要求这些“圆”是圆的。只要是封闭的凸曲线就可以。
2 即一而再地利用(1.4)直到得到h1,我们知道这个值等于2。
 

您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:1.5 例子:最短路径问题
下一篇:1.7 例子:Nim游戏
相关文章
图文推荐
排行
热门
最新书评
特别推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站