第1章组合数学基础
1、排列组合的基本计数问题（研、本）
2、计算多项式系数（研、本）
3、排列组合算法（研）
1.1 绪论
（一）背景
起源：数学游戏
幻方问题：给定自然数1,2,…,n2，将其排列成n阶方阵，要求每行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和。
例：图1.1.1为3阶幻方，其幻和等于15。
（1）存在性问题：即n阶幻方是否存在？
（2）计数问题：如果存在，对某个确定的n，这样的幻方有多少种？
（3）构造问题：即枚举问题，亦即如何构造n阶幻方。
图1.1.1 3阶幻方
奇数阶幻方的生成方法：
一坐上行正中央，依次斜填切莫忘，
上边出格往下填，右边出格往左填，
右上有数往下填，右上出格往下填。
例：将2，4，6，8，10，12，14，16，18填入下列幻方：
例1.1.1 （拉丁方）36名军官问题：有1，2，3，4，5，6共六个团队，从每个团队中分别选出具有A 、B 、C 、D 、E 、F 六种军衔的军官各一名，共36名军官。问能否把这些军官排成6×6的方阵，使每行及每列的6名军官均来自不同的团队且具有不同军衔？
本问题的答案是否定的。 反例：
A1 B2 C3 D4 E5 F6 A1 B2 C3 D4 E5 F6 B2 C3 D4 E5 F6 A1 B3 C4 D5 E6 F1 A2 C3 D4 E5 F6 A1 B2 C5 D6 E1 F2 A3 B4 D4 E5 F6 A1 B2 C3 D2 E3 F4 A5 B6 C1 E5 F6 A1 B2 C3 D4 E4 F5 A6 B1 C2 D3 F6 A1 B2 C3 D4 E5 F6
例1.1.2 （计数——图形染色）用3种颜色红（
r ）、黄（y ）、蓝（b ）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。例如，对图1.1.2的涂染方案(a)，当正方形逆时针旋转o 90时就变为方案(b)，因此，在正方形可旋转的前提下，这两种方案实质上是一种方案。那么，我们要问：不同的染色方案共有多少种？
（a ）
（b ）
图1.1.2 正方形的顶点染色
染色方案的总数为：43＝81种。
问题：要计算不同的染色方案，显然属于计数问题。在旋转条件下，不同的染色方案总数为（见第6章）
L ＝
()
32334
124
?++＝24 例1.1.3 （存在性）不同身高的26个人随意排成一行，那么，总能从中挑出6个人，让其出列后，他们的身高必然是由低到高或由高到低排列的（见第5章）。 （二） 研究内容 算法分类：
● 第一类：是计算方法。主要解决数值计算问题，如方程求
根、解方程组、求积分等，其数学基础是高等数学与线性代数。 ● 第二类：组合算法，解决搜索、排序、组合优化等问题，其数学基础就是组合数学。 按所研究问题的类型，组合数学所研究的内容可划分为： ● 组合计数理论 ● 组合设计 ● 组合矩阵论 ● 组合优化
本课程重点：以组合计数理论为主，部分涉及其它内容。 （三） 研究方法
分类：
第一类：从组合学基本概念、基本原理出发解题的所谓常规方法，例如，利用容斥原理、二项式定理、P ólya 定理解计数问
题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等。
第二类：通常与问题所涉及的组合学概念无关，而对多种问题均可使用。例如：
（1） 数学归纳法：前提是已知问题的结果。 （2） 迭代法
例. 如已知数列{}n h 满足关系???=+=-1
,
1211h h h n n ，求n h 的解析
表达式。
直接迭代即得：
121+=-n n h h
＝()1222+-n h +1＝12222++-n h
＝()1212232+++-n h ＝1222233+++-n h
＝12222223211++++++--- n n n h ＝12-n
（3） 一一对应技术
原理：建立两类事物之间的一一对应关系，把一个较复杂的组合计数问题A 转化成另一个容易计数的问题B ，从而利用对B 的计数运算达到对A 的各种不同方案的计数。
思路：利用它将问题的模式转化为一种已经解决的问题模式。 （4） 殊途同归方法
原理：从不同角度讨论计数问题，以建立组合等式。 应用：组合恒等式的证明（也称组合意义法）。 （5） 数论方法
特别是利用整数的奇偶性、整除性等数论性质进行分析推理的方法。
组合数学用的较多的是方法（3）与（4）。
例1.1.4 有100名选手参加羽毛球比赛，如果采用单循环淘汰制，问要产生冠军共需要进行多少场比赛？
（解）常规思路：50+25+12+6+3+2+1＝99场
采用一一对应方法：因为采用的是单循环淘汰制，所以每两名选手比赛产生一个失败者，且每个失败者只能失败一次。反之，要淘汰一个选手，必须恰好经过一场比赛。因此，失败的人数与比赛场数之间一一对应，计算比赛场数问题转化为计算失败人数问题。后者的解显然是99人，故应该比赛99场。
一般情况：单循环淘汰制的比赛，若有n个选手参考比赛，则须经过n-1场比赛，方可产生冠军。
例1.1.5 设某地的街道将城市分割成矩形方格，某人在其住处A（0，0）的向东7个街道、向北5个街道的大厦B（7，5）处工作（见图1.1.3），按照最短路径（即只能向东或向北走），他每次上班必须经过某12个街段，问共有多少种不同的上班路线？
（解）将图中所有街区抽象为大小一样的矩形，其东西方向的长为x，南北方向的长为y。从A（0，0）点出发，向东走一段为x，向北走一段为y。
B(7,5)
A (0,0)
图1.1.3 最短路径
那么不管怎么走，从A 点出发，总是要经过7个x ，5个y ，方能到达B 点。所以，一条从A 到B 的路线对应一个由7个x ，5个y 共12个元素构成的排列。
ｘｙｙｘｘｙｙｘｘｘｘｙ
反之，给定一个这样的排列，按照x 、y 的含义，必对应一条从A 到B 的行走路线。例如，排列
ｙｘｘｙｙｙｙｘｘｘｘｘ
对应的路线为：由A 点出发，先向北走1段街道，再向东走2个街道，又转向北走4个街道，再向东走5个街道，即到达目的地B 。 所以，从A （0，0）到B （7，5）的最短路径与7个x ，5个y 的排列一一对应。故所求的上班路线数为
N ＝55
7C +＝5
12C ＝!
7!5!
12?＝792 一般情形：从（0，0）点到达（m ，n ）点的不同的最短路径数为
N ＝m n m +C
（四） 学习方法
类似于《线性代数》，与《高等数学》和《概率论》不同。
1.2 两个基本法则
1.2.1 加法法则 （一） 加法法则
●常规描述：如果完成一件事情有两个方案，而第一个方案
有m种方法，第二个方案有n种方法可以实现。只要选择
任何方案中的某一种方法，就可以完成这件事情，并且这
些方法两两互不相同。则完成这件事情共有m＋n种方法。
●集合描述：设有限集合A有m个元素，B有n个元素，且A
与B不相交，则A与B的并共有m＋n个元素。
●概率角度描述：设事件A有m种产生方式，事件B有n种
产生方式，则事件“A或B”有m＋n种产生方式。当然A
与B各自所含的基本事件是互相不同的。
（二）应用
例1.2.1某班又男生18人，女生12人，从中选出一名代表参加会议，问共有多少种选法？
（解）用集合A表示男生，B表示女生，则该班中的学生要么属于A，要么属于B。根据加法法则，全班共有30
+个学生，
12
18=
故有30种选法。
例1.2.2用一个小写英文字母或一个阿拉伯数字给一批机器编号，问总共可能编出多少种号码？
（解）英文字母共有26个，数字0~9共10个，由加法法则，总共可以编出36
+个号码。
10
26=
1.2.2 乘法法则
（一）乘法法则
●常规描述：如果完成一件事情需要两个步骤，而第一步有m
种方法、第二步有n种方法去实现。则完成该件事情共有
m·n种方法。
●集合描述：设有限集合A有m个元素，B有n个元素，且A
与B不相交，B
∈,，记()b
a∈
A
b
a,为一有序对。所有有序对构成的集合称为A和B的积集（或笛卡儿乘积），记作
m?个元素。
A?共有n
A?。那么，B
B
B A ?＝(){}B b A a b a ∈∈,,
概率角度描述：设离散型随机变量X 有m 个取值，Y 有n
个取值，则离散型随机向量（X ，Y ）有n m ?种取值可能。 （二） 应用
例1.2.3 仍设某班有男生18人，女生12人，现要求从中分别选出男女生各一名代表全班参加比赛，问共有多少种选法？ （解） 仍像例1.2.1那样，用集合A 表示男生，B 表示女生，那么，根据乘法法则，共有2161218=?种选法。
例1.2.4 给程序模块命名，需要用3个字符，其中首字符要求用字母A ~G 或U ~Z ，后两个要求用数字1~9，问最多可以给多少种程序命名？
（解） 首先，由加法法则，首字符共有1367=+种选法。其次，再由乘法法则，最多可以产生10539913=??个不同的名称。
例1.2.5 从A 地到B 地有1n 条不同的道路，从A 地到C 地有2n 条不同的道路，从B 地到D 地有1m 条不同的道路，从C 地到D 地有2m 条不同的道路，那么，从A 地经B 或C 到达目的地D 共有多少种不同的走法?
解 首先，由乘法法则，从A 地经B 到达D 地共有1n ×1m 种走法, 由A 经C 到达D 共有2n ×2m 种走法,再由加法法则知, 从A 地经B 或C 到达D 地共有1n 1m ＋2n 2m 种不同的走法。
例
2×3＋3×4＝18
1.3 排列与组合
1.3.1 相异元素不允许重复的排列数和组合数 （一） 计算公式
从n 个相异元素中不重复地取r 个元素的排列数和组合数分别为：
排列： ()()()()!
!
11,P P r n n r n n n r n r n -=
+--== (1.3.1) 组合： ()()!r !r n !n !r P r n r ,n C C r
n r n
-==???
? ??== (1.3.2) 例：n ＝5，r ＝3，即元素为1，2，3，4，5 排列：134，431，143， 254，425 组合：134，245
特点：排列考虑顺序，组合则不然。 （二） 数学模型
（1）排列问题：将r 个有区别的球放入n 个不同的盒子，每
盒不超过一个，则总的放法数为P (n ，r )。 （2）组合问题：将r 个无区别的球放入n 个不同的盒子，每盒不超过一个，则总的放法数为C (n ，r )。
1.3.2 相异元素允许重复的排列
（一）问题
即从n个不同元素中允许重复地选r个元素的排列，简称r 元重复排列。其排列的个数记为RP(∞，r)。
（二）模型
将r个不相同的球放入n个有区别的盒子，每个盒子中的球数不加限制而且同盒的球不分次序。
（三）计算公式
RP(∞，r )＝ r n 。
（四） 集合描述方式
设无穷集合{}n e e e ?∞?∞?∞=,,, 21，即S 中共含有n 类元素，每个元素有无穷多个，从S 中取r 个元素的排列数即为RP(∞，r )。 1.3.3 不尽相异元素的全排列 （一） 问题
有限重复的排列（或称部分排列）：设
{}t t e n e n e n S ???=,,,2211 ，即元素i e 有i n 个（i=1,2,…,t ）
，且n n n n t =+++ 21，从S 中任取r 个元素，求其排列数RP(n ，r )。
（二） 模型
将r 个有区别的球放入t 个不同的盒子，而每个盒子的容量是有限的，其中第i 个盒子最多只能放入i n 个球，求分配方案数。
例： S ＝{2·1，4·2，1·3，3·4，2·5}
说明：相对于前两种情况而言，此处讲的是有限重复的排列问题，即相异元素不重复的排列强调的是不重复，即盒子的容量为1；允许重复的排列实际上针对的是无限重复，即盒子的容量无限。二者都是极端的情况。而有限重复问题恰好介于两者之间，即盒
子的容量有限。
（三） 特例 （1） r ＝1
（2）
r ＝n （全排列）
()!
!!!
,RP 21t n n n n n n =
(1.3.3) 即先视为n 个不同元素的全排列，共有n!种。但每个排列实际重复统计了!!!21t n n n 次。原因是当元素不同时，同类元素互相交换位置，对应不同的排列。而当同类元素相同时，针对每个确定的排列，同类元素互相交换位置，该排列不变。
（3） t ＝2，()???
? ??==121!!!
,RP n n n n n n n （4） i n ＝1，即不重复的排列 （5） ∞=i n ，即重复排列
1.3.4 相异元素不允许重复的圆排列 （一） 圆排列
例1.3.1 把n 个有标号的珠子排成一个圆圈，共有多少种不同的排法？
（解）典型的圆排列问题。
条件：对于围成圆圈的n 个元素，同时按同一方向旋转，即
每个元素都向左（或向右）转动一个位置，虽然元素的绝对位置
发生了变化，但相对位置未变，即元素间的相邻关系未变，这样的圆排列认为是同一种，否则便是不同的圆排列。
解法一：先令n 个相异元素任意排成一行（称为线排列），共有n !种排法，再将其首尾相接围成一圆，当圆转动一个角度时，对应另一个线排列，当每个元素又转回到原先的位置时，相当于n 个不同的线排列，故圆排列数为
CP(n ，n )＝
()n
n n P ,＝(n －1)! (1.3.4) 解法二：先取出某一元素k ，放于圆上某确定位置，再令余下的n －1个元素作成一个线排列，首尾置于k 的两侧构成一个圆排列同样可得到CP (n ，n )＝(n －1)!。
（a ） （b ）
例1.3.2 从n 个相异元素中不重复地取r 个围成圆排列，求不同的排列总数CP(n ，r )。
（解）要完成这个圆排列，需先从n 个元素中取r 个，再将其组成圆排列，故
CP(n ，r )＝ ()r
r n P , ＝()!!r n r n - (1.3.5) （二） 项链排列
例1.3.3 将5个标有不同序号的珠子穿成一环，共有多少种不
同的穿法？
（解）典型的项链排列问题。
首先，由例1.3.1知，5个相异元素的圆排列共有(5-1)!=24种。其次，对于圆排列而言，将所穿的环翻过来，是另一种圆排列，但对于项链排列，这仍然是同一个排列（如图1.3.1所示），故不同的排法共有24/2＝12种。
一般情形，从n 个相异珠子中取r 个穿成一个项链，共有
()r
r n P 2, ＝ ()!2!r n r n - (1.3.6) 种不同的穿法。
（a ） （b ）
图1.3.1 项链排列
允许重复的圆排列：情况复杂（参见反演公式相关内容）。
1.3.5 相异元素允许重复的组合 （一） 问题
设{}n e e e S ?∞?∞?∞=,,,21 ，从S 中允许重复地取r 个元素构成组合，称为r 可重组合，其组合数记为RC(∞，r )。 （二） 抽象
将S 的n 个不同元素分别用数字1，2，…，n 来表示。 例： n ＝5，r ＝4 1111，1122，1345，5555 （三） 计算公式
所取出的r 个元素从小到大设为a 1，a 2，… a r ，则a i 满足：
1?a 1?a 2?…?a r ?n
令
b i ＝a i ＋(i －1)，i ＝1，2，…，r
则
1?b 1＜b 2＜…＜b r ?n ＋(r －1)
对应一个从n ＋r －1个相异元素中不允许重复地取r 个元素的组合。反之，后者的一种组合也与前者的一种组合相对应。所以，两种组合一一对应。从而
()()()()!
1!!
1,1C ,RC --+=-+=∞n r r n r r n r (1.3.7)
例： n ＝5，r ＝4
（四） 模型
重复组合的模型是将r 个无区别的球放入n 个不同的盒子，
每个盒子的球数不受限制。 （五） 应用
例1.3.4 不同的5个字母通过通信线路被传送，每两个相邻字母之间至少插入3个空格，但要求空格的总数必须等于15，问共有多少种不同的传送方式？
（解）将问题分为三步求解：
（1）先排列5个字母，全排列数为 P (5，5)＝5!。 （2）两个字母间各插入3个空格，将12个空格均匀地放入4个间隔内，有1种方案。
（3）将余下的3个空格插入4个间隔：即将3个相同的球放入4个不同的盒子，盒子的容量不限。其方案数即为从4个相异元素中可重复地取3个元素的组合数()()203,1343,=-+=∞C RC 。
c △△△ b △△△
d △△△
e △△△△△△
a
方案1 △△ △ 方案2 （4）总的方案数 L ＝5！·1·20＝2400 1.3.6 不尽相异元素任取r 个的组合问题 （一） 问题
设集合{}t t e n e n e n S ???=,,,2211 ，n n n n t =+++ 21，从S 中任取r 个，求其组合数RC(n ，r )。 （二） 组合数
设多项式
∏∑==t
i n j j i
x 10＝(
)∏=++++t
i n i x x x 1
2
1 ＝∑=n
r r
r x
a 0
则RC(n ，r )就是多项式中r x 的系数，即
RC(n ，r )＝r a
（三） 应用
例1.3.5 整数360有几个正约数？
（解）（1） 分解360为素因子的幂的乘积
360＝23×32×5
（2）正约数
1＝20×30×50，2＝2×30×50，3＝20×3×50， 5＝20×30×5，22＝22×30×50，6＝2×3×50＝3×2，
…
180＝22×32×5，360＝23×32×5
（3）问题转化：即从集合{}５，１，２???=323S 的6个元素中任取0个、1个、……、6个的组合数之和。
（4）求解：构造多项式
P 6 (x)＝（1＋x ＋x 2＋x 3）（1＋x ＋x 2）（1＋x ）
＝1＋3x ＋5x 2＋6x 3＋5x 4＋3x 5＋x 6
求各项系数之和：
L=()∑=6
0,6i i RC ＝1＋3＋5＋6＋5＋3＋1＝24
简单方法：多项式P 6(x )的系数之和实质上就是求P 6(1)。即
P 6(x )＝
()∑=6
,6i i RC ＝4×3×2＝24
（5）一般结论：设正整数n 可以因子分解为
n ＝k k p p p α
αα 2121，
则n 的正约数个数为
L=()()()11121+++k ααα
（四） 习题：18，21
1.4 组合等式及其组合意义
组合等式的证明方法大致可归纳为以下三种： （一） 归纳法
（二） 组合意义法：是指借助于阐明等号两端的不同表达式实
质上是同一个组合问题的方案数（即殊途同归法），或者虽是两个不同组合问题的方案数，但二者的组合方案之间存在着一一对应关系，因此等式两端必须相等，从而达到证明等式成立的目的。对于恒等式的实质揭露得更为深刻。 （三） 母函数法：利用无穷级数（包括有限时的多项式）证明
有关组合等式。是产生和证明组合恒等式的普遍方法。 等式1 称关系式
C (n ，r )＝C (n ，n －r) （1.4.1）
组合意义 从n 个元素{}n a a a ,,, 21中取走r 个，必然余下n －r 个，故从n 取r 的组合与从n 取n －r 的组合一一对应。
等式2 法公式
C (n ，r )＝C (n －1，r )＋C (n －1，r －1) （1.4.2） （一）组合意义：从n 个元素{}n a a a ,,, 21中取r 个组合，就其中某个元素，不妨设为a 1来看，全体组合可分为两类： （1） 每次取出的r 个元素中都含有a 1，这一类组合可视为从剩下的n －1个元素中任取r －1个元素，然后再加上a 1而构成的组合，其组合数为C (n －1，r －1)。
（2） 不含元素a 1，这类组合可视为从其余n －1个元素中任取r 个元素的组合，其数目为C (n －1，r )。
两类情况互不重复，由加法法则，式（1.4.2）成立。
（二）例：从{1，2，3，4，5}中取3个的组合情况为：
第一类（包含元素“1”）：123，124，125，134，135，145 第二类（不包含元素“1”）：234，235，245，345
（三）路径问题：加法公式（1.4.2）的等价形式是
C(m＋n，m)＝C（m＋n－1，m）＋C（m＋n－1，m－1）（1.4.3）
组合意义：从（0，0）点到（m，n）点的路径数等于从（0，0）点分别到（m，n－1）点和（m－1，n）点的路径数之和。
B(m,n)
A(0,0)
等式3法公式
C(n，k) C(k，r)＝C(n，r) C(n－r，k－r) （1.4.4）组合意义考虑等式
C(n，n－k) C(k，k－r) C(r，r)
＝C(n，r) C(n－r，n－k) C(k－r，k－r) （1.4.5）
左端：“将n个元素分为3堆，要求第一堆有n－k个元素，第二堆有k－r个，那么，第三堆就只有r个元素”的组合方案数。
右端：另一个类似的组合问题“将n个元素分为3堆，要求第三堆有r个元素，第二堆有n－k个，第一堆有k－r个元素”的组合方案数。
两个组合问题等价，故其方案数亦相等。
等式4 C (n ＋r ＋1，r)＝
()∑=+r
i i i n C 0
,
＝ C (n ＋r ，r )＋C (n ＋r －1，r －1)＋C (n ＋r －2，r －2)
＋C (n ＋r －3，r －3)＋…＋C (n ，0) （1.4.6）
或 C (n ＋r ＋1，r )＝
()∑=+r
i n i n C 0
,
＝ C (n ＋r ，n )＋C (n ＋r －1，n )＋C (n ＋r －2，n )
＋…＋C (n ，n ) （1.4.7）
（一）组合意义：从n ＋r ＋1个元素{}121,,,++r n a a a 中取r 个的组合情况，分类统计：
（1） 将所有组合针对a 1分为两类：即所取r 个元素中含元素a 1或不含元素a 1。对不含元素a 1的情形，相当于从n ＋r 个元素{}132,,,++r n a a a 中取r 个的组合，其组合数为()r r n C ,+； （2） 仿照（1），再将含有元素a 1的所有组合针对a 2分为两类：即所取r 个元素中含a 2或不含a 2，同样考虑不含a 2的情形，这又相当于从除去a 1、a 2后的n ＋r －1个元素{}143,,,++r n a a a 中取r －1个，再加上a 1而构成组合，其组合数为C (n ＋r －1，r －1)； （3） 同法，r －1组合中含元素a 1、a 2，但不含a 3的组合数为C (n ＋r －2，r －2)；
()r 组合中含元素a 1、a 2、…、a r
－1
，但不含a r 的组合数为C (n
＋1，1)； ()1+r 组合中含元素a 1、a 2、…、a r 的组合数为C (n ＋1，0)
＝C (n ，0) .
（二）说明：实际上，组合等式3是等式2的推广，等式2只是将r 组合分为两类，而等式3则是分为r ＋1类来考虑问题。
r r n C 1++＝1-+++r r n r r n C C
高中数学讲义 1．基本计数原理 ⑴加法原理 分类计数原理：做一件事，完成它有n 类办法，在第一类办法中有1m 种不同的方法，在第二类办法中有2m 种方法，……，在第n 类办法中有n m 种不同的方法．那么完成这件事共有12n N m m m =+++种不同的方法．又称加法原理． ⑵乘法原理 分步计数原理：做一件事，完成它需要分成n 个子步骤，做第一个步骤有1m 种不同的方法，做第二个步骤有2m 种不同方法，……，做第n 个步骤有n m 种不同的方法．那么完成这件事共有12n N m m m =???种不同的方法．又称乘法原理． ⑶加法原理与乘法原理的综合运用 如果完成一件事的各种方法是相互独立的，那么计算完成这件事的方法数时，使用分类计数原理．如果完成一件事的各个步骤是相互联系的，即各个步骤都必须完成，这件事才告完成，那么计算完成这件事的方法数时，使用分步计数原理． 分类计数原理、分步计数原理是推导排列数、组合数公式的理论基础，也是求解排列、组合问题的基本思想方法，这两个原理十分重要必须认真学好，并正确地灵活加以应用． 2． 排列与组合 ⑴排列：一般地，从n 个不同的元素中任取()m m n ≤个元素，按照一定的顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列．（其中被取的对象叫做元素） 排列数：从n 个不同的元素中取出()m m n ≤个元素的所有排列的个数，叫做从n 个不同元素中取出m 个元素的排列数，用符号A m n 表示． 排列数公式：A (1)(2) (1)m n n n n n m =---+，m n +∈N ，，并且m n ≤． 全排列：一般地，n 个不同元素全部取出的一个排列，叫做n 个不同元素的一个全排列． n 的阶乘：正整数由1到n 的连乘积，叫作n 的阶乘，用!n 表示．规定：0!1=． ⑵组合：一般地，从n 个不同元素中，任意取出m ()m n ≤个元素并成一组，叫做从n 个元素中任取m 个元素的一个组合． 组合数：从n 个不同元素中，任意取出m ()m n ≤个元素的所有组合的个数，叫做从n 个不同元素中，任意取出m 个元素的组合数，用符号C m n 表示． 组合数公式：(1)(2)(1)!C !!()! m n n n n n m n m m n m ---+==-，,m n +∈N ，并且m n ≤． 组合数的两个性质：性质1：C C m n m n n -=；性质2：11C C C m m m n n n -+=+．（规定0 C 1n =） 知识内容 排列组合问题的常见模型 1
高考数学排列组合难题解决方法 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1m 种不同的方法，在第2类办法中有2m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有： 12n N m m m =+++ 种不同的方法． 2.分步计数原理（乘法原理） 完成一件事，需要分成n 个步骤，做第1步有1m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有： 12n N m m m =??? 种不同的方法． 3.分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件． 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素. 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置. 先排末位共有13C 然后排首位共有1 4C 最后排其它位置共有34A 由分步计数原理得113 4 34288C C A = C 14A 34C 13 位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的要求,再处理其它位置。若有多个约束条件，往往是考虑一个约束条件的同时还要兼顾其它条件
高二数学知识点：排列与组合 排列组合公式/排列组合计算公式 排列P------和顺序有关 组合C-------不牵涉到顺序的问题 排列分顺序，组合不分 例如把5本不同的书分给3个人，有几种分法."排列" 把5本书分给3个人，有几种分法"组合" 1.排列及计算公式 从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号p(n，m)表示. p(n，m)=n(n-1)(n-2)……(n-m+1)=n!/(n-m)!(规定0!=1). 2.组合及计算公式 从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n 个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号 c(n，m)表示. c(n，m)=p(n，m)/m!=n!/((n-m)!*m!);c(n，m)=c(n，n-m); 3.其他排列与组合公式
从n个元素中取出r个元素的循环排列数=p(n，r)/r=n!/r(n-r)!. n个元素被分成k类，每类的个数分别是n1，n2，...nk这n 个元素的全排列数为 n!/(n1!*n2!*...*nk!). k类元素，每类的个数无限，从中取出m个元素的组合数为c(m+k-1，m). 排列(Pnm(n为下标，m为上标)) Pnm=n×(n-1)....(n-m+1);Pnm=n!/(n-m)!(注：!是阶乘符 号);Pnn(两个n分别为上标和下标)=n!;0!=1;Pn1(n为下标1为上标)=n 组合(Cnm(n为下标，m为上标)) Cnm=Pnm/Pmm;Cnm=n!/m!(n-m)!;Cnn(两个n分别为上标和下标)=1;Cn1(n为下标1为上标)=n;Cnm=Cnn-m 2019-07-0813：30 公式P是指排列，从N个元素取R个进行排列。公式C是指组合，从N个元素取R个，不进行排列。N-元素的总个数R参与选择的元素个数!-阶乘，如9!=9*8*7*6*5*4*3*2*1 从N倒数r个，表达式应该为n*(n-1)*(n-2)..(n-r+1); 因为从n到(n-r+1)个数为n-(n-r+1)=r 举例： Q1：有从1到9共计9个号码球，请问，可以组成多少个三位数?
微专题80 排列组合的常见模型 一、基础知识： （一）处理排列组合问题的常用思路： 1、特殊优先：对于题目中有特殊要求的元素，在考虑步骤时优先安排，然后再去处理无要求的元素。 例如：用0,1,2,3,4组成无重复数字的五位数，共有多少种排法？ 解：五位数意味着首位不能是0，所以先处理首位，共有4种选择，而其余数位没有要求，只 需将剩下的元素全排列即可，所以排法总数为44496N A =?=种 2、寻找对立事件：如果一件事从正面入手，考虑的情况较多，则可以考虑该事的对立面，再用全部可能的总数减去对立面的个数即可。 例如：在10件产品中，有7件合格品，3件次品。从这10件产品中任意抽出3件，至少有一件次品的情况有多少种 解：如果从正面考虑，则“至少1件次品”包含1件，2件，3件次品的情况，需要进行分类讨论，但如果从对立面想，则只需用所有抽取情况减去全是正品的情况即可，列式较为简单。 3310785N C C =-=（种） 3、先取再排（先分组再排列）：排列数m n A 是指从n 个元素中取出m 个元素，再将这m 个元素进行排列。但有时会出现所需排列的元素并非前一步选出的元素，所以此时就要将过程拆分成两个阶段，可先将所需元素取出，然后再进行排列。 例如：从4名男生和3名女生中选3人，分别从事3项不同的工作，若这3人中只有一名女生，则选派方案有多少种。 解：本题由于需要先确定人数的选取，再能进行分配（排列），所以将方案分为两步，第一步： 确定选哪些学生，共有2143C C 种可能，然后将选出的三个人进行排列：33A 。所以共有 213433108C C A =种方案 （二）排列组合的常见模型 1、捆绑法（整体法）：当题目中有“相邻元素”时，则可将相邻元素视为一个整体，与其他元素进行排列，然后再考虑相邻元素之间的顺序即可。 例如：5个人排队，其中甲乙相邻，共有多少种不同的排法
排列组合解法大全 复习巩固 1.分类计数原理（加法原理） 完成一件事，有n类办法，在第 1类办法中有m1种不同的方法，在第 2 类办法中有m2种不同的方法，?，在第n 类办法中有m n种不同的方法，那么完成这件事共有： 种不同的方法． 2.分步计数原理（乘法原理） 完成一件事，需要分成n个步骤，做第 1步有m1种不同的方法，做第 2步有m2种不同的方法，做第n步有m n种不同的方法，那么完成这件事共有： 种不同的方法． 3.分类计数原理分步计数原理区别分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件． 解决排列组合综合性问题的一般过程如下 : 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事 , 即采取分步还是分类 , 或是分步与分类同时进行 , 确定分多少步及多少类。 3.确定每一步或每一类是排列问题（有序）还是组合（无序）问题, 元素总数是多少及取出多少个元素 . 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一. 特殊元素和特殊位置优先策略 例 1. 由 0,1,2,3,4,5 可以组成多少个没有重复数字五位奇数 . 解: 由于末位和首位有特殊要求 , 应该优先安排 , 以免不合要求的元素占了这两个位置 . 先排末位共有C13 然后排首位共有C14 最后排其它位置共有A43 由分步计数原理得C41C13A43 288 练习题 :7 种不同的花种在排成一列的花盆里 , 若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？ 二. 相邻元素捆绑策略 例 2. 7 人站成一排 , 其中甲乙相邻且丙丁相邻 , 共有多少种不同的排法 . 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素部进行自排。由分步计数原理可得共有A55A22A22480种不同的排法 练习题 : 某人射击 8 枪，命中 4 枪， 4 枪命中恰好有 3 枪连在一起的情形的不同种数为20
排列与组合 教学内容：人教版义务教育课程标准实验教科书小学数学二年级上册第八单元的排列与组合。 教学目标： 1．通过观察、实验等活动，使学生找出最简单的事物的排列数和组合数，初步经历简单的排列和组合规律的探索过程； 2．使学生初步学会排列组合的简单方法，锻炼学生观察、分析和推理的能力，让学生初步感悟简单的排列、组合的数学思想方法。； 3．培养学生有序、全面思考问题的意识，通过小组合作探究的学习形式，养成与人合作的良好习惯。 4、感受数学与生活的紧密联系，培养学生学习数学的兴趣和用数学方法解决问题的意识。 教学重点：经历探索简单事物排列与组合规律的过程。 教学难点：让学生初步感悟简单的排列、组合的数学思想方法。 教学过程： 一、创设情境 师：同学们，你们喜欢看球赛吗？球赛的门票是5角，下面有1张5角的，2张2角的，5个1角的硬币，说一说，你是怎样付钱的？ （学生操作──在桌上摆5角钱。） （1）以小组为单位，互相说一说你的付钱方法，看谁想的最多。推荐一名同学汇报一下你们小组都想到了那些付钱的方法？ （2）指名同学进行汇报。 师：噢，你们想到的5角钱的拿法可真多，真是棒极了！那我们就一起买票进场吧。 ［设计意图］：激趣导入，让学生在游戏中产生兴趣，在活动中找到启示，把枯燥的数学变得趣味性。 二、探究新知 出示课件：（乒乓球赛场） 1．感知排列。 师：比赛前，运动员想请你们为他们编号，愿意吗？
要求：①请从1、2、3三张数字卡片中每次选两张组成一个两位数的号码，不许重复； ②三人一组，一个人当记录员，其余两人摆数字卡片，看哪组编的号码最多。（小组合作完成，然后回答所编的号码。） 2．汇报、讨论排列方法。 生可能： 方法一：每次拿出两张数字卡片能摆出不同的两位数； 方法二：固定十位上的数字，交换个位数字得到不同的两位数； 方法三：固定个位上的数字，交换十位数字得到不同的两位数． 3．教师评议方法：三种方法虽然不同，但都能正确并有序地摆出了６个不同的两位数。只要做到正确并有序，就能够不重复、不遗漏的把所有的方法找出来。在今后的学习和生活中，我们还会遇到许多这样的问题，我们都可以运用有序的思考方法来解决它们。同学们可以用自己喜欢的方法 ［设计意图］：以帮运动员编号的方法来进行数的排列教学，使学生在充满兴趣的情感中不知不觉地进入了摆数活动，让学生在体验中感受，在活动操作中成功，在交流中找到方法，在学习中应用。这里先让学生独立思考，调动学生自主学习的积极性，再小组合作，让学生在宽松民主的气氛中，参与学习过程。同时从学生已有的知识基础出发，适当增加了难度，有什么好办法能保证既不漏数、也不重复呢？初步培养学生有顺序地、全面的思考问题的意识。 4．感知组合 师：我们把排好的号码发给这些运动员以后，运动员还想请同学们帮个忙。请你们替他们选取运动服，你们乐意吗？ （课件出示：运动服：黄上衣、红上衣、蓝裤子、黄裤子。） 师：你觉得可以怎样搭配衣裤呢？ （小组讨论，动手摆一摆，然后指名在黑板上集中呈现搭配好的衣裤组合模型。）师：同学们想出了4种搭配方法。第一场比赛有三个运动员上场比赛，下面让我们以热烈地掌声欢迎运动员上场比赛。（鼓掌） （课件演示：三位运动员互相握手问好。） 师：瞧，他们还在互相握手问好呢！同学们想一想，有三位运动员，每两人握一次手，一共得握几次手？小组合作试一试，体验后再回答。 学生回答后，教师再问：排数时用了3个数字，握手时是3个学生，都是“3”，为什么出现的结果却不一样呢？（学生交流后得出：两个数字可以交换位置组成2个两位数，而两个人握手不能交换只能算一次。）
排列组合 一．选择题（共5小题） 1．甲、乙、丙三同学在课余时间负责一个计算机房的周一至周六的值班工作，每天1人值班，每人值班2天，如果甲同学不值周一的班，乙同学不值周六的班，则可以排出不同的值班表有（） A．36种B．42种C．50种D．72种 2．某城市的街道如图，某人要从A地前往B地，则路程最短的走法有（） A．8种 B．10种C．12种D．32种 3．某次联欢会要安排3个歌舞类节目，2个小品类节目和1个相声类节目的演出顺序，则同类节目不相邻的排法种数是（） A．72 B．120 C．144 D．168 4．现将甲乙丙丁4个不同的小球放入A、B、C三个盒子中，要求每个盒子至少放1个小球，且小球甲不能放在A盒中，则不同的放法有（） A．12种B．24种C．36种D．72种 5．从6人中选4人分别到巴黎、伦敦、悉尼、莫斯科四个城市游览，要求每个城市有一人游览，每人只游览一个城市，且这6人中甲、乙两人不去巴黎游览，则不同的选择方案共有（） A．300种B．240种C．144种D．96种 二．填空题（共3小题） 6．某排有10个座位，若4人就坐，每人左右两边都有空位，则不同的坐法有种． 7．四个不同的小球放入编号为1，2，3的三个盒子中，则恰有一个空盒的放法共有种（用数字作答）． 8．书架上原来并排放着5本不同的书，现要再插入3本不同的书，那么不同的
插法共有种． 三．解答题（共8小题） 9．一批零件有9个合格品，3个不合格品，组装机器时，从中任取一个零件，若取出不合格品不再放回，求在取得合格品前已取出的不合格品数的分布列10．已知展开式的前三项系数成等差数列． （1）求n的值； （2）求展开式中二项式系数最大的项； （3）求展开式中系数最大的项． 11．设f（x）=（x2+x﹣1）9（2x+1）6，试求f（x）的展开式中： （1）所有项的系数和； （2）所有偶次项的系数和及所有奇次项的系数和． 12．求（x2+﹣2）5的展开式中的常数项． 13．求值C n5﹣n+C n+19﹣n． 14．3名男生，4名女生，按照不同的要求排队，求不同的排队方案的种数．（1）选5名同学排成一行； （2）全体站成一排，其中甲只能在中间或两端； （3）全体站成一排，其中甲、乙必须在两端； （4）全体站成一排，其中甲不在最左端，乙不在最右端； （5）全体站成一排，男、女各站在一起； （6）全体站成一排，男生必须排在一起； （7）全体站成一排，男生不能排在一起； （8）全体站成一排，男、女生各不相邻； （9）全体站成一排，甲、乙中间必须有2人； （10）全体站成一排，甲必须在乙的右边； （11）全体站成一排，甲、乙、丙三人自左向右顺序不变； （12）排成前后两排，前排3人，后排4人． 15．用1、2、3、4、5、6共6个数字，按要求组成无重复数字的自然数（用排列数表示）．
排列与组合 一、教学目标 1、知识传授目标：正确理解和掌握加法原理和乘法原理 2、能力培养目标：能准确地应用它们分析和解决一些简单的问题 3、思想教育目标：发展学生的思维能力，培养学生分析问题和解决问题的能力 二、教材分析 1.重点：加法原理，乘法原理。解决方法：利用简单的举例得到一般的结论． 2.难点：加法原理，乘法原理的区分。解决方法：运用对比的方法比较它们的异同． 三、活动设计 1.活动：思考，讨论，对比，练习． 2.教具：多媒体课件． 四、教学过程正 1．新课导入 随着社会发展，先进技术，使得各种问题解决方法多样化，高标准严要求，使得商品生产工序复杂化，解决一件事常常有多种方法完成，或几个过程才能完成。排列组合这一章都是讨论简单的计数问题，而排列、组合的基础就是基本原理，用好基本原理是排列组合的关键．
2．新课 我们先看下面两个问题． (l)从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船．一天中，火车有4班，汽车有 2班，轮船有 3班，问一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法？ 板书：图 因为一天中乘火车有4种走法，乘汽车有2种走法，乘轮船有3种走法，每一种走法都可以从甲地到达乙地，因此，一天中乘坐这些交通工具从甲地到乙地共有 4十2十3=9种不同的走法．一般地，有如下原理： 加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有m n种不同的方法．那么完成这件事共有N＝m1十m2十…十m n种不同的方法． (2) 我们再看下面的问题： 由A村去B村的道路有3条，由B村去C村的道路有2条．从A 村经B村去C村，共有多少种不同的走法？ 板书：图 这里，从A村到B村有3种不同的走法，按这3种走法中的每一
高考数学轻松搞定排列组合难题二十一种方法 排列组合问题联系实际生动有趣，但题型多样，思路灵活，因此解决排列组合问题，首先要认真审题，弄清楚是排列问题、组合问题还是排列与组合综合问题；其次要抓住问题的本质特征，采用合理恰当的方法来处理。 教学目标 1.进一步理解和应用分步计数原理和分类计数原理。 2.掌握解决排列组合问题的常用策略;能运用解题策略解决简单的综合应用题。提高学生解决问题分析问题的能力 3.学会应用数学思想和方法解决排列组合问题. 复习巩固 1.分类计数原理(加法原理) 完成一件事，有n类办法，在第1类办法中有 m种不同的方法，在第2类 1 办法中有 m种不同的方法，…，在第n类办法中有n m种不同的方法，那么2 完成这件事共有： 种不同的方法． 2.分步计数原理（乘法原理） 完成一件事，需要分成n个步骤，做第1步有 m种不同的方法，做第2步 1 有 m种不同的方法，…，做第n步有n m种不同的方法，那么完成这件事共2 有： 种不同的方法． 3.分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件． 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素. 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排, 两个位置.
排列组合与二项式定理知识点 １．计数原理知识点 ①乘法原理：N=n1·n2·n3·…nM (分步) ②加法原理：N=n1+n2+n3+…+nM (分类) ２．排列（有序）与组合（无序） Anm=n(n－1)(n－2)(n－3)…(n－m+1)=n!/(n-m)! Ann =n! Cnm = n!/(n-m)!m! Cnm= Cnn－m Cnm＋Cnm＋1= Cn+1m+1 k?k!=(k+1)!－k! ３．排列组合混合题的解题原则：先选后排，先分再排 排列组合题的主要解题方法：优先法：以元素为主，应先满足特殊元素的要求，再考虑其他元素. 以位置为主考虑，即先满足特殊位置的要求，再考虑其他位置. 捆绑法（集团元素法，把某些必须在一起的元素视为一个整体考虑） 插空法（解决相间问题）间接法和去杂法等等 在求解排列与组合应用问题时，应注意： (1)把具体问题转化或归结为排列或组合问题； (2)通过分析确定运用分类计数原理还是分步计数原理； (3)分析题目条件，避免“选取”时重复和遗漏； (4)列出式子计算和作答. 经常运用的数学思想是： ①分类讨论思想；②转化思想；③对称思想. ４．二项式定理知识点： ①(a+b)n=Cn0ax+Cn1an－1b1+ Cn2an－2b2+ Cn3an－3b3+…+ Cnran－rbr+-…+ Cn n－1abn－1+ Cnnbn 特别地：(1+x)n=1+Cn1x+Cn2x2+…+Cnrxr+…+Cnnxn ②主要性质和主要结论：对称性Cnm=Cnn－m 最大二项式系数在中间。（要注意n为奇数还是偶数，答案是中间一项还是中间两项） 所有二项式系数的和：Cn０+Cn1+Cn2+ Cn3+ Cn4+…+Cnr+…+Cnn=2n 奇数项二项式系数的和＝偶数项而是系数的和 Cn０+Cn２+Cn４+ Cn６+ Cn８+…＝Cn１+Cn３+Cn５+ Cn７+ Cn９+…=2n -1 ③通项为第r+1项：Tr+1= Cnran－rbr 作用：处理与指定项、特定项、常数项、有理项等有关问题。 5.二项式定理的应用：解决有关近似计算、整除问题，运用二项展开式定理并且结合放缩法证明与指数有关的不等式。 6.注意二项式系数与项的系数（字母项的系数，指定项的系数等，指运算结果的系数）的区别，在求某几项的系数的和时注意赋值法的应用。
高中数学:排列与组合练习 1．(昆明质检)互不相同的5盆菊花,其中2盆为白色,2盆为黄色,1盆为红色,先要摆成一排,要求红色菊花摆放在正中间,白色菊花不相邻,黄色菊花也不相邻,共有摆放方法(D) A．A55种B．A22种 C．A24A22种D．C12C12A22A22种 解析:红色菊花摆放在正中间,白色菊花不相邻,黄色菊花也不相邻,即红色菊花两边各一盆白色菊花,一盆黄色菊花,共有C12C12A22A22种摆放方法． 2．(广州测试)某学校获得5个高校自主招生推荐名额,其中甲大学2个,乙大学2个,丙大学1个,并且甲大学和乙大学都要求必须有男生参加,学校通过选拔定下3男2女共5个推荐对象,则不同的推荐方法共有(B) A．36种B．24种 C．22种D．20种 解析:根据题意,分两种情况讨论:第一种,3名男生每个大学各推荐1人,2名女生分别推荐给甲大学和乙大学,共有A33A22＝12种推荐方法；第二种,将3名男生分成两组分别推荐给甲大学和乙大学,共有C23A22A22＝12种推荐方法．故共有24种推荐方法,选B. 3．(广东珠海模拟)将5个不同的球放入4个不同的盒子中,每个盒子至少放一个球,则不同放法共有(C) A．480种B．360种 C．240种D．120种 解析:根据题意,将5个不同的球放入4个不同的盒子中,每个盒子至少放一个球,则必须有2个小球放入1个盒子,其余的小球各单独放入一个盒子,分2步进行分析:①先将5个小球分成4组,有C25＝10种分法；②将分好的4组全排列,放入4个盒子,有A44＝24种情况,则不同放法有10×24＝240种．故选C. 4．某小区有排成一排的7个车位,现有3辆不同型号的车需要停放,如果要求剩余的4个车位连在一起,那么不同的停放方法的种数为(C) A．16 B．18
高中数学排列组合公式大全_高中数学排列组合重点知识 1.排列及计算公式 从n个不同元素中，任取mm≤n个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出mm≤n个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 pn,m表示. pn,m=nn-1n-2……n-m+1= n!/n-m!规定0!=1. 2.组合及计算公式 从n个不同元素中，任取mm≤n个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出mm≤n个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号 cn,m 表示. cn,m=pn,m/m!=n!/n-m!*m!;cn,m=cn,n-m; 3.其他排列与组合公式 从n个元素中取出r个元素的循环排列数=pn,r/r=n!/rn-r!. n个元素被分成k类，每类的个数分别是n1,n2,...nk这n个元素的全排列数为 n!/n1!*n2!*...*nk!. k类元素,每类的个数无限,从中取出m个元素的组合数为cm+k-1,m. 排列Pnmn为下标，m为上标 Pnm=n×n-1....n-m+1;Pnm=n!/n-m!注：!是阶乘符号;Pnn两个n分别为上标和下标=n!;0!=1;Pn1n为下标1为上标=n 组合Cnmn为下标，m为上标 Cnm=Pnm/Pmm ;Cnm=n!/m!n-m!;Cnn两个n分别为上标和下标 =1 ;Cn1n为下标1为上标=n;Cnm=Cnn-m 加法乘法两原理，贯穿始终的法则。与序无关是组合，要求有序是排列。 两个公式两性质，两种思想和方法。归纳出排列组合，应用问题须转化。 排列组合在一起，先选后排是常理。特殊元素和位置，首先注意多考虑。
高中数学排列与组合 （一）典型分类讲解 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排, 先排末位共有1 3C 然后排首位共有1 4C 最后排其它位置共有 34A 由分步计数原理得1 1 3 434 288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？ 二.相邻元素捆绑策略 例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元 素内部进行自排。由分步计数原理可得共有 522522480A A A =种不同的排法 练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略 例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？ 解:分两步进行第一步排2个相声和3个独唱共有55A 种， 第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种 46 A 不同的方法,由分步计数原理,节目的不同顺序共有54 56A A 种 练习题：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为 30 四.定序问题倍缩空位插入策略 例4. 7人排队,其中甲乙丙3人顺序一定共有多少不同的排法 解:(倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总排列数除以这几个元素 之间的全排列数,则共有不同排法种数是： 73 73/A A (空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有 47 A 种方法，其余的三个位置甲乙丙共有 1种坐法，则共有4 7A 种方法。 思考:可以先让甲乙丙就坐吗? （插入法)先排甲乙丙三个人,共有1种排法,再把其余4四人依次插入共有 方法 练习题:10人身高各不相等,排成前后排，每排5人,要求从左至右身高逐渐增加，共有多少排法？ 5 10C 五.重排问题求幂策略 例5.把6名实习生分配到7个车间实习,共有多少种不同的分法 解:完成此事共分六步:把第一名实习生分配到车间有 7 种分法.把第二名实习生分配到车间也有7种分依此类推,由分步计数原 理共有6 7种不同的排法 练习题： 1． 某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插 法的种数为 42 4 4 3 允许重复的排列问题的特点是以元素为研究对象，元素不受位置的约束，可以逐一安排各个元素的位置，一般地n 不同的元素没有限制地安排在m 个位置上的排列数为n m 种
~ 高考数学排列组合难题解决方法 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1m 种不同的方法，在第2类办法中有2m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有： 种不同的方法． 2.分步计数原理（乘法原理） 完成一件事，需要分成n 个步骤，做第1步有1m 种不同的方法，做第2 步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有： 种不同的方法． 3.分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件． 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。 … 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素. 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排, 两个位置 . 先排末位共有1 3C 然后排首位共有1 4C / 最后排其它位置共有34A 由分步计数原理得113 4 34288C C A = 443
、 练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不 种在两端的花盆里，问有多少不同的种法 二.相邻元素捆绑策略 例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一 个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有522522480A A A 种不同的排法 练习题1.用1,2,3,4,5组成没有重复数字的五位数其中恰有两个偶数夹1, ５在两个奇数之间,这样的五位数有多少个 解：把１,５,２,４当作一个小集团与３排队共有22A 种排法， 再排小集团内部共有2222A A 种排法，由分步计数原理共有222 222A A A 种排法. ： 2.计划展出10幅不同的画,其中1幅水彩画,４幅油画,５幅国画, 排成一行陈列,要求同一 品种的必须连在一起，并且水彩画不在两端，那 么共有陈列方式的种数为254 254A A A 3. 5男生和５女生站成一排照像,男生相邻,女生也相邻的排法有255 255A A A 种 三.不相邻问题插空策略 例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场, 则节目的出场顺序有多少种 （ 解:分两步进行第一步排2个相声和3个独唱共有55A 种，第二步将4舞蹈插 入第一步排好的6个元素中间包含首尾两个空位共有种4 6A 不同的方法, 由分步计数原理,节目的不同顺序共有5456A A 种 小集团排列问题中，先整体后局部，再结合其它策略进行处理。
高中数学排列与组合知识点 排列组合是高中数学教学内容的一个重要组成部分,但由于排列组合极具抽象性,使之成为高中数学课本中教与学的难点.加之高中学生的认知水平和思维能力在一定程度上受到限制,所以在解题中经常出现错误.以下本人搜集整合了高中数学排列与组合相关知识点，希望可以帮助大家更好的学习这些知识。 高中数学排列与组合知识点汇编如下： 一、排列 1 定义 (1)从n个不同元素中取出m个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一排列。 (2)从n个不同元素中取出m个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，记为 Amn. 2 排列数的公式与性质 (1)排列数的公式： Amn=n(n-1)(n-2)…(n-m+1) 特例：当m=n时， Amn=n!=n(n-1)(n-2)…×3×2×1 规定：0!=1 二、组合
1 定义 (1)从n个不同元素中取出 m个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合 (2)从n个不同元素中取出m个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数，用符号 Cmn表示。 2 比较与鉴别 由排列与组合的定义知，获得一个排列需要“取出元素”和“对取出元素按一定顺序排成一列”两个过程，而获得一个组合只需要“取出元素”，不管怎样的顺序并成一组这一个步骤。 排列与组合的区别在于组合仅与选取的元素有关，而排列不仅与选取的元素有关，而且还与取出元素的顺序有关。因此，所给问题是否与取出元素的顺序有关，是判断这一问题是排列问题还是组合问题的理论依据。 三、排列组合与二项式定理知识点 1.计数原理知识点 ①乘法原理：N=n1·n2·n3·…nM (分步) ②加法原理： N=n1+n2+n3+…+nM (分类) 2. 排列(有序)与组合(无序)
高考数学排列组合难题解决方法 1. 分类计数原理（加法原理） 完成一件事，有类办法，在第1类办法中有种不同的方法，在第2类办法中有种不同的方法，…，在第类办法中有种不同的方法，那么完成这件事共有： N = mi + m2 j + m n 种不同的方法. 2. 分步计数原理（乘法原理） 完成一件事，需要分成个步骤，做第1步有种不同的方法，做第2步有种不同的方法，…，做第步有种不同的方法，那么完成这件事共有： N = mi江m2汇川X m n 种不同的方法. 3. 分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件. 解决排列组合综合性问题的一般过程如下： 1. 认真审题弄清要做什么事 2. 怎样做才能完成所要做的事，即采取分步还是分类，或是分步与分类同时进 行,确定分多少步及多少类。 3. 确定每一步或每一类是排列问题（有序）还是组合（无序）问题,元素总数是多少及取出多少个元素. 4. 解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略
解：由于末位和首位有特殊要求，应该优先安排，以免不合要求的元素占了这两个位置. 先排末位共有 然后排首位共有 最后排其它位置共有 由分步计数原理得 练习题:7种不同的花种在排成一列的xx，若两种葵花不种在中间，也不种在两端的xx，问有多少不同的种法？ 二.相邻元素捆绑策略 例2. 7人站成一排，其中甲乙相邻且丙丁相邻，共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有种不同的排法 练习题1.用1,2,3,4,5 组成没有重复数字的五位数其中恰有两个偶数夹1, 5在两个奇数之间，这样的五位数有多少个？ 解：把1，5，2，4当作一个小集团与3排队共有种排法，再排小集团内部共有种排法，由分步计数原理共有种排法. 1524
高中数学竞赛标准讲义----排列组合与概率 一、基础知识 1．加法原理：做一件事有n 类办法，在第1类办法中有m 1种不同的方法，在第2类办法中有m 2种不同的方法，……，在第n 类办法中有m n 种不同的方法，那么完成这件事一共有N=m 1+m 2+…+m n 种不同的方法。 2．乘法原理：做一件事，完成它需要分n 个步骤，第1步有m 1种不同的方法，第2步有m 2种不同的方法，……，第n 步有m n 种不同的方法，那么完成这件事共有N=m 1×m 2×…×m n 种不同的方法。 3．排列与排列数：从n 个不同元素中，任取m(m ≤n)个元素，按照一定顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列，从n 个不同元素中取出m 个(m ≤n)元素的所有排列个数，叫做从n 个不同元素中取出m 个元素的排列数，用m n A 表示，m n A =n(n-1)…(n-m+1)= )! (! m n n -,其中m,n ∈N,m ≤n, 注：一般地0n A =1，0！=1，n n A =n!。 4．N 个不同元素的圆周排列数为n A n n =(n-1)!。 5．组合与组合数：一般地，从n 个不同元素中，任取m(m ≤n)个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合，即从n 个不同元素中不计顺序地取出m 个构成原集合的一个子集。从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数，用m n C 表示： .)! (!! !)1()1(m n m n m m n n n C m n -=+--= 6．组合数的基本性质：（1）m n n m n C C -=；（2）11--+=n n m n m n C C C ；（3）k n k n C C k n =--11；（4）n n k k n n n n n C C C C 20 10==+++∑= ；（5）111++++-=+++k m k k m k k k k k C C C C ；（6）k n m n m k k n C C C --=。 7．定理1：不定方程x 1+x 2+…+x n =r 的正整数解的个数为11--n r C 。 [证明]将r 个相同的小球装入n 个不同的盒子的装法构成的集合为A ，不定方程x 1+x 2+…+x n =r 的正整数解构成的集合为B ，A 的每个装法对应B 的唯一一个解，因而构成映射，不同的装法对应的解也不同，因此为单射。反之B 中每一个解(x 1,x 2,…,x n ),将x i 作为第i 个盒子中球的个数，i=1,2,…,n ，便得到A 的一个装法，因此为满射，所以是一一映射，将r 个小球从左到右排成一列，每种装法相当于从r-1个空格中选n-1个，将球分n 份，共有11--n r C 种。故定理得证。 推论1 不定方程x 1+x 2+…+x n =r 的非负整数解的个数为.1r r n C -+
高一数学排列与组合知识点汇总 高一数学排列与组合知识点(一) 排列组合与二项式定理知识点 1.计数原理知识点 ①乘法原理：N=n1·n2·n3·…nM(分步)②加法原理： N=n1+n2+n3+…+nM(分类) 2.排列(有序)与组合(无序) Anm=n(n-1)(n-2)(n-3)-…(n-m+1)=n!/(n-m)!Ann=n! Cnm=n!/(n-m)!m! Cnm=Cnn-mCnm+Cnm+1=Cn+1m+1k?k!=(k+1)!-k! 3.排列组合混合题的解题原则：先选后排，先分再排 排列组合题的主要解题方法：优先法：以元素为主，应先满足特殊元素的要求，再考虑其他元素.以位置为主考虑，即先满足特殊位置的要求，再考虑其他位置. 捆绑法(集团元素法，把某些必须在一起的元素视为一个整体考虑) 插空法(解决相间问题)间接法和去杂法等等 在求解排列与组合应用问题时，应注意： (1)把具体问题转化或归结为排列或组合问题; (2)通过分析确定运用分类计数原理还是分步计数原理; (3)分析题目条件，避免“选取”时重复和遗漏; (4)列出式子计算和作答.
经常运用的数学思想是： ①分类讨论思想;②转化思想;③对称思想. 4.二项式定理知识点： ①(a+b)n=Cn0ax+Cn1an-1b1+Cn2an-2b2+Cn3an-3b3+…+Cnran- rbr+-…+Cnn-1abn-1+Cnnbn 特别地：(1+x)n=1+Cn1x+Cn2x2+…+Cnrxr+…+Cnnxn ②主要性质和主要结论：对称性Cnm=Cnn-m 最大二项式系数在中间。(要注意n为奇数还是偶数，答案是中 间一项还是中间两项) 所有二项式系数的和：Cn0+Cn1+Cn2+Cn3+Cn4+…+Cnr+…+Cnn=2n 奇数项二项式系数的和=偶数项而是系数的和 Cn0+Cn2+Cn4+Cn6+Cn8+…=Cn1+Cn3+Cn5+Cn7+Cn9+…=2n-1 ③通项为第r+1项：Tr+1=Cnran-rbr作用：处理与指定项、特 定项、常数项、有理项等有关问题。 5.二项式定理的应用：解决有关近似计算、整除问题，运用二项展开式定理并且结合放缩法证明与指数有关的不等式。 6.注意二项式系数与项的系数(字母项的系数，指定项的系数等，指运算结果的系数)的区别，在求某几项的系数的和时注意赋值法的 应用。 高一数学排列与组合知识点(二) 一、排列 1定义 (1)从n个不同元素中取出m个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一排列。