NOIP初赛复习(十二)组合数学基础

组合学问题在生活中随处可见。

例如,计算世界杯比赛场次、计算彩票摸奖概率等。

组合数学是数学的重要分支,其快速发展的原因:

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种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种?

NOIP初赛复习(十二)组合数学基础-少儿编程网

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:画大图,清晰明了。

算术序列 (等差序列)

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结果为

NOIP初赛复习(十二)组合数学基础-少儿编程网,只需要知道:头,尾,n

公式2:代入公式1,可变形为 n*a1+n*(n-1)*d/2,只需要知道:头或尾、d、n

几何序列 (等比序列)

2 4  8  ? 32  64  ….. 答案是:16

特点:相邻两个数的比是固定的常数q!(注意:q可以是负数,分数,什么都有可能)

通项公式:若初始项为a1:则递推关系为:NOIP初赛复习(十二)组合数学基础-少儿编程网

对应的各项为:a1,a1*q,a1*q^2,....

求和公式:

公式:NOIP初赛复习(十二)组合数学基础-少儿编程网只需要知道:头,q,n

Fibonacci序列(斐波那契数列)

0 1 1  2  3  5   ?   13  21……答案是: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

NOIP初赛复习(十二)组合数学基础-少儿编程网

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、下图中用点表示城市,点与点之间的联线表示城市间的道路:试问:

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、用邻接矩阵表示下面的无向图:

NOIP初赛复习(十二)组合数学基础-少儿编程网


鸽巢原理与容斥原理每日练习参考答案:

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、(略)

*文章为作者独立观点,不代表少儿编程网立场
发表评论

坐等沙发
相关文章
新手想参加信息学竞赛NOIP ,如何入门进阶?
新手想参加信息学竞赛NOIP ,如何入门进…
从NOIP三年榜单看全国信息学竞赛形势(2017终结版)
从NOIP三年榜单看全国信息学竞赛形势(2…
IOI金牌再传秘笈:水平不高怎么拿NOIP一等奖?
IOI金牌再传秘笈:水平不高怎么拿NOIP一…
杜博闻:信息学奥赛一等奖,获三所名校保送资格!
杜博闻:信息学奥赛一等奖,获三所名校…
这些参加信息学竞赛的娃高一就保送清华!
这些参加信息学竞赛的娃高一就保送清华!
【NOIP专栏】搜狗CEO王小川的传奇人生!
【NOIP专栏】搜狗CEO王小川的传奇人生!
NOIP2017 作者
NOI官网发布了2017年全国青少年信息学奥林匹克联赛(NOIP2017)的报名通知。NOIP2017将于2017年10月及11月分别举行初赛和复赛,有意向参加比赛的考生,即日起至10月10日可报名。