GMAT数学之光—排列组合的本质

基本概念

排列组合的本质是“两则基本运算”，即，加法和乘法运算。可以说，所有的排列组合概念均可以通过加法和乘法这两个运算而推理得出。

排列组合的加法原理是：

如果N种方法的每一种都能把某件事做完，则能完成这件事的方法总数即为N。

假设，小明要从北京到上海，他能选择的交通方式是2班飞机和3班火车。那么，小明共有3+2=5种方式可以从北京到上海。

这就是加法原理的使用。之所以把它们加在一起，是因为无论哪一种方式，都能独立地把整件事做完。

排列组合的乘法原理是：

如果一件事需要分成两个步骤完成，第一步有N种方法，第二步有M种方法，则完成这件事的总方法数为N*M种。

假设，小明又要从上海回北京，这次没有直达方式了，都需要先经过南京。如果上海到南京有3班火车且南京到北京有2班飞机，则从北京到上海的总方法数为2*3 = 6。

这就是乘法原理的使用。之所以把它们乘在一起，是因为无论任何一种方式都只做了一个步骤。

理解了这两个基本原理后，我们就可以解锁阶乘的实际意义了。

假设我手里有一个黑盒子，盒子里有六个颜色不同小球。这六个小球，除掉颜色不同之外，没有任何其他的不同。请问，如果随机从盒子中取出一个小球，这个小球有几种可能的颜色呢？

相信大家都不会答错，是6种。

如果再取出一个小球，它有几种可能的颜色呢？

答案是5种。

以此类推，全部拿出来后，六个小球可能的颜色种数为6，5，4，3，2，1。

根据乘法定理，6个球全体的颜色排序为：

6*5*4*3*2*1

实际上，从黑盒子里一个一个取球的过程相当于给本来在黑盒中排序混乱的小球进行重新排序。因此，也可以说，6个小球的全体排列为：

6*5*4*3*2*1

之所以乘在一起，是因为每个数字只表示一个球的颜色可能，问题是要求排列6个小球，所以每个小球都只相当于做了一个步骤，应乘在一起。

观察6*5*4*3*2*1可以发现，它是数字逐个减1后相乘，很像逐个下台阶直到1。因此，数学中将这样的乘法定义为“阶乘”。

6*5*4*3*2*1 = 6!

因此，n的阶乘的实际意义可以被看作是给n个小球做全排列。

如果只要求给6个小球中的2个进行排列。依照刚才的思路则有：

拿出第一个小球，它共有6种可能的颜色，第二个小球则有5种可能的颜色，总体的情况为：

6*5

在排列组合中成为排列，可以记作：

2A6或2P6

（因为帖子里打不出真正的写法，我们就简单写为这样。打包版PDF中有正确的写法）

意思是从6个球中选出2个球进行排列。

例题1

Each participant in a certain study was assigned a sequence of 3 different letters from the set {A, B, C, D, E, F, G, H}. If no sequence was assigned to more than one participant and if 36 of the possible sequences were not assigned, what was the number of participants in the study? (Note, for example, that the sequence A, B, C is different from the sequence C, B, A.)

(A) 20

(B) 92

(D) 372

(E) 476

解：

这道题的关键在于把题目理解清楚。因为每个人会被分配三个字母且三个字母的顺序不同应被视为不同的排序。所以从8个字母中选出3个字母进行排序全部的可能性为3A8=8*7*6=336种。有36个结果无人认领，因此，总参加人数应该为336-36 = 300，答案为C。

除序法

了解完排列的实际意义后，我们就可以了解组合的实际意义了。

要求从6个球中选择2个球带走。请问，共有多少种不同的选法？

请注意这个问题和排列的区别。如果是从6个小球中排列2个小球，那么这2个小球的顺序是必须要计算的。但在刚才的问题中，由于题目只要求选择两个小球带走，所以我们不应该考虑两个小球的先后顺序，即，无论这两个球是什么顺序，都是带走了这两个球，所以应该算作一种情况。

由此可知，6*5这个算法多计算了两个小球的顺序。当算式中多计算了不需要的顺序时，我们应当把多出来的顺序除掉，即，

6*5/2!

“2!”表示两个小球的全排列。6*5中计算了两个小球的顺序，而因为题目不考虑它们的顺序，所以将该顺序除掉。这种不计算取出的小球间的顺序的方式叫做“组合”，记作：

2C6

（因为帖子里打不出真正的写法，我们简写为这样。打包版PDF中有正确的写法）

“除”顺序而不是“减”顺序的原因是取出的两个元素的顺序只是整个任务的一个步骤，我们可以把它想象成先取出小球，之后再对取出的小球进行全排列。根据乘法原理则有：

取*排 = 6*5

取 = 6*5/排 = 6*5/2!

也正是因为这个原因，人们经常说，“排列”和“组合”的区别就在于是否需要计算被选出的元素之间的顺序。

例题2

Departments A, B, and C have 10 employees each, and department D has 20 employees. Departments A, B, C, and D have no employees in common. A task force is to be formed by selecting 1 employee from each of departments A, B, and C and 2 employees from department D. How many different task forces are possible?

(A) 19,000

(B) 40,000

(D) 190,000

(E) 400,000

解：

一共4组雇员。我们一组一组的选。A组从10种取1个，共有1C10 = 1A10 = 10种可能。B，C两组都和A组相同。D组一共20人，选其中2个。显然这两个人的顺序是不应考虑的，即，不管选出的两个人谁在前谁在后，在这道题中都是相同的。

2C10 = 20*19/2! = 190

因为最终任务需要分别从4组选择，因此每组的情况都是一个步骤，四组应乘到一起，即，10*10*10*190 = 190000，答案为D。

例题3

From a group of 21 astronauts that includes 12 people with previous experience in space flight, a 3-person crew is to be selected so that exactly 1 person in the crew has previous experience in space flight. How many different crews of this type are possible?

(A) 432

(B) 594

(D) 1,330

(E) 7,980

解：

依题意，可以将题目的要求分成两步进行，第一步先选出那个有经验的，第二步选出剩下两个没有经验的。

有经验的共有1C12=12种选择；没经验的是2C9=36种选择，两者相乘等于432。答案为A。

重复元素

除序法除了在排列组合中有使用之外，还有两个情况经常使用。第一种情况就是当排列对象中出现了“重复元素”时，需要把本来计算过的多余的顺序除掉。

例如，ABCDE这五个字母的全排列应该为5！，此时五个字母均不相同，不存在重复元素的问题；但是，若出现相同的字母，例如AACDE，此时便会涉及到除序的问题。

由于五个字母中两个字母A是一样的，所以它们俩谁先谁后在全排列时是没有区别的。也就是说，这两个A的顺序不应该被考虑，因此，AACDE的顺序应为5！/2！

因此，但凡在排列时出现了重复的元素，我们计算全排列时应该把重复元素的顺序除掉。

例题4

There are 5 cars to be displayed in 5 parking spaces, with all the cars facing the same direction. Of the 5 cars, 3 are red, 1 is blue, and 1 is yellow. If the cars are identical except for color, how many different display arrangements of the 5 cars are possible?

(A) 20

(B) 25

(D) 60

(E) 125

解：

因为红色车之间没有区别，所以需要把红色车的顺序除掉，即，5！/3！=20。答案为A。

平均分组问题

除序法的另一个应用是平均分组问题。例如，ABCDEF六个人，要求把他们分成两组，一组4个人，另一组2个人，请问，一共有多少种分法？

这个问题的答案应该是：2C6 = 4C6 = 15种。即，从6个人中选出两个人分为一组，剩下的4个人自动成为第二组。当然，也可以先选出4个人，让剩下的两个人自动成为一组。

现在考虑另一个问题。如果要求将这个六个人分为三组，每组两个人，有多少种分法呢？依照刚才的思路可得：2C6*2C4*2C2 = 90种。

但是，90这个结果是不对的。假设，第一次的挑选情况为：

第一组：AB

第二组：CD

第三组：EF

第二次的挑选情况为：

第一组：CD

第二组：AB

第三组：EF

因为两次的三组选择情况不完全一样，所以在2C6*2C4*2C2这个算法中，这两次算作两种不同的情况。

但实际的问题中，只问了有多少种分组方法，并不应该考虑先挑哪组，再挑哪组。也就是说，只要AB是一组，CD是一组，EF是一组的情况，都应该算作一种情况。因此，当每组人数相同时，应该把多计算的组间顺序除掉，答案应为：2C6*2C4*2C2/3！=15种。此处，3！表示三组的全排列。

由此可知，当每组的元素个数相同时（平均分组），我们就需要考虑除掉组间顺序的问题。

桶装信问题

桶装信的最经典版本是：

小明手里有三封信，面前有三个桶。除了信必须要放在桶里外没有任何要求，问一共有几种放法？

这样的问题看起来有两个考虑的方向—“桶”和“信”。

从桶来考虑，这个问题十分复杂：

第一个桶里可能有信可能没信，可能有1封2封3封；第一个桶又会影响到第二个桶。

从信来考虑，这个问题就很简单了：

第一封信，有3种可能；第二封信，也有3种；第三封信，依然是三种。因为最终任务是要放完三封信，所以应该相乘，答案为3*3*3 = 9。

因此，桶装信问题请记住，永远都要从信的角度来考虑。类似的背景还有“小孩发糖”和“学生去教室”等等。

即，所有类似问题，都不要从容器角度出发，要从需放置的东西的角度出发。

例题5

A certain company assigns employees to offices in such a way that some of the offices can be empty and more than one employee can be assigned to an office. In how many ways can the company assign 3 employees to 2 different offices?

(A) 5

(B) 6

(D) 8

(E) 9

解：

雇员是信，办公室是桶。每个雇员有2个选择，答案为2*2*2 = 8。答案为D。

插空，捆绑法

当题目要求中提到“某两个元素必须挨在一起”或“某两个元素必须不能挨在一起”，此时需要用到捆绑或插空法。

例如，AACDE五个字母排队，要求AA必须在一起，问一共几种排法？

类似这样的问题，我们最先想到的应该是捆绑法，即，因为AA被要求必须在一起，所以可以将两个A“捆”在一起，当成一个元素。相当于4个元素的排列，即4！

插空法和捆绑法的使用情况刚好相对，例如

AACDE五个字母排队，要求两个A必须不能挨着，问一共几种排法？

类似这样的问题，我们可以将AA插到CDE之间，CDE之间有4个空位，即，_C_D_E_。插入后再安排CDE的顺序即可：2C4*3！=36种。

例题6

The letters D, G, I, I , and T can be used to form 5-letter strings as DIGIT or DGIIT. Using these letters, how many 5-letter strings can be formed in which the two occurrences of the letter I are separated by at least one other letter?

(A) 12

(B) 18

(D) 36

(E) 48

解：

本题中the two occurrences of the letter I are separated by at least one other letter的意思就是两个I必然不能相邻的情况，因此应该用插空法。我们可以将两个I插到DGT之间，DGT之间有4个空位，即，_C_D_E_。插入后再安排CDE的顺序即可：2C4*3！=36种。

当然，也可以用总数减去两个I捆绑在一起这个方法。即：5！/2！- 4！ = 36种。

答案是D。

隔板法

当给一堆元素分组，且每组元素个数不定时，就会用到隔板法。例如：

问：小明手里一共有6个苹果，要分给3个人，要求每个人必须能拿到一个苹果，问有几种分法？请注意，此时

我们可以这样想，将苹果横放一排：

0 0 0 0 0 0

假设手里有两个隔板，把它们插到这六个苹果中间，自然就把这些苹果分成了不定数量的三组。注意，头尾不能放板，是因为每个人都必须有一个苹果，如果放在最开头，那么第一个人就分不到苹果了（尾部同理）。

0 I 0 0 0 I 0 0

如上图这个放法，则第一组1个，第二组3个，第三组2个。因为6个苹果中间有五个空位，所以答案为2C5 = 10。

例题7

If x, y, z are both positive integers and x + y + z = 10, how many different sets of x, y, z?

(A) 72

(B) 54

(D) 20

(E) 18

解：

x, y, z均不能为0且是整数，一共加和为10，这就可以看作10个苹果分三组，每组必有一个苹果的情况。10个苹果间有9个空位，即，2C9 = 36。答案为C。

圆桌问题

普通列成一排时，ABCDE五个人全排列是5！。此时，ABCDE和BCDEA是不同的。但当这五个人围坐在一个圆桌上时，开头和结尾变得模糊，ABCDE，BCDEA，CDEAB，DEABC，EABCD都是相同的。

因为一共五个字母，不论谁开头都是一样的，所以需要把这5种顺序除掉，即，排序为5！/5 = 24种。

若有n的元素围成圆桌排序，则一共有n！/n = (n-1)！种排序方式。

例题8

At a dinner party, 5 people are to be seated around a circular table. Two seating arrangements are considered different only when the positions of the people are different relative to each other. What is the total number of different possible seating arrangements for the group?

(A) 5

(B) 10

(D) 32

(E) 120

解：

圆桌问题，答案为(5-1)! = 24，答案为C。

实战解题

排列组合考题的解题关键在于“逐步完成问题”，在分步骤或分情况时需做到“不重不漏”。其实任何数学问题乃至生活中的问题都是如此，一口气吃一个胖子是困难甚至无法完成的，但如果能将整件事分成一个一个简单的小步骤，那么由于每一步都是简单的，所以完成一件“大事”就不再困难。

例题9

A company plans to assign identification numbers to its employees. Each number is to consist of four different digits from 0 to 9, inclusive, except that the first digit cannot be 0. How many different identification numbers are possible?

(A) 3,024

(B) 4,536

(D) 9,000

(E) 10,000

解：

某公司要给员工编号，员工的编号由0-9中四位不同的数字构成，并且第一位不能为0，问最多有多少个编号。

我们可以将整个问题分为两个简单的步骤，第一步是选取第一位数字（因为第一位数字有特殊的要求），第二步则是选取剩余的三位数字。

第一位可以选择的数字共有9个（除了0），因此它的总共有9种可能；

余下三位将会从0-9中剔除了第一位选择的数后的9个数中选三个进行排列，因此共有3A9种可能。

综上，总数为9*3A9 = 4536。答案为B。

例题10

A certain university will select 1 of 7 candidates eligible to fill a position in the mathematics department and 2 of 10 candidates eligible to fill 2 identical positions in the computer science department. If none of the candidates is eligible for a position in both departments, how many different sets of 3 candidates are there to fill the 3 positions?

(A) 42

(B) 70

(D) 165

(E) 315

解：

第一步从7个人中选一个；第二步从10个人中选两个。两步相乘可得答案，则有：

1C7*2C10 = 315。答案为E。

例题11

Two members of a club are to be selected to represent the club at a national meeting. If there are 190 different possible selections of the 2 members, how many members does the club have?

(A) 20

(B) 27

(D) 57

(E) 95

解：

依题意，设共有n个人，则有： 2Cn=190，即，n(n-1)/2 = 190，则，n = 20。综上，答案为A。

例题12

The letters C, I, R, C, L, and E can be used to form 6-letter strings such as CIRCLE or CCIRLE. Using these letters, how many different 6-letter strings can be formed in which the two occurrences of the letter C are separated by at least one other letter?

(A) 96

(B) 120

(D) 180

(E) 240

解：

本题问的是两个C不相邻的情况，因此应该用插空法。我们可以分为两步，第一步先将两个C插到IRLE之间，IRLE之间有5个空位，即，_I_R_L_E_，选取两个空位放上C，结果为2C5；第二步在插入后，再安排IRLE这四个字母的全排列，即，4！。

2C5*4！=240。答案为E。

例题13

In a certain group of 10 members, 4 members teach only French and the rest teach only Spanish or German. If the group is to choose a 3-member committee, which must have at least 1 member who teaches French, how many different committees can be chosen?

(A) 40

(B) 50

(D) 80

(E) 100

解：

10人中有4人只教法语，剩下6人只教西语或者德语。从10人中选三人成小队，至少有一个人教法语。问有多少种选法？

至少有一个教法语的老师有如下这几种情况（请注意，此处是不同的情况而不是步骤，因为每一种情况都能完成分配）：

1.仅有1个法语老师：1C4*2C6=60；

2.有且仅有2个法语老师：2C4*1C6=36；

3.3个都是法语老师：3C4 = 4

三者相加为100。

但是本题还有更简单的解法，所谓“正难则反”，至少有一个教法语的老师，反面则是一个教法语的老师都没有，用10人中随机选三人的总数减去这个反面的数字，则是至少有一个教法语老师的数：3C10-3C6=100。答案为E。