1、第一章：计数原理第一章：计数原理1.1：分类加法计数原理与分步乘法计数原理：分类加法计数原理与分步乘法计数原理1.2：排列与组合：排列与组合1.3：二项式定理：二项式定理1、分类加法计数原理、分类加法计数原理：完成一件事，有：完成一件事，有n类办法，在类办法，在第第1类办法中有类办法中有m1种不同的方法种不同的方法,在第在第2类办法中有类办法中有m2种不同的方法种不同的方法在第在第n类办法中类办法中有有m mn n种不同的方法种不同的方法.那么完成这件事共有那么完成这件事共有 种不同的方种不同的方法法.12nNmmm2 2、分步乘法计数原理、分步乘法计数原理：完成一件事，需要分成完成一件事，需
2、要分成n n个步个步骤，做第骤，做第1 1步有步有m m1 1种不同的方法种不同的方法,做第做第2 2步有步有m m2 2种不同的种不同的方法方法，做第，做第n n步有步有m mn n种不同的方法种不同的方法.那么完成这件那么完成这件事共有事共有 种不同的方法种不同的方法.12nNmmm两个计数原理两个计数原理分类计数原理分类计数原理 分步计数原理分步计数原理完成一件事，共有完成一件事，共有n类类办法，关键词办法，关键词“分类分类”区别区别1完成一件事，共分完成一件事，共分n个个步骤，关键词步骤，关键词“分步分步”区别区别2区别区别3每类办法都能独立地完成每类办法都能独立地完成这件事情，它是独
3、立的、这件事情，它是独立的、一次的、且每次得到的是一次的、且每次得到的是最后结果，最后结果，只须一种方法只须一种方法就可完成这件事就可完成这件事。每一步得到的只是中间结果，每一步得到的只是中间结果，任何一步都不能独立完成这件任何一步都不能独立完成这件事，缺少任何一步也不能完成事，缺少任何一步也不能完成这件事，这件事，只有各个步骤都完成只有各个步骤都完成了，才能完成这件事了，才能完成这件事。各类办法是互相独立的。各类办法是互相独立的。各步之间是互相关联的。各步之间是互相关联的。类类独立，不重不漏；类类独立，不重不漏；步步关联，步骤完整步步关联，步骤完整。经典例子来区分 现有5幅不同的国画，2幅不
4、同的油画，7幅不同的水彩画。（1）从中任选一幅画布置房间，有几种不同的选法？（2）从国画 油画 水彩画里各选一幅布置房间，有几种不同的选法？（3）从这些画中选两幅不同种类的画布置房间，有几种不同的选法？解析（1）分类原理：5（国画）+2（油画）+7（水彩）=14（2）分步原理：5（国画）2（油画）7（水彩）=70（3）先分类再分步：第一类：一幅国画一幅油画 52=10 第二类：一幅国画一幅水彩画 57=35 第三类：一幅油画一幅水彩画 27=14 所以，共有 10+35+14=59 种不同的方案多面手问题例题（成才P72 例四）某外语组有9人，每人至少会英语和日语中的一门，其中7人会英语，3人
5、会日语，从中选出会英语和日语的各一人，有多少种不同的选法。首先算出多面手的个数以多面手的选择情况分类多面手+只会英语多面手+只会日文不含多面手6种2种2X6=12共6+2+12=20种假设现有A，B两名多面手，会英语的有A，B，a，b，c；会日语的有A，B，d，e，fABabcABdef对于会英语的A，B，a，b，c它们各有五种选择：A，B，d，e，f。可是A选择A，B选择B是不符合挑两个人的条件的，所以这两种情况不可取。还有A选择B和B选择A重复。所以5*5-3=22会A的乘于会B的-（n+（n-1）+1）直接法：在处理有限制条件的排列，优先排特殊元素，后再排其他元素。定元定位优先排间接法：
6、先不考虑特殊元素，而列出所有元素的全排列数，从中减去不满足特殊元素要求的排列数。注意：不重不漏 成才后翻P56 T13 六个人从左到右排成一行，最左端只能排甲或已，最右端不能排甲，则不同的排法？直接法：最左端排甲，则剩下的随便排。最左边排乙，则甲有四个位置选择，剩 下的随便排 共216种。间接法：全排列数-右端站甲-最左端站的不是甲乙+右端站甲左端不站乙 共216种。排列与组合排列：一般地，从n个不同元素中取出m(mn)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。排列数：从n个不同元素中取出m(mn)个元素的所有不同排列的个数叫做从n个不同元素中取出m个元素的排
7、列数。用符号 表示.mnA排列数公式：!121mnnmnnnnAmn .,*nmNmn 并并且且排列数公式的推导 我们可以把排序过程分解为m个程序：第一个程序决定排于第一位的数字，第二个程序决定排于第二位的数字.第m个程序决定排于第m位的数字。在进行第一个程序时，有n个数字可供选择，因此有n种选法。在进行第二个程序时，由於在前一程序已选定了一个数字，现在可供选择的数字只剩下n-1个，因此有n-1种选法。在进行第三个程序时，由於在前一程序已选定了一个数字，现在可供选择的数字只剩下n-2个，因此有n-2种选法。按照这样直至第m个程序，这时可供选择的数字只剩下n-m+1个，因此只有n-m+1种选择。
8、由於以上各程序是各自独立的，我们可以运用分步乘法计数原理求得答案为n(n-1)(n-2).(n-m+1)1()2)(1(mnnnnAmn即排列数的另一个公式 阶乘：一个正整数的阶乘是所有小于及等于该数的正整数的积，并且规定0的阶乘为1。自然数n的阶乘写作n!。亦即n!=123.n)!(!)!(!12)1)(12)1()2)(1()1()2)(1(mnnAmnnmnmnmnnnnmnnnnmn 排列数的计算 化简:解:nnnAAAA 33221132!)!1(!)1(nnnnnnAnn1)!1(!)!1(!3!4!2312 nnn！原式解方程 解方程：解:由 得 化简得 ，解得19843xxAA
9、19843xxAA)!10(!94)!8(83xx！)!8)(9)(10(!894)!8(!83xxxx078192xx13,621xx6,91,8xxx原方程的解是且解不等式 解不等式:解：2886xxAA882,02,8,127,08419,)!10(!86!88,6*2288xNxxxxxxxxxAAxx得由及，又解之得化简得）（！得由组合组合：一般地，从n个不同元素中取出m(mn)个元素合成一组，叫做从n个不同元素中取出m个元素的一个组合。组合数：从n个不同元素中取出m(mn)个元素的所有不同组合的个数叫做从n个不同元素中取出m个元素的组合数。用符号 表示.mnC组合数公式：!121m
10、nmnmmnnnnCmn .,*nmNmn 并并且且组合数性质：mnnmnCC mnmnmnCCC11 判断一个具体问题是否为组合问题判断一个具体问题是否为组合问题,关键是看取关键是看取出的元素是否与顺序有关出的元素是否与顺序有关,有关就是排列有关就是排列,无关便无关便是组合是组合.判断时要弄清楚判断时要弄清楚“事件是什么事件是什么”.组合数的计算 算一算：求m的值 解：m!(5-m)!/75!-m!(6-m)!/76!=m!(7-m)!/107!(m-21)(m-2)=0 m=21（舍去）或m=2 m=2mmmCCC7651017171排列组合应用题的常用方法1 1对有约束条件的排列问题，应
11、注意如下类型：对有约束条件的排列问题，应注意如下类型：某些元素某些元素不能在不能在或必须排列或必须排列在在某一位置；某些元素要求某一位置；某些元素要求连连排排（即必须相邻）；某些元素要求（即必须相邻）；某些元素要求分离分离（即不能相邻）；（即不能相邻）；2 2基本的解题方法：基本的解题方法：（）有特殊元素或特殊位置的排列问题，通常是先排特殊元（）有特殊元素或特殊位置的排列问题，通常是先排特殊元素或特殊位置，称为优先处理特殊元素（位置）法（优先法）；素或特殊位置，称为优先处理特殊元素（位置）法（优先法）；特殊元素特殊元素,特殊位置优先安排策略特殊位置优先安排策略（）某些元素要求必须相邻时，可以先
12、将这些元素看作一个元（）某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内部排列，这种方法素，与其他元素排列后，再考虑相邻元素的内部排列，这种方法称为称为“捆绑法捆绑法”；相邻问题捆绑处理的策略相邻问题捆绑处理的策略（）某些元素不相邻排列时，可以先排其他元素，再将这些（）某些元素不相邻排列时，可以先排其他元素，再将这些不相邻元素插入空挡，这种方法称为不相邻元素插入空挡，这种方法称为“插空法插空法”；不相邻问题不相邻问题插空处理的策略插空处理的策略习题1.7人排一列，若7人中甲乙丙相邻，另外4人也相邻，共有几种排法。习题2.7人排一列，若甲在中间，乙丙相邻
13、，共有几种排法。相邻问题，常用“捆绑法”习题3.7人排一列，若7人中甲，乙相邻，但都不与丙相邻，共有几种不同排法？960254422AAA不相邻问题，常用“插空法”分组问题问题问题1：3个不同的小球分成两堆，有多少种分法？个不同的小球分成两堆，有多少种分法？问题问题2：4个不同的小球分成两堆，有多少种分法？个不同的小球分成两堆，有多少种分法？问题问题3：6个不同的小球分成个不同的小球分成3堆，有多少种分法？堆，有多少种分法？平均分成平均分成m组要除以组要除以mmA2131C C2231424122C CC CA+2221112346422165362323CCCCCCCCAA+C C+分配问题
14、分堆问题的变式问题问题1变式变式：3个不同的小球放进两个不同的小球放进两个盒子，每个盒子至少一个，有多个盒子，每个盒子至少一个，有多少种放法？少种放法？问题问题3变式变式：三名教师教六个班的课，每人至少教一个班，：三名教师教六个班的课，每人至少教一个班，每班只配一名教师，则分配方案共有多少种？每班只配一名教师，则分配方案共有多少种？问题问题2变式变式：4本不同的书分给两个同学，本不同的书分给两个同学，每人至少一本，有多少种放法？每人至少一本，有多少种放法？212312C C A223124241222C CC CAA+222111234364221653632323C C CC CC C CA
15、AA+C+C+多个分给少个时，采用多个分给少个时，采用先分组先分组再分配再分配的策略的策略例例1、从从6个学校中选出个学校中选出30名学生参加数学竞赛名学生参加数学竞赛,每每校至少有校至少有1人人,这样有几种名额分配方法？这样有几种名额分配方法？分析分析:问题相当于把个问题相当于把个30相同球放入相同球放入6个不同盒子个不同盒子(盒盒子不能空的子不能空的)有几种放法有几种放法?这类问题可用这类问题可用“隔板法隔板法”处处理理.解解:采用采用“隔板法隔板法”得得:5294095C分配问题隔板法类似练习：类似练习：1、将、将8个学生干部的培训指标分配给个学生干部的培训指标分配给5个不同的班级，个不
16、同的班级，共有多少种不同的分配方法？共有多少种不同的分配方法？2、从一楼到二楼的楼梯有、从一楼到二楼的楼梯有17级，上楼时可以一步走级，上楼时可以一步走一级，也可以一步走两级，若要求一级，也可以一步走两级，若要求11步走完，则有步走完，则有多少种不同的走法？多少种不同的走法？3、方程、方程x+y+z=12的非负整数解的个数为多少？的非负整数解的个数为多少？正整数解的个数呢？正整数解的个数呢？122rrnnnnnn1+C x+C x+C x+C xn(1+x)2、一般地，对于一般地，对于n N*有有011222()nnnnnnnrnrrnnnnabC aC abC abC abC b 1、二项式
17、定理、二项式定理:通项公式通项公式T Tr+1r+1=rrn-rnC ab1.3：二项式定理 一般地，一般地，展开式的二项式系数展开式的二项式系数 有如下性质：有如下性质：nba)(（1 1）nnnnCCC,10mnnmnCC （2 2）（4 4）mnmnmnCCC11nnnnnCCC210 （3 3）当）当n n为偶数时，为偶数时，最大最大 当当n n为奇数时，为奇数时，=且最大且最大 2Cnn21Cnn21Cnn（对称性）（对称性）1.3：二项式定理02413512nnnnnnnCCCCCC奇数项二项式系数和偶数项二项式系数和：例例1.在在(1+x)3+(1+x)4+（1+x）50的展开式
18、的展开式中，求含中，求含x3项的系数。项的系数。解法一：解法一：分析：可将此式看成首项为（分析：可将此式看成首项为（1+x)3,公比为（公比为（1+x）的等）的等比数列，比数列，原式=要在展开式中取得x3项，必须在（1+x）51取得x4项故其原式的展开式中x3的系数为C514解法二：4513503433CCCC二项式定理的应用特定项nxx3221若 展开式中的偶数项系数和为-256，求n例2n=9二项式定理的应用奇偶项解：（1）求a1+a2+a3+a4+a5+a6+a7+a8 设f（x）=(3x-1)8 分别赋予x=1，0 a1+a2+a3+a4+a5+a6+a7+a8=f(1)-f(0)例：
19、(3x-1)8=a0+a1x+a2x2+a3x3+a4x4+a5x5+a6x6+a7x7+a8x8变式：即对（3x+1）8进行赋值x=1可得二项式定理的应用赋值法（1）求a1+a2+a3+a4+a5+a6+a7+a8变式：求|a0|+|a1|+|a2|+|a3|+|a4|+|a5|+|a6|+|a7|+|a8|（2）求a0+a2+a4+a6+a8；解：（2）设f（x）=(3x-1)8 分别赋予x=1，-1 a0+a2+a4+a6+a8=f(1)+f(-1)/2(3x-1)8=a0+a1x+a2x2+a3x3+a4x4+a5x5+a6x6+a7x7+a8x8一般来说多项式f（x）各项系数和为f（1）奇数项系数和为1/2f(1)-f(-1)偶数项系数和为1/2f(1)+f(-1)二项式定理的应用赋值法求值、等式与不等式证明问题1055845635425215222221)1(CCCCC求值：（3 3）求证：）求证：),1(221321NnnnCCCCnnnnnn（2）求证：）求证：5555+1能被能被8整除；整除；
