第2章-组合数学初步

1、第2章 组合数学初步,引言 2.1 计数基本原理 2.2 鸽笼原理 2.3 排列与组合 *2.4 递推关系,组合数学是一个古老而又年轻的数学分支.它的渊源可以追溯到公元前2200年的大禹治水时代; 但它的蓬勃发展却是在计算机问世和普遍应用之后.,组合数学涉及面非常广, 内容庞杂, 并且仍在很快地发展着, 因此目前还没有一个统一而有效的理论体系.,引言,引例 幻方问题(最古老、最流行的游戏),将 1, 2, 3, , n2 个数排成nn方阵, 使得每行, 每列, 以及每条对角线上元素的和相等, 是否存在解?,n=4时:,n=3时:,对任意的n, 解是否存在（存在性问题）? 如果存在, 有多少种不

2、同的解（计数问题）？解应如何构造（枚举问题）？,2.1 计数基本原理,2.1.1 加法原理和乘法原理 2.1.2 包含排斥原理,加法原理: 如果完成一件事情有两个方案, 第一种方案有m种方法, 第二种方案有n种方法, 只要选择任何方案中的任一种方法, 就可以完成这件事情, 且这些方法两两互不相同, 则完成这件事情共有m+n种方法.,2.1.1 加法原理和乘法原理,加法原理的集合论语言:,设有限集合A有m个元素, B有n个元素, 且A与B不相交, 则A与B的并共有m+n个元素.,定理2.1 设A, B为有限集,定理2.2 设n个有限集合,满足,则,例 某班有18个男生, 12个女生, 从中选出一

3、 名代表参加会议, 问共有多少种选法?,解: 设集合A: 男生, B: 女生.,根据加法原理知, 有30种选法.,任选的一个学生要么属于A, 要么属于B.,且,18+12=30,共有 个满足要求的六位二进制数.,例 在所有六位二进制数中, 至少有连续4位 是1的有多少个?,解: 把所有满足要求的二进制数分成如下3类:,111100, 111101, 011110, 001111, 101111.,B: 恰有5位连续的1. 则,B=, 011111, 111110 .,C: 恰有6位连续的1. 则,C=, 111111 .,由加法原理知:,5+2+1=8,乘法原理: 如果完成一件事情需要两个步骤

4、, 第一步有m种方法, 第二步有n种方法, 则完成该件事情共有 种方法.,定理2.3 设A, B为有限集,则,定理2.4 给定n个有限集合,则,乘法原理的集合论语言:,设有限集合A有m个元素, B有n个元素. 则,那么,共有,个元素.,例 从5位先生, 6位女士, 2位男孩和4位女孩 中选取1位先生, 1位女士, 1位男孩和1位 女孩, 共有 种方式.,从中选取一个人共有 种方式.,5+6+2+4=17,例 某班有18个男生, 12个女生, 从中分别选出 男女生各一名代表全班参加比赛, 问共有 多少种选法?,解: 设集合A: 男生, B: 女生.,因,故共有216种选法.,包含排斥原理(容斥原

5、理)是研究有限集合的交或并的计数.,解: 2的倍数是 2, 4, 6, 8, 10, 12, 14, 16, 18, 20.,引例. 求1,20中2或3的倍数的个数.,10个,中重复计数了, 应减去.,3的倍数是 3, 6, 9, 12, 15, 18.,6个,但答案不是10+6=16个, 因为,6, 12, 18在两集合,故答案是: 16-3=13.,注意: 加法原理是在,时, 才成立,当,时, 应将,中的元素个数减去.,2.1.2 包含排斥原理,定理2.5 设A, B为有限集, 则,的另外的形式:,图形说明:,定理2.5的推广:,当集合A, B是有限集U的子集时, 另一种形式为:,图形说明

6、:,更一般地有,定理2.6 给定n个有限集合,则,当n个集合 是有限集U的子集时,定理的另一种形式为:,例 一学校只有3门课程: 数学, 物理, 化学. 已知修这3门课的学生分别有170, 130, 120人; 同时修数学, 物理两门课的学生有45人; 同时修数学, 化学的有20人; 同时修物理, 化学的有22人; 同时修三门课的学生有3人. 假设学校的学生至少修一门课程, 问这个学校共有多少学生?,解: 设A为修数学的学生集合; B为修物理课的学生集合; C为修化学课的学生集合. 则所求为:,由容斥原理知,因为,例 求从1到1000不能被5, 6和8整除的整数个数.,解: 先引入几个符号.,

7、设x为实数, 则,表示不超过x的最大整数;,两个整数a, b的最小公倍数记为: lcm(a, b);,三个整数a, b, c的最小公倍数记为: lcm(a, b, c);,令: U是前1000个正整数组成的集合;,是前1000个正整数中能被5整除的整数集合;,是前1000个正整数中能被6整除的整数集合;,是前1000个正整数中能被8整除的整数集合;,于是所求为:,又,这些整数能被,lcm(5, 6)整除.,因为lcm(5, 6)=,30,lcm(5, 8)=,40,lcm(6, 8)=,24.,于是,又因为lcm(5, 6, 8)=,120,所以,从1到1000不能被5, 6和8整除的整数个数

8、为,由容斥原理知,2.2 鸽笼原理,2.2.1 鸽笼原理 2.2.2 鸽笼原理的加强形式,鸽笼原理是组合数学中最简单也是最基本的原理, 也叫抽屉原理.,“若有n个鸽笼, n+1个鸽子, 则至少有一个鸽笼内有两个或更多的鸽子.”,再如: 10双手套中任取11只, 其中至少有两只是完整配对的.,例如: 367人中至少有人的生日相同.,定理2.7 如果把n+1个物品放在n个盒子中, 那么至少有一个盒子中有两个或更多的物品.,证明: 倘若每个盒子中至多有1个物品, 那么n个 盒子中至多有 个物品.而我们共有n+1个物品, 矛盾！ 故定理成立.,n,注意: 鸽笼原理只断言存在一个盒子, 该盒子中有两个或

9、两个以上的物品, 但它并没有指出是哪个盒子, 要想知道是哪一个盒子, 则只能逐个检查这些盒子. 所以, 这个原理只能用来证明某种安排的存在性, 而对找出这种安排却毫无帮助.,2.2.1 鸽笼原理,例2.7 从1到200的所有整数中任取101个，则这101个整数中至少有一对数, 其中的一个一定能被另一个整除.,证明: 设,是任取出的101个整数,对任一,都可以唯一地写成如下的形式:,其中,为非负整数，,为奇数.,由于,所以,取1, 3, 5, , 199这100个奇数,只能,由鸽笼原理知, 存在,使得,不妨设,进而,所以,整数.,定理2.8 (加强形式1)设q1, q2, , qt是正整数, 把

10、,2.2.2 鸽笼原理的加强形式,件物品放入 t 个盒子里, 则存在某个i(1it)使第i个盒子里至少装qi件物品.,证明: 倘若对所有的i(1it), 均有第i个盒子至多装有qi-1件物品, 从而这t个盒子装有的物件总数至多为,矛盾, 所以定理成立.,定理2.8 （加强形式2） 如果把t(r-1)+1件物品装入t个盒子中, 则至少有一个盒子至少有r件物品.,定理2.8 (加强形式3) 如果t个整数q1, q2, ,qt的算术平均值大于r-1, 则qi(1it)中至少有一个不能小于r.,证明: 假若对所有的qi, 都有qir-1(1it), 则,矛盾.,当q1=q2= =qt=r时, 上述原理

11、可叙述为:,把mn+1个物品放入m个盒子，至少一个盒子至少有n+1个物品。,若n个整数的和大于nm，则至少有一个整数大于m.,例 证明每个长为n2+1的实数序列, ,都含有一个长为n+1的递增子序列或,长为n+1的递减子序列.,设,证明概要: 假设不存在长为n+1的递增子序列. 下面我们证明一定存在长为n+1的递减子序列.,设qk是以ak为首元素的最长递增子序列的长度,1qkn.,n2+1个数qk中至少有n+1个数相等.,此时必有,(否则, 会得出矛盾).,故,从而,是一个长为n+1的递减子序列.,注意：尽管鸽笼原理很简单, 但它却能解决一些看似很复杂的组合问题. 在将其运用到具体的问题时,

12、需要一定的技巧去构造具体问题中的“鸽子”与“笼子”。,2.3 排列与组合,2.3.1 基本的排列与组合 2.3.2 多重集合的排列与组合 2.3.3 二项式系数,2.3.1 基本的排列与组合,2.3.1.1 集合的排列 线排列 圆排列 2.3.1.2 集合的组合,2.3.1.1 集合的排列,定义: n元集合S的一个 r 排列是指先从S中选出r个元素, 然后将其按次序排列, 用P(n, r)或 表示n元集合的r排列数.,定理2.9 对于满足,的正整数n和r, 有,证明: 要构造n元集合的一个r排列, 可以在n个元素中任取一个作为第一项, 有 种取法;,第r项有 种取法.,n,第一项后, 第二项可

13、以从剩下的n-1个元素中任选一个, 有 中取法;,n-1,;,由乘法原理知结论成立.,n-r+1,在取定,在前r-1项取定后, 全排列数P(n, n)=,显然有:, P(n, r)= (当rn时);, P(n, 1)= (当n1时);,0,n,n!,规定：0!=1.,例 15迷宫游戏: 将标有数字1到15的15个可以滑 动的小正方形装在一个44的正方形框架上, 剩 下一个小的空方块. 游戏是将15个小方块从任一 排列方式移动成下图所示的初始位置. 问: 这15个 小方块在44的框架上有多少种不同的排列方式?,所以有P(16, 16)=16!种不同的排列方式.,解: 原问题就是求将1, 2, ,

14、15 放在44框架中的16个小方 块上而剩下一个空方块的方 式数.,将空方块看作16, 则原问题就变为1, 2, , 16放入16个小方块中的方式数,它等于1, 2, , 16的,全排列数.,例 A单位有7位代表, B单位有3位代表, 排成 一行合影, 要求B单位3人排在一起. 问有多少 种不同的排列方案?,8!3!,解: 先令B单位3 个人的某一排列作为一个元素 参加A单位进行排列, 可得方案数为 ,(7+1)!=8!,又B单位的3人有 种排列,3!,由乘法原理, 总的,方案数为 .,解: A单位7人共有 种排列.,7!,设A1 A2 A3 A4 A5 A6 A7是A的一个排列,定后, B单

15、位3人中的第1人有 种选择,两端固,6,见下图:,例 A单位有7位代表, B单位有3位代表, 排成一行合影, 要求B单位3人不能相邻，而且A单位的两人排在两端. 问有多少种不同的排列方案?,A1*A2*A3*A4*A5*A6*A7,其中*的位置是第1人可选的位置.,第2位为了不与第1位相邻, 故只有 种选择.,5,第3位有 种选择.,4,故排列总数为 .,7!654,显然, 同一个圆排列（循环排列）,对应7个不同的线性排列:,A1 A2 A3 A4 A5 A6 A7,A2 A3 A4 A5 A6 A7 A1,A3 A4 A5 A6 A7 A1 A2,A4 A5 A6 A7 A1 A2 A3,A

16、5 A6 A7 A1 A2 A3 A4,A6 A7 A1 A2 A3 A4 A5,A7 A1 A2 A3 A4 A5 A6,说明: 对于相同的问题，圆排列的数目比线排列的的数目少.,前面所学的r排列都是在直线上进行的, 所以也叫线性r排列. 若在圆周上进行排列, 结果又如何呢?,定理2.10 n元集合的圆r排列数为,特别地, n个元素的圆n排列(r=n时)个数是(n-1)!.,例 10个男生和5个女生聚餐, 围坐在圆桌旁, 任意两个女生不相邻的坐法有多少种？,解: 先将10个男生进行圆排列, 共有 种排法.,9!,对男生的任一种排法,生之间, 每两个男生之间只能插一个女生,把5个女生插在10个

17、男,女生在10个位置中任选,5个位置的排列数为,P(10, 5),由乘法原则知,共有,种坐法.,9!P(10, 5),.,2.3.1.2 集合的组合,定义: n元集合S的r组合是指从S中取出r个元素的一种无序选择, 其组合数记为C(n, r),或,或,定理2.11 若0rn, 则,显然有:,证明: 设S是一n元集合, 任取S的一个r组合, 将该 r组合中的r个元素进行排列,可得到 个,P(r, r)=r!,S中的r排列.,且S中的任一r排列都恰好可通过,将S中的某一r组合排序而得到.,所以, 有,例 学院欲将6名保送研究生推荐给3个单位, 每个单位2名, 问有多少种方案?,解: 推荐给某个单位

18、的两名学生的顺序是无关紧 要的, 这是一个组合问题.,先从6名学生中选出2名给第1个单位, 有 种,选法.,然后从余下的4名学生中选出2名给第2个,单位, 有 种选法.,最后2名学生给第三个单位.,由乘法原理:,所以共有90种方案.,2.3.2 多重集合的排列与组合,2.3.2.1 多重集合的排列 2.3.2.2 多重集合的组合,2.3.2.1 多重集合的排列,n元集合的r排列是指从n个不同的元素里, 每次取出r个互不相同的元素进行排列. 然而在现实生活中, 并不一定是对不同的元素进行排列. 例如, 对一组数据排序就是求它的一个排列, 而这些数据中可能有相同的数.,多重集合: 集合中可以有相同

19、的元素.,例如: M=a, a, a, b, c, c, d, d, d, d是一个10个 元素的多重集合.,通常, 可将M表示为M=3a, 1b, 2c, 4d.,一般多重集合可记为M= k1a1, k2a2, , knan.,一般多重集合可记为M= k1a1, k2a2, , knan.,其中,a1, a2, , an,为M中所有互不相同的元素;,ki是正整数, 称ki为ai的重数, 表示M中有ki个ai (1in), ki也可以是,表示M中有无限多个ai.,多重集合S的排列同一般集合的r排列一样, 也是从S中选出r个元素的有序选择.,定理2.12 多重集合M=, a1, a2, ,ak,

20、的r排列数为,kr.,证明: 在构造M的一个r排列时, 第一项有 种选,择,k,第二项有 种选择,k, , 第r项有 种,选择.,k,所以r排列中的任一项都有k 种选择, 且不依赖于前面已选择的项.,由于M中的每个元素都是无限重的，,故M的r排列数为kr.,由上面的证明易知, 若M中每个元素的重数至少为r, 则定理的结论仍然成立.,定理2.13 多重集合M= k1a1, k2a2, , knan,的全排列数为,证明: 因为集合M中共有 个元素,k1+k2+kn,a1占集合M的全排列中的k1个位置, 选取a1所占位,的位置后, 还有 个位置,k2+k3+kn,位置的方法数为,在确定了k1个a1,

21、从中选取k2,个a2的位置的方法数为,依次选取位置安排a3, a4, ,an,类似的,由乘法原理知, M,的全排列数为,例 求不多于四位的二进制数的个数.,解: 此问题是多重集合,的4排列问题.,由定理2.12知, 所求的二进制数个数为,2412.,例 设S=3a, 2b, 4c, 求S的8排列的个数.,解: S的8排列可分为以下三类:, 2a, 2b, 4c的8排列(全排列), 数目为, 3a, 1b, 4c的8排列(全排列), 数目为, 3a, 2b, 3c的8排列(全排列), 数目为,因此S的全部8排列的个数为,420+280+5601260.,2.3.2.2 多重集合的组合,多重集合M

22、的r组合是指从M中无序的选r个元素.,定理2.14 多重集合M= , a1, a2, ,ak,的r组合数为,证明: 设多重集合M的某个r组合为, x1a1, x2a2, , xkak,x1+x2+xk=r，,则有,其中,x1, x2, , xk,为非负整数;,反之, 若给出上述,方程的一组非负整数解:,x1, x2, , xk ,则它们也,对应M的一个r组合.,所以M的r组合与上述方程,的非负整数解一一对应,题化为求上述方程非负整数解的问题.,从而将求M的r组合问,x1+x2+xk=r 的一个非负整数解可以表示,方程,成一个长为k-1+r的0, 1序列:,其中0的个数为k-1.,该0, 1序列

23、是集合,(k-1)0, r1,的一个全排列.,方程的解与集合(k-1)0, r1,的全,排列之间是一一对应的,从而得多重集合M的r组,合数为,例 方程,x1+x2+x3+x4=20 的整数解的个数是,多少? 其中x13, x21, x30, x45.,解: 引入新变量 y1=x1-3, y2=x2-1, y3=x3, y4=x4-5,则原方程变为 y1+y2+y3+y4=11, 且诸yi是非负的.,因新方程非负整数解的个数是,故原方程整数解的个数是364.,定理2.14的推广: 重数为n1, n2, , nk的多重集合 S=n1a1, n2a2, , nkak的r-组合数和方程 x1+x2+x

24、k=r的整数解的个数相同, 其中 0 x1n1, 0 x2n2, , 0 xknk .,2.3.3 二项式系数,2.3.3.1 二项式定理 2.3.3.2 二项式系数的基本性质 2.3.3.3 组合恒等式,定理2.15（二项式定理）设n为一正整数, 则对任意的x和y, 有,2.3.3.1 二项式定理,证明: 将,完全展开,然后再合并同类项.,因为在展开时, 每个因子均可选择x或者y，,故结果共有2n项,根据乘法原理).,(每个因子两种选择, 共n个因子,且每一项都可写成xryn-r的形式,(r=0, 1, , n),在n个(x+y)因子中选出r个, 从这r,个因子中选择x, 而在剩下的n-r个因子中选择y,即 xryn-r的系数等于,证毕.,推论 设n为一正整数, 则对任意的x, 有,证明: 在二项式定理中令y=1即可得此结论.,表达式,式系数, 它有许多奇妙的性质, 也有很多重要的应用，特别是，他经常用于计算机算法的分析。,表示n元集合的r组合数, 也叫二项,设n, r均为非负整数, 且nr, 则,(1) 对称关系,(2) 递推关系,(nr1).,(3) 单峰性,当n为偶数时, 有,当n为奇数时, 有,2.3.3.2 二项式系数的基本性质,性质(1)对称关系,的证明.,证法1: 利用二项式系数表达式,说明: 在证明二项式系