排列（考虑顺序）

全排列：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: 

组合数的性质２: 

排列组合解题注意：

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，．．．．．．

自测练习

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) 6男２女排成一排，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：某班在短跑、投掷和跳远三项比赛中的人数分布如下。

单短跑	单投掷	单跳远	短跑+投掷	短跑+跳远	跳远+投掷	跑+跳+投	没参加的人数	参加的人数
19	21	20	10	9	6	3	4	88

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 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、一个商场有m种颜色的小球，每种小球足够多，在这m种小球中挑选n个小球的选法有多少种？如 m=2，n=3 时有4种选法分别是：两种小球的个数分别为03，12，21，30．问：当m=4，n=4时,选法数=( )。
10、如果一棵m度树中有n1个度为1的结点，n2个度为2的结点，…….有nm个度为m的结点,则该树中叶结点的的个数=( )。

11、已知:1到10中有两个数1、7不能被2，3，5整除，那1到1000中有多少个数不能被2，3，5 整除？
12、有30个连续的自然数，在其中选三个数，这三个数的和能整除3，共有多少种选法？

13、设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的计算公式。

---

鸽巢原理与容斥原理自测练习参考答案：

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、35 ；10、n2+2n3+…+(m-1)nm+1；11、266

12、c(10,3)*3+c(10,1)*c(10,1)*c(10,1)=1360

13、1）K=I+J(J-1)/2    2）K=I+(J-1)N