组合学问题在生活中随处可见。  
例如,计算世界杯比赛场次、计算彩票摸奖概率等。  
组合数学是数学的重要分支,其快速发展的原因:  
1、计算机对社会的影响越来越大,很多计算机程序的基础往往是基于组合学思想设计的算法。  
2、组合数学的适用性越来越广,包括社会科学、生物科学、信息论等领域。  
组合数学一般有存在性问题、计数问题、构造性算法、最优化问题四个方面。  
存在性问题:工程实际或科学研究提出各种问题,有些可以判定其有解或无解,但也有不少难以判定。  
计数问题:如一个组合问题的解已知是存在的,自然会问有多少不同的解。  
构造性算法:一个组合问题,已判知解存在,甚至也可以推知有几组解,需要从组合论角度设计算法,使之较好地构造出解。  
优化问题:一个问题的构造性算法可能不止一种,如何择优?如何改进?使问题的解在多项式时间复杂性要求下能解出来,不出指数级情况的“组合爆炸”。  
NOIP初赛知识点(十二)组合数学基础
排列(在乎顺序)  
全排列: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:  
NOIP初赛知识点(十二)组合数学基础
组合数的性质2:  
NOIP初赛知识点(十二)组合数学基础
练习:  
NOIP初赛知识点(十二)组合数学基础 
排列组合解题注意:  
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这两种。  
错排公式:  
NOIP初赛知识点(十二)组合数学基础  
同时也有:  
NOIP初赛知识点(十二)组合数学基础
错位排列数列为: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,....。  
NOIP初赛复习(三)栈与卡特兰数>>>  
该递推关系的解为:  
NOIP初赛知识点(十二)组合数学基础
NOIP初赛知识点(十二)组合数学基础  
每日练习  
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个物体。  
容斥原理  
例1:某班在短跑、投掷和跳远三项比赛中的人数分布如下。  
NOIP初赛知识点(十二)组合数学基础
NOIP初赛知识点(十二)组合数学基础
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怎么算呢?  
NOIP初赛知识点(十二)组合数学基础
NOIP初赛知识点(十二)组合数学基础 
|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:画大图,清晰明了。  
算术序列(等差序列)  
25811?17……答案是:14  
特点:相邻两个数的差是固定的常数d!(注意:d可以是负数)  
通项公式:若初始项为a1:则递推关系为an=a1+(n-1)*d;  
对应的各项为:a1,a1+d,a1+2d,....,a1+(n-1)*d;  
求和公式:  
公式1:平均数*n结果为  
NOIP初赛知识点(十二)组合数学基础,只需要知道:头,尾,n  
公式2:代入公式1,可变形为n*a1+n*(n-1)*d/2,只需要知道:头或尾、d、n  
几何序列(等比序列)  
248?3264…..答案是:16  
特点:相邻两个数的比是固定的常数q!(注意:q可以是负数,分数,什么都有可能)  
通项公式:若初始项为a1:则递推关系为:NOIP初赛知识点(十二)组合数学基础对应的各项为:a1,a1*q,a1*q^2,....  
求和公式:
 NOIP初赛知识点(十二)组合数学基础
公式:只需要知道:头,q,n  
Fibonacci序列(斐波那契数列)  
011235?1321……答案是:11  
特点:每一项是它前两项的和  
通项公式:  
NOIP初赛知识点(十二)组合数学基础
求和公式:前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.20B.8C.16D.12E.24  
4、由3个a,5个b和2个c构成的所有字符串中,包含子串“abc”的共有()个。  
A.40320B.39600C.840D.780E.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、下图中用点表示城市,点与点之间的联线表示城市间的道路:试问:  
NOIP初赛知识点(十二)组合数学基础
①能否找出一条从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)mod13  
7、f(n)=f(n-1)+f(n-2)(n>2)f(1)=1f(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)/22)K=I+(J-1)N  
17、(略)