组合数学算法(一)

i 1 j1
k
k
ij

(i - 1)k
i 1 j1
k
k
j
[0 k 2k (k 1)k] (1 2 k) k 2 (k 1)
2
2. 圆排列
从集合S={a1 ，„，an}的n个不同元素中取出r个元素，按某种次序 （如逆时针方向），排成一个圆圈，称这样的排列为圆排列。 A D 这里相同的顺序被视同一排列。如： P C B D = A 这种圆排列的个数=
（三）排列 1. 线排列 2. 圆排列 3. 重排列 1.线排列（排列） 排列的字面意思是列队。“最基本”例子就是：“要从n个不同的物体 中选出k件（1≤k≤n）来排成一列，共有多少种不同的排法？”高中数学 课本中就以此为排列的定义基础。 称“从n个不同元素中，任取k（k ≤ n）个元素按照一定的顺序排成一列， 叫做从n个不同元素中取出k个元素的一个排列。”（即线排列）
一、引言
中国是最早研究排列组合的国家。《周易》就被认为是世界上最早讨论 排列组合的书，其中的《八卦》和《六十四卦》阵，就属于重复排列问题。 我国的《洛书》有“幻方”的最早记载，幻方是组合数学中构造问题之例， 据说“河图”就是一种幻方。 历史走着曲折的道路。一些历史悠久的学科，在经历了漫长的不被人们 重视的岁月之后，又会重新焕发出青春的活力。组合数学的历史就是如此。 它同算术、代数、几何一样古老，源远流长，但却没有它们那种持续不断的 发展历程。这不能归咎于它的衰老，而只能解释成历史的青睐尚未到来。历 史是公正的，人类创造的每一项伟绩都不至于被遗忘。近几十年来，这门古 老的学科年轻了，活跃起来了，开始以前所未有的速度向前发展着，不断取 得丰富的成果。促使这种变化出现的最主要动力是二十世纪的计算机科学的 迅速发展。计算机科学，数字通讯理论，规划论和试验设计都要求人们把注 意力转向研究离散变量的数学学科，其中之一便是组合数学。这种来自尖端 学科领域的刺激的出现，激起了这门古老学科领域中从未有过的发展势头， 使它一反长期沉睡的状态，成为本世纪最活跃的数学学科之一。
r n
r
C
B
如果r=n，则
Pn n
n

n! n
(n 1)!
例：4对兄弟站成一圈，要求每对兄弟相邻，有多少种不同站法？ P 解：先让哥哥站一圈，有 4 =3！=6（种）不同排法。然后，让4位弟弟插 入其中，每人均可在其兄左边亦可右边，故均有2种方式。所以共有6x2 =96（种） *例：用4种不同颜色给小正方形木块的4条边着色，每边各涂一种颜色，能 有多少种不同的着色花样？ 解：此处不仅只考虑4种颜色的相对顺序，而且木块可以翻边，因此没有逆 时针顺序与顺时针顺序的不同区分。故一共有 P 1 =3 种。
加法原理 用途极多，如将其与其他数学原理，例如抽屉原理结合起来， 就可以推出许多有趣的数学命题。
（二）乘法原理
如果完成一件事情要分几个步骤B1 ，B2 ，„ n n ，而每个步骤Bi有 ，B mi种方法(1≤i≤n) ，那么完成这事共有 N mi
i 1
例2 某人在进小学、初中、高中时都分别有二所学校可选择，那么他就 有多种不同的方式从小学到高中。 共8种=2 x 2 x 2 例3 多项式乘积 (a1+a2+a3) (b1+b2+b3+b4) (c1+c2+c3+c4+c5+c6) (d1+d2) 的展开式中有多少不同的项。 解：展式中每项均形如aibjckdl，其中i є {1,2,3} ，j є {1,2,3,4} ， k є {1,2,3,4,5,6} ， l є {1,2} 由乘法原理，展式中共有 3 x 4 x 6 x 2 =144 （项） 例4 在ΔABC的三边上分别取n1，n2，n3个点（不含A,B,C），在三边上 的点中各取一个作为三角形的顶点，可以得到多少个不同的三角形？ n1 n2 n3
现代组合学中对排列下了一个更为妥当的定义：从n个不同元素中有 次序地选取k（1≤k≤n）个，叫做从n个不同元素中取出k个元素的一个排 列。又当k=n时，就叫做一个全排列。 n 有 Pn n ! 人们又规定 0！=1 容易的大家都知道了计算。 例 把自然数1，2，„，k2排成一个方阵表。从表中任意取一个数，然后 删去这个数所在的行和列中的全部数字，再从剩下的(k-1)2 个数组成的 方阵表中任意取出一个数，并删去这个数所在的行和列中的所有数字。 这样一直进行下去，一共可取表中k个不同的数字，它们构成了集合{1， 2，„ ，k2}的一个k阶子集。问题是：用这样的方法，共可取得{1， 2，„ ，k2}中多少个不同的由k个数字组成的子集？这些子集中的k个数 字之和各是多少？ 1 2 „ k k+1 k+2 „ 2k „ „ „ (k-1)k+1 (k-1)k+2 „ k2
加法原理的例子补充 |A|，|B|分别为集合A，B中元素的个数 补例1 现有长度分别为1，2，∙∙∙，n的细木棍各一根，可以以它们为边构 成多少个不同的三角形？ 解：记三角形三边长度为a，b，c，不妨设a<b<c，则应有a+b>c 。以c 的长度将这些三角形分类，则可分为c=4，c=5， ∙∙∙，c=n 这样一些不 同的类，分别将各类三角形的集合记作B4，B5，∙∙∙，Bn，则它们构成 n 了所有三角形的集合B的一个分划，则有 B B
4
当k 为奇数时，有 所以n为偶数时，B

B k 2 4 (k 3)
1 4
1 4
(k 1)(k 3)
(5 2)
2 22来自nBk 2
1 4
2
(4 2)
2

1 4

1 4
(n 2)
2
k4
(2
3 4
(n 2) )

k
k4
而在Bk 中，三角形三边分别为a<b<k ，其中k为定值。于是可将(a,b) 对应为平面中的格点，如图。由于还有a+b>k ，所以这些点由a=b， a+b=k，b=k三条直线所围成的三角形区域内部。所以当k 为偶数时， 有 B k 1 3 (k 3) 1 (k 2) 2
1 24
n(n 2)(2n 5)
n为奇数时，
B

n
Bk
1 24
(n 1)(n 3)(2n
1)
k4
补例2 设[x]表示不超过实数x的最大整数。求方程x2 - [x2] = (x - [x] )2在区间 1≤x≤n中根的个数。 解：显然x=n是方程的一个根。下面我们再分别求出方程在区间1≤x<2， 2≤x<3，„，n-1≤x<n中的根的个数。为此设这些区间中根的个数为B1 ， B2，„，Bn-1， 即以Bk表示方程在区间k≤x<k+1中根的全体。 ∵在k≤x<k+1中，有[x]=k ，如果再记p= x-[x] ，就有0≤p<1。于是原来 方程就可以写成 (k+p)2 -[(k+p)2]=p2 即k2 +2kp=[k2 +2kp+p2] 注意到 [k2 +2kp+p2]=k2 +[2kp+p2] 知上式即为 2kp=[2kp+p2] 该式右端是一个整数，所以左端也应为整数，即2kp是整数 由于k为整数，0≤p<1，所以只有当p=0 ，1/2k ，2/2k ，„，(2k-1)/2k 时，等式才能成立。从而知原方程在此区间中恰有2k个根，即| Bk |=2k 于是由加法原理知原方程在区间1≤x≤n中共有 | B1 |+ | B2 |+ „ +| Bn-1 |+1=2+4+ „ +2(n-1)+1=n 2 -n+1 个根
由于Sk的最小性，知
S 1 a i k 1 S k 1 S k 0 S 2 a i k 1 a i k 2 S k 2 S k 0 S n - k a i k 1 a i k 2 a i n S n S k 0 S n -1 S n a i k S n (S k S k 1 ) S n S k S k 1 S k 1 S k 0 Sn 0 a1 a n
4 4
4 4
4
2
*例：在右图的圆周上均匀地布列着n个方框。 今有n个非零实数a1，a2，„，an 满足a1+a2+„+an=0，要将它们分别填入 圆周上的n个方框。证明：至少有(n-1)！种 填法可以使得自某个方框A开始按逆时针方向， ai2 A ai1 逐个累加方框中的数字，得出的每一步和数都非负。 证：设已将n个数字填入方框，并且自A开始按逆时针依次填入 ai1，ai2，„，ain 。现来逐个累加它们得到 S1=ai1，S2=ai1+ai2 ，„，Sn=ai1+ai2+„+ain。 如果这些S1，„，Sn≥0，则相应的填法合乎要求。 如果S1，„，Sn中有负数，则只要将所填数字集体顺时针旋转若干位置， 即可得合乎要求的填法。 现证之。设Sk=min(S1，„，Sn) ，Sk<0
*例5 每个完全平方数都有奇数个正约数 证：设n=m2是一个完全平方数 而m的素因数分解式为 r r r p 11 p 22 ...p kk m= ，那么 2r n= p 1 1 p 2r 2 ...p 2r k 2 k 记A1={0，1，„，2r1}，A2={0，1，„，2r2}，„，Ak={0，1，„，2rk} j j j 那么n的每一个正约数就都具有形式 p 11 p 22 ...p kk 其中j1 є A1 ， „ ，jk є Ak ，故由乘法原理n一共有 | A1|∙ | A2| „ | Ak| = (2r1+1) (2r2+1) „ (2rk+1)个正约数 共有奇数个。 例6 （结合程度较高的例子） 一种单向行驶的汽车，满载为25人，全程共设14个车站，中途的每一 个车站均可上下乘客。由不同起点到达不同终点的乘客各应购买不同的 车票。在一次单程行驶中，车上最多可卖出多少种不同的车票？ 解：车上应准备由每个车站到达它后面每一个车站的车票，所以一共应准 备 13+12+ ∙∙∙ +2+1=91（种） （加法原理之应用）