组合学问题在生活中随处可见。
例如,计算世界杯比赛场次、计算彩票摸奖概率等。
组合数学是数学的重要分支,其快速发展的原因:
1、计算机对社会的影响越来越大,很多计算机程序的基础往往是基于组合学思想设计的算法。
2、组合数学的适用性越来越广,包括社会科学、生物科学、信息论等领域。
组合数学一般有存在性问题、计数问题、构造性算法、最优化问题四个方面。
存在性问题:工程实际或科学研究提出各种问题,有些可以判定其有解或无解,但也有不少难以判定。
计数问题:如一个组合问题的解已知是存在的,自然会问有多少不同的解。
构造性算法:一个组合问题,已判知解存在,甚至也可以推知有几组解,需要从组合论角度设计算法,使之较好地构造出解。
优化问题:一个问题的构造性算法可能不止一种,如何择优?如何改进?使问题的解在多项式时间复杂性要求下能解出来,不出指数级情况的“组合爆炸”。
排列(在乎顺序)
全排列:n个人全部来排队,队长为n。第一个位置可以选n个,第二位置可以选n-1个,以此类推得:P(n,n)=n(n-1)(n-2)……3*2*1= n! (规定0!=1).
部分排列:n个人选m个来排队(m<=n)。第一个位置可以选n个,第二位置可以选n-1个,以此类推,第m个(最后一个)可以选(n-m+1)个,得:
P(n,m)=n(n-1)(n-2)……(n-m+1)= n! / (n-m)! (规定0!=1).
组合(不在乎顺序)
n个人m(m<=n)个出来,不排队,不在乎顺序C(n,m)。如果在乎排列那么就是P(n,m),如果不在乎那么就要除掉重复,那么重复了多少?同样选出的来的m个人,他们还要“全排”得到P(n,m),所以得:
C(n,m) * m! =P(n,m)
C(n,m)= P(n,m) / m!=n! / ((n-m)! * m! )
组合数的性质1:
组合数的性质2:
练习:
排列组合解题注意:
1、正确判断是排列问题,还是组合问题,还是排列与组合的综合问题。
2、解决比较复杂的排列组合问题时,往往需要既分类又分步。正确分类,不重不漏;正确分步,连续完整。
其他排列组合
圆排列:n个人全部来围成一圈为Q(n,n),其中已经排好的一圈,从不同位置断开,又变成不同的队列。所以:Q(n,n)*n=P(n,n) >>> Q(n)=P(n,n)/n=(n-1)!
由此可知,部分圆排Q(n,r)=P(n,r)/r=n!/(r*(n-r)!)。
重复排列(有限):k种不一样的球,每种球的个数分别是a1,a2,…ak,设n=a1+a2+…+ak,这n个球的全排列数,为n!/(a1!*a2!*…*ak!)。
重复组合(无限):n种不一样的球,每种球的个数是无限的,从中选k个出来,不用排列,是组合,为C(n+k-1,k)。
不相邻排列:1~n这n个自然数中选k个,这k个数中任何两个数不相邻数的组合有C(n-k+1,k)。
第二类 stirling数(子集划分)
第二类stirling数的性质:
① S(n,m)= m*S(n-1,m) + S(n-1,m-1)
② S(n,1)=1,S(n,0)=0, S(n,n)=1
例:将n个数(1,2,…,n)分成r个部分。每个部分至少一个数。将不同划分方法的总数记为S(n,r)。例如,S(4,2)=7,这7种不同的划分方法依次为 { (1) , (234) },{ (2) , (134) },{ (3) , (124)},{ (4) , (123) },{ (12) , (34) },{ (13) ,(24) },{ (14) ,(23) }。当n=6,r=3时,S(6,3)=?
题解:先固定一个数,对于其余的5个数考虑S(5,3)与S(5,2),再分这两种情况对原固定的数进行分析。最后得到:S(6,3)=90。
错位排列(简称:错排)
例:胸口贴着编号为1,2,….n的n个球员分别住在编号为1,2,….n的n个房间里面。现规定每个人住一个房间,自己的编号不能和房间的编号一样。这就是错排问题。当n=3时,只能为312或231这两种。
错排公式:
同时也有:
错位排列数列为:0,1,2,9,44,265,......
Catalan 数列(卡特兰数)
例1:有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票, 剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?
例2:一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
Catalan数列为1, 1, 2, 5, 14, 42, 132,….。
该递推关系的解为:
每日练习
1.
(1) 用0,1,2,3,4组合多少无重复数字的四位数?
(2) 这些四位数中能被4整除的数有多少个?
(3) 这些四位数中能被3整除的数有多少个?
2.用0,1,2,3,4五个数字组成无重复数字的五位数从小到大依次排列。
(1) 第49个数是多少?
(2) 23140是第几个数?
3.求下列不同的排法种数:
(1) 6男2女排成一排,2女相邻;
(2) 6男2女排成一排,2女不能相邻;
(3) 5男3女排成一排,3女都不能相邻;
(4) 4男4女排成一排,同性者相邻;
(5) 4男4女排成一排,同性者不能相邻。
4.有四位医生、六位护士、五所学校。
(1) 若要选派三位医生到五所学校之中的三所学校举办健康教育讲座,每所学校去一位医生有多少种不同的选派方法?
(2) 在医生或护士中任选五人,派到五所学校进行健康情况调查,每校去且仅去一人,有多少种不同的选派方法?
(3) 组成三个体检小组,每组一名医生、两名护士,到五所学校中的三所学校为老师体检,有多少种不同的选派方法?
5.平面上有三条平行直线,每条直线上分别有7,5,6个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成多少个不同四边形?
6.平面上有三条平行直线,每条直线上分别有7,5,6个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成多少个不同三角形?
7.将N个红球和M个黄球排成一行。例如:N=2,M=2可得到以下6种排法:
红红黄黄 红黄红黄 红黄黄红 黄红红黄 黄红黄红 黄黄红红
问题:当N=4,M=3时有多少种不同排法?
8.用20个不同颜色的念珠穿成一条项链,能做多少个不同的项链?
9.在单词MISSISSIPPI中字母的排列数是?
10.求取自1,2,…k的长为r的非减序列的个数为?
排列与组合每日练习参考答案:
1、96,30,36;2、30124,40
3、p(7,7)*p(2,2);p(6,6)*p(7,2);p(5.5)*p(6,3);p(4,4)*p(4,4)*p(2,2);p(4,4)*p(4,4)*p(2,2)
4、c(5,3)*p(4,3);p(10,5);c(5,3)*p(4,3)*c(6,2)*c(4,2)*c(2,2)
5、2250;6、751;7、35;8、20!/20
9、11!/(1!*4!*4!*2!);10、c(r+k-1,r)
加法原理:
完成一个工程可以有n类办法,a[i](1<=i<=n) 代表第i类方法的数目。
那么完成这件事共有S = a[[1]+a[2]+…+a[n]种不同的方法。
乘法原理:
完成一个工程需要分n个步骤,a[i](1<=i<=n) 代表第i个步骤的不同方法数目。
那么完成这件事共有S = a[[1]*a[2]*…*a[n]种不同的方法。
两个原理的区别:一个与分类有关,加法原理是“分类完成”;一个与分步有关,乘法原理是“分步完成”。
每日练习
1. 由数字1,2,3,4,5可以组成多少个三位数(分别讨论各位上的数字允许重复和不允许重复的情况)?
2. 由数字0、1,2,3,4,5可以组成多少个三位数(讨论各个位上数字允许重复和不重复的情况)?
3. 由数字0,1,2,3,4,5可以组成多少个十位数字大于个位数字的两位数?
4. 一个三位密码锁,各位上数字由0,1,2,3,4,5,6,7,8,9十个数字组成,可以设置多少种三位数的密码(各位上的数字允许重复)?首位数字不为0的密码数是多少种?900首位数字是0的密码数又是多少种?
5. 如图,要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种?
6. 某班有22名女生,23名男生. 选一位学生代表班级去领奖,有几种不同选法?选出男学生与女学生各一名去参加智力竞赛,有几种不同的选法?
7. 105有多少个约数?并将这些约数写出来。
8. 从5幅不同的国画、2幅不同的油画、7幅不同的水彩画中选不同画种的两幅画布置房间有几种选法?
9. 若x、y可以取1,2,3,4,5中的任一个,则点(x ,y)的不同个数有多少?
10. 一个口袋内装有5个小球另一个口袋内装有4个小球,所有这些小球的颜色各不相同,从两个口袋内任取一个小球,有几种不同的取法? 从两个口袋内各取一个小球,有几种不同的取法。
11. 乘积(a1+a2+a3)*(b1+b2+b3+b4)*(c1+c2+c3+c4+c5)展开共有几个项?
12. 有四位考生安排在5个考场参加考试.有几种不同的安排方法。
加法原理与乘法原理每日练习参考答案:
1、重复:125,不重复:60
2、重复:180,不重复:100
3、15;4、1000,100;5、6;6、45,506;7、8;8、59;9、25;10、9,20;11、60;12、625
鸽巢原理
简单形式:如果n+1个物体被放进n个盒子,那么至少有一个盒子包含两个或更多的物体。
例1:在13个人中存在至少两个人,他们的生日在同一月份里。
例2:设有n对已婚夫妇。为保证有一对夫妇被选出,至少要从这2n个人中选出n+1个人。
加强形式:令q1,q2,…qn为正整数。如果将 q1+q2+…+qn+1个物体放入n个盒子内,那么或者第一个盒子至少含有q1+1个物体,或者第二个盒子至少含有q2+1个物体,…,或者第n个盒子含有qn+1个物体。
容斥原理
U:全班的人 |U|:全班的人数92;
S:参加比赛的人 |S|:参加比赛的人数 88
A1:参加短跑的人 |A1|:参加短跑的人数19+9+3+10=41
A2:参加投掷的人 |A2|:参加投掷的人数21+6+3+10=40
A3:参加跳远的人 |A3|:参加跳远的人数20+9+6+3=38
S=A1∪A2∪A3 ∪是并在一起,而不是加!
所以|S|=|A1∪A2∪A3|=88
而不是|S|=|A1∪A2∪A3|=|A1|+|A2|+|A3|=41+40+38=119 这是错误的!
那么|S|=88怎么算呢?
|S|=|A1∪A2∪A3|=|A1|+|A2|+|A3| -(|A1∩A2|+|A1∩A3|+|A2∩A3|)+ |A1∩A2∩A3|
例2:求从1到1000不能被5、或被6、或被8整除的整数的个数?
题解1: |S|=|A1∪A2∪A3|=|A1|+|A2|+|A3| -(|A1∩A2|+|A1∩A3|+|A2∩A3|)+ |A1∩A2∩A3|=400,所以 |U| - |S|=600
题解2:画大图,清晰明了。
算术序列 (等差序列)
2 5 8 11 ? 17 ……答案是:14
特点:相邻两个数的差是固定的常数d!(注意:d可以是负数)
通项公式:若初始项为a1:则递推关系为 an=a1+(n-1)*d;
对应的各项为:a1,a1+d,a1+2d,….,a1+(n-1)*d;
求和公式:
公式1:平均数*n结果为
,只需要知道:头,尾,n
公式2:代入公式1,可变形为 n*a1+n*(n-1)*d/2,只需要知道:头或尾、d、n
几何序列 (等比序列)
2 4 8 ? 32 64 ….. 答案是:16
特点:相邻两个数的比是固定的常数q!(注意:q可以是负数,分数,什么都有可能)
通项公式:若初始项为a1:则递推关系为:
对应的各项为:a1,a1*q,a1*q^2,….
求和公式:
公式:只需要知道:头,q,n
Fibonacci序列(斐波那契数列)
0 1 1 2 3 5 ? 13 21……答案是:11
特点:每一项是它前两项的和
通项公式:
求和公式:前n项的和Sn= f(0)+f(1)+f(2)+…+f(n)= f(n+2)-1
例1:楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法?
例2:有一对雌雄兔,每两个月就繁殖雌雄各一对兔子,问n个月后共有多少对兔子?
例3:有n*2的一个长方形方格,用一个1*2的骨牌铺满方格。求铺法总数?
分平面的最大区域数
1、直线分平面的最大区域数的序列为:
2, 4, 7, 11,….
递推公式是:fn=f(n-1)+n=n(n+1)/2+1
2、折线分平面的最大区域数的序列为:
2, 7, 16, 29, …,
递推公式是:fn=(n-1)(2n-1)+2n
3、封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为:
2, 4, 8, 14,…
递推公式是:fn=f(n-1)+2(n-1)=n^2-n+2
每日练习
1、平面上有三条平行直线,每条直线上分别有7,5,6个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成多少个不同三角形?
2、平面上有三条平行直线,每条直线上分别有7,5,6个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成多少个不同四边形?
3、由3个a,1个b和2个c构成的所有字符串中,包含子串“abc”的共有()个。
A. 20 B. 8 C. 16 D. 12 E. 24
4、由3个a,5个b和2个c构成的所有字符串中,包含子串“abc”的共有()个。
A. 40320 B. 39600 C. 840 D. 780 E. 60
5、已知8个元素为(26、75、15、23、14、62、72、19),按照依次插入结点的方法生成一颗二叉排序树,则该树的深度为( )?
6、编号为1到13的纸牌顺时针排成一圈,有人从编号为1的牌从数字1开始顺时针数下去,1、2、3、…、20、21、…,一圈又一圈。问:当数到数字N时,所在纸牌的编号为( )?
7、“蜂巢问题”:有一只蜜蜂沿如下图所示的蜂巢爬行,蜂巢编号为1到n,上面的为奇数,下面的为偶数,它只能由小号爬入大号相邻的巢,如果它从1号开始向N号爬,共有多少种不同的走法?
8、“圆桌问题”之相邻不重复:有n个人坐在一张圆桌上吃饭,要求每天每一个人两边相邻的人不同,问这样最多可以安排多少天?如3个人时只能1天,4个人时也只能是1天,而5个人可以安排2天。
9、一个二叉树的前序遍历结果为ABCDE,中序遍历结果为BADCE,那么它的后序遍历结果是什么?
10、一个商场有m种颜色的小球,每种小球足够多,在这m种小球中挑选n个小球的选法有多少种?如 m=2,n=3 时有4种选法分别是:两种小球的个数分别为03,12,21,30.问:当m=4,n=4时,选法数=( )。
11、如果一棵m度树中有n1个度为1的结点,n2个度为2的结点,…….有nm个度为m的结点,则该树中叶结点的的个数=( )。
12、已知:1到10中有两个数1、7不能被2,3,5整除,那1到1000中有多少个数不能被2,3,5 整除?
13、有30个连续的自然数,在其中选三个数,这三个数的和能整除3,共有多少种选法?
14、下图中用点表示城市,点与点之间的联线表示城市间的道路:试问:
①能否找出一条从A城市出发,经过图中所有道路一次后又回到出发点的通路来?
②能否从A出发,找出去每个城市且只去一次的通路来?若能,则写出通路;否则说明理由。
15、为了便于处理表达式,常常将普通表达式(称为中缀表示)转换为:前缀(运算符在前,如X/Y写为/XY)和后缀(运算符在后,如X/Y写为XY/)的表达式。在这样的表示中可以不用括号即可确定求值的顺序,如:
(P+Q)*(R-S) →*+PQ-RS或→ PQ+RS-*
①试将下面的表达式改写成前缀与后缀的表示形式:
(a) A+B*C/D (b) A-C*D+B^E
②试将下面的前缀表示还原成中缀的表示形式,同时写出后缀表示:
+△A*B△C【前缀式中△表示一元运算符取负号,如△A表示(-A)】
16、设A是一个n阶上三角阵,将这个上三角阵按列序存储一维数组b[n*(n+1)/2]中,如果a[I,j]存放在b[k],那么请给出求解k的计算公式。设A是一个一维数组a[m*n],现将这个数组按列序存储在一个m*n的矩阵B中,如果a[k]存放在b[I,J],那么请给出求解I,J的计算公式。
17、用邻接矩阵表示下面的无向图:
鸽巢原理与容斥原理每日练习参考答案:
1、C(7,2)*(5+6)+C(5,2)*(7+6)+C(6,2)*(7+5)+7*6*5=21*11+10*13+15*12+210=231+130+180+210=751
2、21*10+21*15+10*15+21*30+10*42+15*35=1155+525+570=2250
3、D;4、D,8*7!/2!/4!-4*C(5,2)-4*5=8*3*5*7-40-20=840-60=780
5、4;6、1+(N-1)mod 13
7、f(n)=f(n-1)+f(n-2) (n>2)f(1)=1 f(2)=1
8、(n-1)/2 (n为奇数时);n/2-1(n为偶数时)
9、BDECA;10、35 ;11、n2+2n3+…+(m-1)nm+1;12、266
13、c(10,3)*3+c(10,1)*c(10,1)*c(10,1)=1360
14、①能;②不能,因为C与四个城市邻接,不可能一次遍历
15、注意:先依中缀或前缀表达式画出表达式树,再根据后序遍历方法写出后缀表达式:
1)前缀:+A/*BCD,后缀:ABC*D/+;
2)中缀:-A+B*(-C);后缀:A△BC△*+
16、1)K=I+J(J-1)/2 2)K=I+(J-1)N
17、(略)