葡萄的英语-金陵十三钗豆瓣

经典的组合数学题
加法和乘法原理+一点点的容斥定理
例：
1)求小于10000的含1的正整数的个数
2)求小于10000的含0的正整数的个数
解：
1)小于10000的不含1的正整数可看做4位数, 但0000除外。
故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个
另: 全部4位数有10
4
个,不含1的四位数有9
4
个,
含1的4位数为两个的差:10
4
－9
4
=3439个
2)含0和含1不可直接套用。0019含1但不含0。
在组合的习题中有许多类似的隐含的规定，要特别留神。
不含0的1位数有9个，2位数有9
2
个，3位数有个，4位数有9
4
个
不含0小于10000的正整数有9+9
2
++9
4
=(－9)( 9－1)=7380个
含0小于10000的正整数有9999－7380=2619个

部分全排：n个不同的人选r个出来排列的种数（一般 不说 可重 意即 无
重。）
在上述定义中，一个排列的第1位有n个选择，第2位有(n-1)个选择，第k
位有(n -k+1)个选择，故P(n,r)=n(n-1)…(n-r+1)。
（无重）排列与球放入盒子的方案的对照：
从a,b,c 3个元素中取2个的排列相当于将2个不同的球放入3个不同的盒
子里，每盒最多一个球的方案。

组合数的物理意义：
从a,b,c 3个字母中取2个做组合，每个组合对应2!个排列：
ab： ab ,ba；
ac： ac ,ca；
bc： bc ,cb。

部分组合：组合的计数相当于将r个相同的球放入n个不同的盒子里，每盒最多
一个球的方案数
注意分类讨论计算！
例：从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？
解: 将[1,300]分成3类：
A={i|i≡1(mod3)}={1,4,7,…,298},

B={i|i≡2(mod3)}={2,5,8,…,299},
C={i|i≡3(mod3)}={3,6,9,…,300}.
要满足条件，有四种解法：1 )3个数同属于A;2)3个数同属于B;3)3个数同属
于C;4)A,B,C各取一数.
故共有3C(100,3)+1003=485100+1000000=1485100。
注意模型转换！
例：某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案
有多少？
解: 一进站方案表示成：00 其中表示人，表示门框，其中
是不同元，是相同元。n个门只 用n-1个门框。任意进站方案可表示成上面
14个元素的一个排列。
[解法1]标号可产生5!个14个元的全排列。故若设x为所求方案，则x·5!=14! ∴
x=14!5!=726485760
[解法2]在14个元的排列中先确定的位置，有C (14,5)种选择，在确定人的位
置，有9！种选择。故C(14,5)·9!即所求
[解 法3]把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9
号。1号有6种选择；2号 除可有1号的所有选择外，还可（也必须）选择当与
1号同一门时在1号的前面还是后面，故2号有7种 选择；3号的选择方法同2
号，故共有8种。以此类推，9号有14种选择。故所求方案为[6]
9
。

圆排列和项链排列的定义：
一般而言，若两个项链排列通过转动、平移和翻转能够重合，就看做是同一个项
链排列。
从n个字符中取r个不同的字符构成圆排列的个数为 P(n,r)r，(0≤r≤n)。
从n个字符中取r个不同的字符构成项链排列的个数为P(n,r)2r，(3≤r≤n)。

组合应用：

简单格路问题 |(0，0)→(m，n)|=，从(0，0)点出发 沿x轴或y轴的正方向
每步走一个单位，最终走到(m，n)点，有多少条路径？
解:

无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一 个x
表示x方向上的一步，一个字母y表示y方向上的一步。 则(0,0) → (m,n)的每一条路径可表示为m个x与n个y的一个多重排列。将每一个多重排列的x与y

分别 编号，可得m!n!个m+n元的无重全排列。
设所求方案数为P(m+n；m，n),则P(m+n；m,n)·m!·n!=(m+n)!
故P(m+n;m,n)=＝=C(m+n,m) 设c≥a,d≥b,则由(a,b)到(c,d)的简单
格路数为|(a,b)(c,d)|=


在上例的基础上若设m接触包括穿过
解:
从(0,1)点到(m,n )点的格路，有的接触x=y，有的不接触。对每一条接触x=y
的格路，做(0,1)点到第一个接触 点部分关于x=y的对称格路，这样得到一条从(1,0)
到(m,n)的格路。


容易看出从(0,1)到(m,n)接触x=y的格路与(1,0)到(m,n)的格路(必穿过x= y)一一
对应。
故所求格路数为

若条件改为 可接触但不可穿过，则限制线要向下或向右移一格，得x－y=1，
(0,0)关于x－y=1的对称点 为(1, -1)。
所求格路数为

格路也是一种常用模型。

在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一
名冠军，问要举行几场比赛？
解: 99场比赛。
一种常见的思路是按轮计场，费事。
另一种思路是淘汰的选手与比赛(按场计)集一一对应。

(Cayley定理)n个有标号的顶点的树的数目等于n
n-2
。
生长点不是叶子，每个生长点是[1,n]中的 任一元.有n种选择。两个顶点的树
是唯一的





鸽巢原理
鸽巢原理的几种形式，应用鸽巢原理的技巧，Ramsey问题，Ramsey数。
【学习指南】
容斥原理

|A∪B∪C|=|A|+|B|+|C|－|A∩B|
图 －|A∩C|－|B∩C|＋
|A∩B∩C|
先利用文氏图对两个，三个集合的并有直观 的了解。然后推导n个公式的并
的势的计数公式及几个集合的补的交的势的计数公式。
例：求[1，20]中2或3的倍数的个数.
解:2的倍数是：2，4，6，8，10，12，14，16，18，20。一共10个
3的倍数是：3，6，9，12，15，18。一共6个
答案不是10+6=16个，因为6，1 2，18被重复记数，应该减去，所以答案应
为10+6-3=13个。
在论域U，补集 中，

DeMorgan定理
，有：




DeMorgan原理的推广：
设、、...是 U 的子集，则：





一个学校只有三门课程：数学、物理、化学。已知修这三门 课的学生分别有170、
130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学 的20
人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？
解:令:M为修数学的学生集合；
P 为修物理的学生集合；

C 为修化学的学生集合；
则 |M|=170,|P|=130,|C|=120,
＝45,=20,=22,=3
＝|M|+|P|+|C|---
＝170+130+120-45-20-22+3
＝336
即学校学生数为336人。
例1：求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。
解:设A为ace作为一个元素出现的排列集，
B为 df作为一个元素出现的排列集，
A∩B为同时出现ace、df的排列集。
∴ |A|=4!；|B|=5!；|A∩B|=3!；
根据容斥原理，不出现ace和df的排列数为：

例2：求从1到500的整数中能被3或5除尽的数的个数。
解:令A为从1到500的整数中被3除尽的数的集合，
B为被5除尽的数的集合,
A∩B为能同时被3和5整除的数的集合。





故能被 3或 5整除的数的个数为：|A∪B|=|A|+|B|－|A∩B|=166+100－33＝233
例 3：求由a,b,c,d四个字母构成的位符号串中，a,b,c,d至少出现一次的符号串数
目。 < br>解:令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号
串中每一位都 可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号
串的个数应是，即：
|A|=|B|=|C|=；
|A∩B|=|A∩C|=|B∩C|＝；
|A∩B∩C|=1
a，b，c至少出现一次的n位符号串集合即为：

例4：求小于120的素数的个数。
解:因为=121,故不超过120的合数必然是2、3、5、7的倍数，而且不超 过120
的合数的因子不可能都超过11。
设为不超过120的数i的倍数集，i＝2,3,5,7

，，
，，
，
，
，，
，，
，


∴
，
，
＝120-||-||－||－||+|∩ |-|∩|+|∩|+|∩|+|∩|+|∩|-|
∩∩|-|∩∩|-|∩∩|-|∩∩|+|∩∩∩ |=120-（60+40+24+17）+
（20+12+8+8+5+3）-（4+2+1+1）= 27。
注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7这四
个数，又包含了1这个非素数。2， 3，5，7本身是素数。故所求的不超过120
的素数个数为: 27+4-1=30。

例5：用26个英文字母作不允许重复的全排列，要求排除dog， god，gum，depth，
thing字样的出现，求满足这些条件的排列数。
解:所有排列中，令：
为出现dog的排列的全体；
为出现god的排列的全体；
为出现gum的排列的全体；
为出现depth的排列的全体；

为出现thing的排列的全体；
出现dog字样的排列，相当于把dog作为一个单元参加排列，
故||＝24!类似有：||＝||＝24!，||＝||＝22!
由于god,dog不可能在一个排列中同时出现，故：|∩|＝0；
类似有：|∩|=0；|∩|=0。
由于dog和gum可以在dogum字样中同时出现，故：|∩|＝22!
类似的理由god和depth可以在godepth字样中同时出现，故|∩|=20!
god和thing可以在thingod字样中同时出现，故：
|∩|=20!；|∩|＝0；|∩|＝19!
|∩|=|∩|＝20!|∩∩|＝0；
|∩∩|=0；
|∩∩|＝|∩∩|＝0；
|∩∩|＝|∩∩|＝0；
|∩∩|＝|∩∩|＝0
由于god、depth、thing不可以同时出现，故|∩∩|＝0；|∩∩|＝17!
其余多于3个集合的交集均为空集，不一一列举。故所求的满足要求的排列
数为：
26! －3×24!－2×22!＋22!＋4×20!＋19!－17!＝26!－3×24!－22!＋4×20! ＋19!
－17!

错排问题 就是 n个元素依次给以标号1，2，…，n。N 个元素的全排列中，求
每个元素都不在自己原来位置上的排列数。设Ai为数i在第i位上的全体排列，
i＝1,2,...,n．因数字i不动，故：||＝(n－1)!，i＝1,2,...,n。
同理| ∩ | ＝(n－2)!，i,j＝1,2,...n，i≠j。……。
每个元素都不在原来位置上的排列数为：

＝
＋
－……±





例1数1，2，…，9的全排列中，求偶数在原来位置上，其余都不在原来位置的
错排数目。
解:实际上是1,3,5,7,9五个数的错排问题，总数为：
5!－C(5,1)4!+C(5,2)3!－C(5,3)2!+C(5,4)1!－C(5,5)＝44。
例2：在8个字母A,B,C,D,E,F,G,H的全排列中，求使A,C,E,G四个字母不在原< br>来位置上的错排数目
解:8个字母的全排列中令,,,分别为表A,C,E,G 在原来位置上的排列，则：
|∩∩∩|＝8!－C(4,1)7!+C(4,2)6!－C(4, 3)5!+C(4,4)4!＝40320－
20160+4320－480+24＝24024 例3：求8个字母A,B,C,D,E,F,G,H的全排列中只有4个元素不在原来位置上的
排列 数。
解:8个字母中只有4个不在原来的位置上，其余4个字母保持不动，相当于4

< br>个元素的错排， 其数目为：4!(1－11!+12!－13!+14!)＝9。
故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)×9＝
630。
1.有限制排列
错排问题就是一种有限制条件的排列。

例：4个x，3个y，2个z的全排列中，求不出现xxxx、yyy、zz图象的排列数
解:出现xxxx图象的排列记为
出现yyy图象的排列记为
出现zz图象的排列记为
xxxx作为一个单元出现进行排列，考虑到y重复3次,z重复2次，故
||＝6!(3!2!)=60，
||＝7!(4!2!)=105，
||＝8!(4!3!)＝280，
|∩|＝4!2!=12,
|∩|＝5!3!=20,
|∩|＝6!4!=30,
|∩∩|＝3!=6,
4个x，3个y，2个z的全排列中不同的排列数为9(4!3!2!)＝1260。所以
|∩∩|
＝1260－||－||－||+|∩|+|∩|+|∩|-|∩∩|
＝1260－(60+105+280)+(12+20+30)－6 = 871。

例1： 某校有12个教师，已知教数学的有8位，教物理的有8位，教化学的5
位；数、理5 位，数、化4位，理、化3位；数理化3位。问教其他课的有几位？
只教一门的有几位？只好教两门的有 几位？
解:令教数学的教师属于，教物理的属于，教化学的属于。则
＝12，
＝||＋||＋||＝8+6+5＝19；
＝|∩|+ |∩|+|∩|＝12；
＝|∩∩|＝3；
故教其他课的老师数为：
＝ － +－＝2
恰好一门的教师数：
＝－2 + 3＝4
恰好教两门的老师数为：
＝－3＝3

n 对夫妻围坐问题
设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种
可能的方案？
解:不妨设 n 个女人先围成一圈，方案数为( n－1 )! 。对任一这样的给定方案，
顺时针给每个女人以编号1,2,…,n。设第i号与第 i + 1号女人之间的位置为第 i
号位置，1≤i≤n－1。第 n 号女人与第1 号之间的位置为第 n 号位置。设第 i 号

女人的丈夫的编号也为第 i 号， 1≤i≤ n。让 n 个男人坐到上述编号的 n 个位
置上。设 是坐在第 i号位置上的男人，则 ≠ i ，i + 1，1≤i≤n－1；≠n，1。
这样的限制也即要求在下面3行n列的排列中
1 2 3 … … n-1 n
2 3 4 … … n 1
… …
每列中都无相同元素。满足这样的限制的排列 ··· 称为二重错排。
设二重错排的个数为，原问题所求的方案数就是( n－1)！。
设 为 = i 或 i + 1 (1≤i≤n－1 )，an = n或1的排列 ··· 的集合。
则||= 2 (n－1)!，关键是计算

也就是从( 1 , 2 ) ( 2 , 3 ) …( n－1, n ) ( n , 1)这n对数的k 对中各取一数，且互
不相同的取法的计数。这相当于从1 , 2 , 2 , 3 ,3 ,4,…,n－1, n－1, n , n , 1中取 k
个互不相邻数的组合的计数，但首尾的 1 不能同时取。回想无重复不相邻组合
的计数：
C'(n,r) = C(n－r + 1,r) ,
这里所求的是C(2n-k+1,k)－C(2n-4-(k-2)+1,k-2)= C(2n-k,k)×2n(2n-k)


抽屉原理
鸽巢原理是组合数学中最简单也是最基本的原理，也叫 抽屉原理。即若有n个
鸽子巢，n+1 个鸽子，则至少有一个巢内有至少有两个鸽子。
367人中至少有2人的生日相同。
10双手套中任取11只，其中至少有两只是完整配对的。
参加一会议的人中至少有2人认识的别的参加者的人数相等。
例：从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数， 其
中一个是另一个的倍数。
证：设n+1个数是 ,,…, 。每个数去掉一切2的因子， 直至剩下一个奇数
为止。组成序列 , ,…,。这n+1个数仍在[1,2n]中，且都是奇数。而[1,2n]
中只有n个奇数。故必有 = = r，则
倍数。
，若＞，则 是 的

例：设 ,,…,是正整数序列，则至少存在k和 l , 1≤k≤l≤m， 使得和 +
+ … + 是m的倍数。证：设，≡ mod m，0≤≤m-1，h = 1,2 ,…, m 。
若存在l，≡0 modm则命题成立。否则，1≤≤m-1。但h = 1,2,…,m。由鸽巢原
理，故存在 = ，
即≡ ，不妨设 h＞k。则
－＝＋ +… + ≡ 0 mod m
例：设 ，， 为任意3个整数， 为 ，， 的任一排列， 则 －，
－，－中至少有一个是偶数。
证：由鸽巢原理，，， 必有两个同奇偶．设这3个数被2除的余数为 xxy，
于是，， 中被2除的余数有2个x，一个y。这样 －，－，－ 被
２除的余数必有一个为0。
例：设 ，，… 是由 1和２组成的序列，已知从其任一数开始的顺序10
个数的和不超过16．即 + +… + +9 ≤16，1≤i≤91，则至少存在 h 和 k ，
k > h，使得 + +… + = 39。
证： 令 ，j =1，2，…，100。显然<<…<，且 =( + … +)+(
+ … +)+…+( + … +) 根据假定有≤10×16=160，作序列，，… ，，
+39，… ， +39。共200项．其中最大项 +39≤160+39由鸽巢原理，必
有两项相等． 而且必是前段中某项与后段中某项相等．设= + 39，k＞h，
－ =39 ，即 + +… + = 39。

错排问题就是 n个元素依次给以标号1，2，…，n。N个元素的全排列中，求
每个元素都不在自己原来位置上的排列 数。设Ai为数i在第i位上的全体排列，
i＝1,2,...,n．因数字i不动，故：||＝(n－ 1)!，i＝1,2,...,n。
同理|∩|＝(n－2)!，i,j＝1,2,...n，i≠j。……。
每个元素都不在原来位置上的排列数为：


＝
＋
－……±





例1：数1，2，…，9的全排列中，求偶数在原来位置上，其余都不在原来位置
的错排数目。
解:实际上是1,3,5,7,9五个数的错排问题，总数为：
5!－C(5,1)4!+C(5,2)3!－C(5,3)2!+C(5,4)1!－C(5,5)＝44。
例2：在8个字母A,B,C,D,E,F,G,H的全排列中，求使A,C,E,G四个字母不在原< br>来位置上的错排数目

解:8个字母的全排列中令,,,分别为表A,C,E,G 在原来位置上的排列，则：
|∩∩∩|＝8!－C(4,1)7!+C(4,2)6!－C(4, 3)5!+C(4,4)4!＝40320－
20160+4320－480+24＝24024． < br>例3：求8个字母A,B,C,D,E,F,G,H的全排列中只有4个元素不在原来位置上的
排 列数。
解:8个字母中只有4个不在原来的位置上，其余4个字母保持不动，相当于4
个元素的错排， 其数目为：4!(1－11!+12!－13!+14!)＝9。
故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)×9＝
630。

有限制的错排
例：4个x，3个y，2个z的全排列中，求不出现xxxx、yyy、zz图象的排列数
解:出现xxxx图象的排列记为
出现yyy图象的排列记为
出现zz图象的排列记为
xxxx作为一个单元出现进行排列，考虑到y重复3次,z重复2次，故
||＝6!(3!2!)=60，
||＝7!(4!2!)=105，
||＝8!(4!3!)＝280，
|∩|＝4!2!=12,
|∩|＝5!3!=20,
|∩|＝6!4!=30,
|∩∩|＝3!=6,
4个x，3个y，2个z的全排列中不同的排列数为9(4!3!2!)＝1260。所以
|∩∩|
＝1260－||－||－||+|∩|+|∩|+|∩|-|∩∩|
＝1260－(60+105+280)+(12+20+30)－6 = 871。

例1某校有12个教师，已知教数学的有8位，教物理的有8位，教化学的5位；
数、理5位， 数、化4位，理、化3位；数理化3位。问教其他课的有几位？只
教一门的有几位？只好教两门的有几位
解:令教数学的教师属于，教物理的属于，教化学的属于。则
＝12，
＝||＋||＋||＝8+6+5＝19；
＝|∩|+ |∩|+|∩|＝12；
＝|∩∩|＝3；
故教其他课的老师数为：
＝ － +－＝2
恰好一门的教师数：
＝－2 + 3＝4
恰好教两门的老师数为：
＝－3＝3

例2：n 对夫妻围坐问题
设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种
可能的方案？
解:不妨设 n 个女人先围成一圈，方案数为( n－1 )! 。对任一这样的给定方案，
顺时针给每个女人以编号1,2,…,n。设第i号与第 i + 1号女人之间的位置为第 i
号位置，1≤i≤n－1。第 n 号女人与第1 号之间的位置为第 n 号位置。设第 i 号
女人的丈夫的编号也为第 i 号， 1≤i≤ n。让 n 个男人坐到上述编号的 n 个位
置上。设 是坐在第 i号位置上的男人，则 ≠ i ，i + 1，1≤i≤n－1；≠n，1。
这样的限制也即要求在下面3行n列的排列中
1 2 3 … … n-1 n
2 3 4 … … n 1
… …
每列中都无相同元素。满足这样的限制的排列 ··· 称为二重错排。
设二重错排的个数为，原问题所求的方案数就是( n－1)！。
设 为 = i 或 i + 1 (1≤i≤n－1 )，an = n或1的排列 ··· 的集合。
则||= 2 (n－1)!，关键是计算

也就是从( 1 , 2 ) ( 2 , 3 ) …( n－1, n ) ( n , 1)这n对数的k 对中各取一数，且互
不相同的取法的计数。这相当于从1 , 2 , 2 , 3 ,3 ,4,…,n－1, n－1, n , n , 1中取 k
个互不相邻数的组合的计数，但首尾的 1 不能同时取。回想无重复不相邻组合
的计数：
C'(n,r) = C(n－r + 1,r) ,
这里所求的是C(2n-k+1,k)－C(2n-4-(k-2)+1,k-2)= C(2n-k,k)×2n(2n-k)

１．４ 计算机系统结构的发展
1.4.1 冯·诺依曼结构

冯·诺依曼等人于1946年提出了一个完整的 现代计算机雏型，它由运算器、
控制器、存储器和输入输出设备组成，如图1.7所示。
现代的计算机系统结构与冯·诺依曼等人当时提出的计算机系统结构相比虽
已发生了重大变化，但就其结 构原理来说占有主流地位的仍是以存储程序原理为
基础的冯·诺依曼型计算机。存储程序原理的基本点是 指令驱动，即程序由指令
组成，并和数据一起存放在计算机存储器中，机器一经启动，就能按照程序指定
的逻辑顺序把指令从存储器中读出来逐条执行，自动完成由程序所描述的处理工
作。冯·诺依曼 计算机的特征可概括为：
1．存储器是字长固定的、顺序线性编址的一维结构。
2．存储器提供可按地址访问的一级地址空间，每个地址是唯一定义的。

3．由指令形式的低级机器语言驱动。
4．指令的执行是顺序的，即一般按照指令在存储器中存放的顺序执行，程
序分支由转移指令实现。
5．机器以运算器为中心，输入-输出设备与存储器之间的数据传送都途经运
算器。运算器 、存储器、输入输出设备的操作以及它们之间的联系都由控制器
集中控制。

虽 然至今绝大多数计算机仍基于上述结构特点，但这四十多年来计算机系统
结构有了许多改进。主要包括以 下几个方面：
1．计算机系统结构从基于串行算法改变为适应并行算法，从而出现了向量
计算机，并行计算机、多处理机等。
2．高级语言与机器语言的语义距离缩小，从而出现了面向高级语言机器和
直接执行高级语言机器。
3．硬件子系统与操作系统和数据库管理系统软件相适应，从而出现了面向
操作系统机器和 数据库计算机等。
4．计算机系统结构从传统的指令驱动型改变为数据驱动型和需求驱动型，从而出现了数据流机器和归约机。
5．为了适应特定应用环境而出现了各种专用计算机，如快速傅里叶变换机
器、过程控制计算机等。
6．为了获得高可靠性而研制容错计算机。
7．计算机系统功能分散化、专业化，从 而出现了各种功能分布计算机，这
类计算机包含外围处理机、通信处理机等。
8．出现了与大规模、超大规模集成电路相适应的计算机系统结构。
9．出现了处理非数值化信息 的智能计算机。例如自然语言、声音、图形和
图象处理等。主要的处理方法已不是依靠精确的算法进行数 值计算而是依靠有关
的知识进行逻辑推理，特别是利用经验性知识对不完全确定的事实进行非精确性推理。