1、排列与组合一、知识回顾1、排列与组合问题是一类特殊的计数问题，它的解决需要用到以下几个基本工具：对应原理； 分类计数原理； 分步计数原理； 容斥原理2、排列与组合问题的求解策略：（1）排除：对有限条件的问题，先从总体考虑，再把不符合条件的所有情况排除（2）分类与分步：有些问题的处理可分成若干类，用加法原理，要注意每两类的交集为空集，所有各类的并集是全集；有些问题的处理分成几个步骤，把各个步骤的方法数相乘，即得总的方法数，这是乘法原理（3）对称思想：两类情形出现的机会均等，可用总数取半得每种情形的方法数（4）插空：某些元素不能相邻或某些元素在特殊位置时可采用插空法即先安排好没有限制条件的元素，然
2、后将有限制条件的元素按要求插入到排好的元素之间（5）捆绑：把相邻的若干特殊元素“捆绑”为一个“大元素”，然后与其它“普通元素”全排列，然后再“松绑”，将这些特殊元素在这些位置上全排列（6）隔板模型：对于将不可辨的球装入可辨的盒子中，求装的方法数，常用隔板模型如将12个完全相同的球排成一列，在它们之间形成的11个缝隙中任意插入3块隔板，把球分成4堆，分别装入4个不同的盒子中的方法数应为，这也就是方程的正整数解的个数3、圆排列（1）从集合的个不同元素中取出个元素按照某种顺序（如逆时针）排成一个圆圈，叫做一个圆排列（或叫环状排列）（2）圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换后仍是
3、同一排列；（iii）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同时，才是不同的圆排列（3）定理：从集合的个元素中取出个不同的元素进行圆排列的圆排列数为4、不尽相异元素的全排列如果个元素中，有个元素相同，又有个元素相同，又有个元素相同（），这个元素全部取出的排列叫做不尽相异的个元素的全排列，它的排列数是.5、可重排列与组合（1）定义：元素可以多次重复出现的集合称为重集，元素出现的次数叫做该元素的重数.一般地，重集可以表示为，其中为中个不同类型的元素，为的重数，是正整数，也可以是.若的重数是，表示中有无限多个.重集的一个排列仍是中的个元素的一个有序摆放；重集的一个组合仍是中的个元
4、素的一个无序选择.（2）重集的排列的个数为.（3）设重集，且的元素个数为则的全排列数为.（4）重集的组合的个数为.（5）设重集，要求至少出现一次的组合的个数为.（6）方程的解有组；方程的解有组.二、例题分析例1、有2n个人参加收发电报培训，每两人结为一对互发互收，有多少种不同的结对方式？例2、在正方体的8个顶点，12条棱的中点，6个面的中心及正方体的中心共27个点中，共线的三点组的个数是多少个？例3、数1447，1005和1231有某些共同点，即每个数都是首位为1的四位数，且每个四位数中恰有两个数字相同，这样的四位数共有多少个？例4、在平面上，顶点的坐标满足，且是整数的三角形有多少个？例5、（
5、1）有8人围圆桌就餐，问有多少种就座方式？如果有两人不愿坐在一起，又有多少种就座方式？（2）4男4女围圆桌交替就座有多少种方式？例6、将个相同的小球，放入个不同的盒子（）（1）有多少种不同的放法？ （2）如果不允许空盒应有多少种不同的放法？例7、如果从1，2，14中，按从小到大的顺序取出，使同时满足：，那么所有符合要求的不同取法有多少种？例8、由数字1，2，3组成n位数(n3)，且在n位数中，1，2，3每一个至少出现1次，问：这样的n位数有多少个？例9、用1，2，3三个数字来构造n位数，但不允许有两个紧挨着的1出现在n位数中，问：能构造出多少个这样的n位数？例10、设一个圆分成S1，S2，Sn
6、共n个扇形，用m种不同的颜色对这n个扇形着色（m3，n3），每一个扇形着一种颜色，相邻扇形着不同颜色，那么，共有多少种不同的着色方法？三、课后练习1、设ABCDEF为正六边形，一只青蛙开始在顶点A处，它每次可随意地跳到相邻两顶点之一若在5次之内跳到D点，则停止跳动；若5次之内不能到达D点，则跳完5次也停止跳动，那么这只青蛙从开始到停止，可能出现的不同跳法共_种2、从1到100的正整数中每次取出不同的2个数，使它们的和大于100，则不同的取法有多少种？3、平面上给定5点，这些点两两间的连线互不平行，又不垂直，也不重合，现从任一点向其余四点两两之间的连线作垂线，则所有这些垂线间的交点数最多是_4、
7、如果：（1）a,b,c,d都属于1,2,3,4；（2）ab,bc,cd,da；(3)a是a,b,c,d中的最小值，那么，可以组成的不同的四位数的个数是_5、（1）10人围圆桌而做，如果甲、乙二人中间相隔4人，有_种坐法（2）圆桌的9个位置上放着9样不同的点心和饮料，6为先生和3为女士共进早餐，3位女士两两不相邻的坐法有多少种？6、由1，2，3，4，5，6这六个数字能组成多少个五位数？又可组成多少个大于34500的五位数？（数字允许重复）7、由4面红旗、3面蓝旗、2面黄旗、5面绿旗可以组成多少种由14面旗子组成的一排彩旗？8、用字母A、B和C组成五个字母的符合，要求在每个符号里，A至多出现2此，B至多出现1次，C至多出现3次，求此类符号的个数.
