数学与程序设计 章维铣
|A1?A2???An|?|S|??|Ai|??|Ai?Aj|??|Ai?Aj?Ak|???(?1)n|A1?A2???An|
ii?ji?j?k如:m=3,时上式为：
A1?A2?A3=|S|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)－
|A1∩A2∩A3|
推论:至少具有性质P1,P2,...Pm之一的集合S的物体的个数有： | A1∪A2∪....∪Am|=|S|—|A1∩A2∩...∩Am|=
∑|Ai|-∑|Ai∩Aj|+∑|Ai∩Aj∩Ak|+...+(-1)m+1|A1∩A2∩...∩Am|
例4：求从1到1000不能被5，6，和8整除的整数的个数？ （1000-（200+166+125）+（33+25+41）-8=600）
7. 常见递推关系及应用
7.1算术序列
每一项比前一项大一个常数d；
若初始项为h0：则递推关系为 hn=hn-1+d=h0+nd； 对应的各项为：h0，h0+d，h0+2d，....,h0+nd; 前n项的和为(n+1)h0+dn(n+1)/2 例5: 1,2,3,...
例6: 1,3,5,7...等都是算术序列。 7.2几何序列
每一项是前面一项的常数q倍
n-1n
若初始项为h0：则递推关系为 hn=h0qq=h0q；
12n
对应的各项为: h0，h0q，h0q，....,h0q 例7: 1,2,4,8,16,...
例8: 5,15,45,135,...等都是几何序列;
n+1
前n项和为((q-1)/(q-1) )h0 7.3Fibonacci序列
除第一、第二项外每一项是它前两项的和；
若首项为f0为0,则序列为0，1，1，2，3，5，8...递推关系为(n>=2)fn=fn-1+fn-2 前n项的和Sn=f0+f1+f2+...+fn=fn+2-1 例9:以下是Fibonacci的示例:
(1)楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法?
(2)有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子? (3)有n*2的一个长方形方格,用一个1*2的骨牌铺满方格。求铺法总数？ 7.4错位排列 首先看例题：
例10：在书架上放有编号为1,2,....n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能 放在原来的位置上。 例如:n=3时: 原来位置为:123
第 11 页 共 29 页
数学与程序设计 章维铣
放回去时只能为:312或231这两种
问题:求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法) (44)
{1，2，3，....,n}错位排列是{1,2,3,..,n}的一个排列i1i2...in,使得i1<>1,i2<>2,i3<>3,...in<>n 错位排列数列为
0,1,2,9,44,265,....
错位排列的递推公式是:dn=(n-1)(dn-2+dn-1)(n>=3)
n-2
=ndn-1+(-1) 7.5分平面的最大区域数
(1) 直线分平面的最大区域数的序列为: 2，4，7，11，....,
递推公式是: fn=fn-1+n=n(n+1)/2+1 (2)折线分平面的最大区域数的序列为: 2, 7, 16,29, ...,
递推公式是:fn=(n-1)(2n-1)+2n;
(3)封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为: 2, 4, 8, 14,...,
2
递推公式是:fn=fn-1+2(n-1)=n-n+2 7.6 Catalan 数列 先看下面两个例题:
例11: 欧拉多边形分割问题：
设有一个正凸n边形,可以用n-3条不相交的对角线将n边形分成n-2?个互相没有重叠的三角形, 例如n=5,共有图2_1所示的5种方法。
图2_1
对任意给定的一个n边形，任意选定一条边，则该边必是某一组成分割的三角形的一边，它的两个端点也是该三角形的两个端点，另一个端点可以来自于另外n-2个顶点，这个三角形将n边形分成二个多边形，图2_2是选定底边时的情况。
图2_2
根据加法原理和乘法原理有：
Hn=Hn-1+H3Hn-2+??+Hn-2H3+Hn-1 (1)
另外任取一条对角线Pij，将n边形一分为二，二部分分别为多边形，它们的边数之和为n+2，从一个顶点出发的n-3条对角线形成的n边形分割数为：H3Hn-1+H4Hn-2+??+Hn-2H4+Hn-1H3，从n个顶点出发的n(n-3)条对角线形成的n边形分割数为n(H3Hn-1+H4Hn-2+??+Hn-2H4+Hn-1H3)，由于一条对角线有两个端点，所以在上面的统计中，每条对角线出现了两遍，
第 12 页 共 29 页
数学与程序设计 章维铣
r
从所有的对角线出发形成的n边形分割数为：n(H3Hn-1+H4Hn-2+??+Hn-2H4+Hn-1H3)/2。任何一个分割是由n-3条对角线组成的，每个分割在上式中被重复统计了n-3遍，所以：
(n-3)Hn=n(H3Hn-1+H4Hn-2+??+Hn-2H4+Hn-1H3)/2 (2) 将(1)式写成n+1的情况有：
Hn+1=Hn+H3Hn-1+??+Hn-1H3+Hn=(2+2(n-3)/n)Hn=((4n-6)/n)Hn Catalan数的计算公式： Hn+1=c(2n-2,n-1)/n (n=1,2,3,...) 例12: n个+1和n个-1构成2n项 a1,a2,...,a2n
其部分和满足a1+a2+...+ak>=0(k=1,2,3,..,2n)，满足该条件的2n项不同的排列方式为 Cn=C(2n,n)/(n+1)
对应的序列为 1,1,2,5,14,42,132,... 序列1,1,2,5,14,42,132,....叫Catalan数列。 N凸多边形的分割总数Hn=Cn-1
例13：下列问题都是Catalan数列。
(1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票， 剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？
(2)一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ (3)在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? (4)n个结点可够造多少个不同的二叉树?
(5)一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列? 7.7 第二类Stirling数
定义：n个有区别的球放入r个相同的盒子中，要求无一空盒，其不同的方案数 s(n,r)称为第二类Stirling数。
例如：红(k)、黄(y)、蓝(b)、白(w)四种颜色的球，放入两个无区别的盒子里，不允许空盒，其方案数共有如下7种： 方案 1 2 y rbw 3 b ryw 4 W Ryb 5 ry bw 6 rb yw 7 rw yb 第1盒子 r 第2盒子 ybw
所以S(4,2)=7
下面就1≤n≤5,1≤r≤n列出各个S(n,r)的值如下 1 2 3 4 5 1 1 1 1 1 1 2 1 3 7 15 3 1 6 25 4 1 10 5 1 定理：第二类Stirling数满足下面的递推关系
S(n,r)=r·S(n-1,r)+S(n-1,r-1) (n＞1,r≥1)
第 13 页 共 29 页
数学与程序设计 章维铣
证明：设n个不同的球为b1,b2,?,bn，从中取一个球设为b1。把这n个球放入r个盒子无一空盒的方案全体可分为两类：
⑴ b1独占一盒，其余n-1个球放入r-1个盒子无一空盒的方案数为S(n-1,r-1)
⑵ b1不独占一盒，这相当于先将b2,b3,?,bn这n-1个球放入r个盒子，不允许有空盒的方案数共有S(n-1,r)，然后将b1放入其中一盒，这一盒子有r种可挑选，故b1不独占一盒的方案数为r·S(n-1,r)。
根据加法原理，则有
S(n,r)=r·S(n-1,r)+S(n-1,r-1) (n＞1,r≥1)
对于 n=r，或r=1，显然有 S(n,n)=1，S(n,1)=1。
思考题： n个有区别的球放入r个不同的盒子中，要求无一空盒，求不同的方案数。算法提示 可用第二类Stirling数的递推关系先求出S(n,r)，再乘上r!，即得所求方案数。
8. 正整数的分拆
8.1概念
把正整数n表示成k个正整数之和的一种表示法n=n1+n2+??+nk称为 n的一个k部分拆，每个被加数ni称为此分拆的一个分部。n的k部分拆的个数记为P(n,k)；n的所有分拆的个数记为P(n)，即P(n)=ΣP(n,k)，k=1,2,??,n，P(n)称为n的分拆数。在1669年G．Leibnitz给J．Bernoulli的一封信里最先提出了确定分拆数的问题。不过首先系统研究这类计数问题的是Euler，对分拆数的研究是一类重要的计数课题，其内容十分丰富，在数学各分支中有广泛的应用。这里只是一个很初步的介绍。 8.2有序分拆
首先应该说明，以上所说的分拆不考虑各分部的次序。所以n的每个 k部分拆可以唯一确定地表示成如下规范形式：n=n1+n2+??+nk，其中n1≥n2≥??≥nk≥1。这个分拆可简记为(n1,n2,??,nk)≥。一般地，正整数n的有序分拆用有序k元组(a1,??,ak)表示，其中数ai称为这个有序分拆的第i个分部(i=1,??,k)。例如4只有1个3部分拆(2,1,1)，但有3个有序3部分拆(2,1,1)，(1,2,1)和(1,1,2)。一般说来，有序分拆的计数比较容易处理。下面是一个典型的有关结论，它们说明有序分拆的计数常常能归结到可重复组合公式。 正整数 n的一个 k部有序分拆(n1,n2,??,nk)就是k元不定方程 x1+x2+??+xk=n
的一个正整数解，从而可知其总数是C(n-1,k-1)。
三． 计算几何初步
1． 基础知识
1.1两点间的距离公式：
已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2)，则P1和P2两点间的距离为
d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) 1.2线段的中点坐标公式：
已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2)，则线段P1P2的中点坐标为
x=(x1+x2)/2 y=(y1+y2)/2 1.3直线的斜率公式：
第 14 页 共 29 页
数学与程序设计 章维铣
已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2),则线段P1P2所在的直线的斜率为
k=（y2-y1）/(x2-x1) 1.4直线的点斜式方程:
已知：直线过点P0(x0,y0)，斜率为k,则该直线所在的方程为
y=k(x-x0)+y0=kx+y0-kx0=kx+b(与y轴交点的纵坐标:纵截距) 思考题
（1）已知:矩形上三点的坐标p1(x1,y1),p2(x2,y2),p3(x3,y3) （2）求矩形另外一点的坐标p4(x4,y4)。
（3）判断点p(x,y)是在矩形内、矩形外还是在矩形的边上。 2． 线段的相交判断 2.1叉积
已知：平面上的两点的直角坐标分别为p1(x1,y1)，p2(x2,y2)则 （1）该两点相对坐标原点(0,0)的叉积为m=x1*y2-x2*y1 若m>0 则相对坐标原点,点p1在点p2的顺时针方向 若m<0 则相对坐标原点,点p1在点p2的逆时针方向 若m=0 则原点和p1、p2在一条直线上
（2）该两点相对点p0(x0,y0)的叉积为m=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0) 若m>0 则相对p0点,点p1在点p2的顺时针方向 若m<0 则相对p0点,点p1在点p2的逆时针方向 若m=0 则p0和p1、p2在一条直线上
2.2确定两条连续的有向线段p0p1和p1p2在pl点是向左转还是向右转
(1)计算叉积m=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0) （2）判断m
若m>0 则p1点向左拐 若m<0 则p1点向右拐
若m=0 则点p0、p1、p2在一条直线上 2.3确定两条线段p1p2、p3p4是否相交 程序如下： program xdxj; type p=record x, y:real end;
第 15 页 共 29 页