排列组合典型类型题总结.doc

排列组合

一.相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组，当作一个大元素参与排列.

例1.五人并排站成一排，如果必须相邻且在的右边，那么不同的排法种数有
A、60种 B、48种 C、36种 D、24种

二.相离问题插空法:元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素的空位和两端.
例2.七人并排站成一行，如果甲乙两个必须不相邻，那么不同的排法种数是
A、1440种 B、3600种 C、4820种 D、4800种

元素相同问题隔板策略

将n个相同的元素分成m份（n，m为正整数）,每份至少一个元素,可以用m-1块隔板，插入n个元素排成一排的n-1个空隙中，所有分法数为

例3 某校召开学生会议，要将10个学生代表名额，分配到某年级的6个班中，若每班至少1个名额，又有多少种不同分法？

例4把20个相同的球全部装入编号分别为1，2，3的三个盒子中，要求每个盒子中的球数不小于其编号数，则共有 种不同的放法。

三.特殊元素或特殊位置优限法：优先解决带限制条件的元素或位置，或说“先解决特殊元素或特殊位置”

例5.1名老师和4名获奖同学排成一排照相留念，若老师不站两端则有不同的排法有多少种？

四.分组分配：
1基本的分组的问题

例4 六本不同的书，分为三组，求在下列条件下各有多少种不同的分配方法？
(1)每组两本.
(2)一组一本，一组二本，一组三本.
(3)一组四本，另外两组各一本.

2.基本的分配的问题
(1)定向分配问题
例5 六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？
(1) 甲两本、乙两本、丙两本.
(2) 甲一本、乙两本、丙三本.
(3) 甲四本、乙一本、丙一本.

(2)不定向分配问题
例6六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？
(1) 每人两本.
(2) 一人一本、一人两本、一人三本.
(3) 一人四本、一人一本、一人一本.

例7 六本不同的书，分给甲、乙、丙三人，每人至少一本，有多少种分法？

3.分配问题的变形问题
例8 四个不同的小球放入编号为1，2，3，4的四个盒子中，恰有一个空盒的放法有多少种？

例9有甲、乙、丙三项任务，甲需2人承担，乙、丙各需1人承担，从10人中选派4人承担这三项任务，不同的选法有多少种？

例10设集合A={1，2，3，4}，B={6，7，8}，A为定义域，B为值域，则从集合A到集合B的不同的函数有多少个？

五.相同元素隔板法及应用:
情形1：将n件相同的物品或（名额）分配给m个（或位置），允许若干个人或（位置）为空。将n件物品和m-1个隔板排成一排，占n+m-1个位置，从n+m-1个位置选m-1位置放隔板，有种。
情形2：将n件相同的物品或（名额）分配给m个（或位置），每个位置必须有物品，有种。

例11. 把20个相同的球放入4个不同的盒子，每个盒子都不空，有多少种不同方法？

把20个相同的球放入4个不同的盒子，每个盒子至少有3个小球，有多少种不同方法？

把20个相同的球放入编号为2，3，4，5的4个盒子，每个盒子的小球数不少于编号数，有多少种不同方法？

把20个相同的球放入4个不同的盒子，盒子可以空，有多少种不同方法？
1.指标分配问题。
例12、某校召开学生会议，要将10个学生代表名额，分配到某年级的6个班中，若每班至少1个名额，又有多少种不同分法？

2.求n项展开式的项数。
例13、求展开式中共有多少项？

例14、求方程++…+=7的正整数解的个数。

五 至多，至少问题排除法

例15.从4台甲型和5台乙型电视机中任取3台，其中至少要甲型和乙型电视机各一台，则不同的取法共有
A、140种 B、80种 C、70种 D、35种

例16.（1）以正方体的顶点为顶点的四面体共有
A、70种 B、64种 C、58种 D、52种

（2）四面体的顶点和各棱中点共10点，在其中取4个不共面的点，不同的取法共有
A、150种 B、147种 C、144种 D、141种

六. 综合问题先选后排

例17.（1）四个不同球放入编号为1，2，3，4的四个盒中，则恰有一个空盒的放法有多少种？

（2）9名乒乓球运动员，其中男5名，女4名，现在要进行混合双打训练，有多少种不同的分组方法？

七 .对等问题缩倍法:在排列问题中限制某几个元素必须保持一定的顺序，可用缩小倍数的方法.
例19.五人并排站成一排，如果必须站在的右边（可以不相邻）那么不同的排法种数是
A、24种 B、60种 C、90种 D、120种

十.多排问题单排法:把元素排成几排的问题可归结为一排考虑，再分段处理.
例20.（1）6个不同的元素排成前后两排，每排3个元素，那么不同的排法种数是
A、36种 B、120种 C、720种 D、1440种

（2）8个不同的元素排成前后两排，每排4个元素，其中某2个元素要排在前排，某1个元素排在后排，有多少种不同排法？

复杂的排列组合问题

例23 上一个有10级台阶的楼梯，每步可上一级或两级，共有多少种上台阶的方法？

例24 如图1中A，B，C，D为海上四个岛，
要建三座桥，将这四个小岛连接起来，
则不同的建桥方案共有（ ）
A.8种 B.12种 C.16种 D.20种

例25 把20个相同的球全部装入编号分别为1，2，3的三个盒子中，要求每个盒子中的球数不小于其编号数，则共有 种不同的放法。

例27.（1）圆周上有10点，以这些点为端点的弦相交于圆内的交点最多有多少个？