课堂实录｜组合问题处理策略
前面讲了
排列问题的常规处理策略
其实我认为
能够把站队的问题处理好
排列的计数就不会成为问题了
当然
务必要记住
不同条件下的计数策略
就像
特殊元素优先法
相邻问题捆绑
不相邻问题插空
相同元素排列用位置分析法
先分类后分步
……
其实
彭老师认为
这些方法都不难理解
难的是遇到一个陌生的情境
你还能不能认识它？！
就好象上期留的这个
从1~9这9个数字当中，任取三个互不相邻的数字，有多少种不同的取法？
这种问题的处理
也确实是要讲求策略的
否则
大多会一头雾水
而且你问题处理的设计
务必要让你的每一步操作
都要流畅
才能完美解决问题
所以
我就这样思考
假设现在有编号为1~9的9个小球，分别自左向右排列。那本题就相当于从这9个球当中取出三个互不相邻的小球。
确实，就这个样子按条件去取，情况太多、是比较麻烦的。
如果静下心来深思，这个事情的处理我觉得可以这样理解：既然是互不相邻的取出小球，按照排列计数方法，应该是“不相邻问题”，那最好的方法就一定是插空法了。
当然，“要求谁不相邻，我们就用谁来插空“，这是插空法的基本操作，那我们就需要先将其它的球排列好，才会出来空。
先排谁呢？看我这样处理：
（1）先将球上的号码抹去。手上拿3个小球，其它的6个小球在桌上排列成一排（如图）；
（2）6个小球排成一排后，形成了7个空。从中选出3个空，并将手上的三个小球分别插进去（如图）。而且，因为小球都是一样的，选空就可以了，小球都是在空里，插进去后自然也就不会相邻的；
（3）然后自左向右，再分别在小球上编上号码1~9看看（如图）；
因为插进去的小球不相邻，那编号后的号码，肯定也就不会连续。
如图取出来的三个数字就分别是：1、4、7，自然会满足条件。
按这个思路，原题的结果应该是：
所以我们说
计数问题本身倒是没什么
难的是
如何将一个
相对陌生的情境
转化成你所熟悉的题型
然后
再设计一个优雅的解题策略
当然
方法固然重要
但策略才最
最至关重要的
…
可惜
今天我们的主题是讲组合
所以闲言少叙了
彭老师
数学教书匠
其实，在组合当中主要注意两个题型：分组和分配。那么这一讲我们主要就这两个问题做一些方法的介绍。
分组问题
彭老师
数学教书匠
其实，生活中我们也会经常做这件事情的。比如元旦晚会时，我们会买很多的桔子，然后将它们分成一小袋一小袋的，这其实就是分组。
那在生活中，我们如何进行分组呢？
她
如果已经确定了每一堆的数量，那我只要直接去抓就可以了。先从6个里面取3个（作为一组），再从剩下的3个里面取两个（作为一组），剩下的一个就作为一组了。
那结果应该是：
彭老师
数学教书匠
确实，在生活中我们要分组，其实就是将一些元素组合在一起，操作时直接从所有元素中取出就可以了，分步原理用乘法，也是没有任何问题的。很好！
那我们再看下面这题：
他
我觉得这个和例1一样，先从6个里面选2个，再从剩下的4个里面选2个，最后剩下的2个就自动作为一组了。
那应该是：
彭老师
数学教书匠
真的一样吗？有没有同学有不同意见呢？
等分组问题是疑点
要让学生认真分析
分步选取元素
与分组所产生的矛盾
每一组中元素个数相同和不同时，好像是有点不一样的……
有什么不一样了呢
假如现在是分成了三组：AB、CD、EF，在选取元素时，因为是分步选取的，所以这三个组出现的顺序就有可能不一样了，但分组的结果是一样的。
彭老师
数学教书匠
确实，分组时我们关心的是结果，也就是每个小组中的元素都有谁。至于每个组形成的先后或组中的元素是怎么选取的，对我是无所谓的。
在分步选取元素时，
却产生了顺序。
分组的结果不应该有顺序！我也觉得有重复。
象这样选取的三个组，其实是一样的，只能算一种分组。
李小男
这样一来，取相同的三个组合，一共会有3！种不同的选法，那这3！种选法对于分组来说，只能算一种分法。
3！种如果只能算一种，那一共
彭老师
数学教书匠
大家分析的非常好！
象这种每个组内元素个数都相同的分组，我们称为等分组。对于等分组问题，因为每组内元素个数都相同，所以在分步选取组内元素时，小组之间就会产生一个顺序，而对分组来说，讲究的是结果，而不是过程。所以分步选取小组内元素，只是分组的过程，再将其除以组数的阶乘，才是分组的方法数。
彭老师
数学教书匠
大家再思考下下面这个问题：
8本不同的书分成三堆，其中有两组有3本书，一组2本书。则有多少种不同的分法？
这个简单啊。
先取从8本中3本，再从剩下的5本中取3本，最后取剩下的2本，按刚才的思路，再除以3的阶乘！
好象不对。就象如果分成的是abc,def和mn,在选取的时候，可能是按这个顺序，但也可能是def,abc和mn的顺序，因为只有两个组的元素个数是相同的，所以应该只有这两种重复的情况。
我认为，只要除以2的阶乘就好了。
应该是：
她
有道理！
彭老师
数学教书匠
这位同学分析的很好。
看来，等分组的问题，首先一定要除以组数的阶乘，但这个组数，应该只是等分的组数，有几个组的元素个数相同，就除以几的阶乘，而不应该是全体组数的阶乘。
分配问题
这个题中没有告诉我们每个人得几本书，那就是随便了。
那我就拿每本书送给人，每本书都有3种选择，那应该就是36种。
彭老师
数学教书匠
大家都能赞同她的做法吧？
这个问题是把书分给人，我们把类似于这样的问题叫“分配问题”。在本题中分配时，书是有主动性的，不同的书可以重复的分给某一个人，这种叫“重复分配问题”，这位同学的方法，叫“求幂法”。
比如：你手上有四封信，街上有三个邮筒，现在你去寄信时，每拿一封信，你应该都会考虑“我是塞进哪只邮筒呢”。那每封信都有3种选择，按照分步原理，就应该是四个3相乘，也就是34
从6本书里选一本给三人中的一人，再从剩下5本书中选两本送给剩下两人中的一人，最后的三本送给最后一个人。
应该有:
你这是用书去选人。
我觉得可以用人去选书：选让甲去选一本，再让乙去选两本，最后丙拿三本。应该是：
我觉得这有问题。
因为你也不能确定甲就是一本，乙就两本啊。
所以，应该乘以3的阶乘。
它们的结果是一样的。
彭老师
数学教书匠
其实这两种方法都是可以的，只是两种做事的策略不同。从内心来说，我还是偏向于第二种策略，这种策略使得问题的处理更流畅。
仔细想想呢，
所以，以后遇到分配问题，我们就遵循“先分组再分配”的原则。
彭老师
数学教书匠
如果将题中的不同的书，都改成”相同“的书，又会是怎么样呢？
按照先分组再分配的原则，应该是：
但元素相同时的分组，
应该和元素不相同有区别的吧？
元素如果相同，不管各组元素是多少，我认为应该都只有一种分法！
第一步：从6个里面取3个，怎么取不都是一样的嘛，应该只有一种情况；
第二步：从剩下的3个里任取2个，也应该只有一种情况；
第三步：剩下的1个作为一组，当然只有一种情况。
那按照分步乘法原理，三个1相乘，自然只有一种方法了。
彭老师
数学教书匠
这位同学说的非常有道理！
如果元素相同，那不论一次任取多少元素，都是只有一种取法的。
如果不论如何分组，都只有一种方法，那怎么分配呢？
王小五
既然一定要分组才能分配，那我分组用穷举法行不？比如：
：1-1-4、1-2-3、2-2-2。然后再分配。
小明
可以是可以，但如果元素个数很多时，还不得累死！
大家一定看过《赌神》或与赌博相关的电影吧？
我们虽不能参与赌博，但了解一些常识还是可以的。一般赌桌上除了筹码之外，好象还有一根长棍。有同学能告诉我们，这根长棍是用来干什么的吗？
彭老师
数学教书匠
是的，这是为了取筹码的方便。只所以这样做，主要还是因为筹码和筹码之间并没有区别，都是一样的。如果我要给你五个筹码，用棍子放在筹码之间的空隙拨拉给你就可以了。
这个没问题，确实是这样。
但，这与我们的这个题目有什么关系呢？
彭老师
数学教书匠
既然筹码都是一样的，我们认为都是相同的元素，筹码要分给赢了的人，不就是将这些相同的元素分配给不同的人嘛！
那这样，这个情景和我们这个题，本质上是没有区别的。
嗯，情景虽不同，意思其实是一样的。那与这个题的解法又有什么联系呢？
彭老师
数学教书匠
大家看看这个动态图，看看能不能找到一点灵感或启示。
小明
应该是先把筹码排成一排，然后用两根棍子插到空隙里，将筹码就分成了三组，再拨拉给三个人，当然，事先已确定了三个人的位置。
彭老师
数学教书匠
就是这个意思。
要分成三组，我们可以用两根棍子插到空隙中，虽然从结果上看，有可能分成的三组中元素个数情况是一样的，但只要三个组的位置不同，分配方案就是不一样的！就象这样：
这两种分组的结果虽然一样，都是1-2-3分组，但因棍子放置的位置不同，所以分配的方法也就不一样。
那按这种方式，一种插空的方法，其实就对应了一种分配的方法，分组和分配同时完成了。
两边的空不能插，中间有5个空，从5个不同的空当中选取两个空就行了。那分配的方法数应该就是：
彭老师
数学教书匠
非常正确了！
那，以后遇到这种相同元素的分配问题时，我们就可以统一的用这种思路，这里的棍子是用来隔开元素的，我们一般把它叫作隔板，那这种方法我们把它叫作”隔板法“。
彭老师
数学教书匠
很显然，因为6本书是一样的，肯定不能用36了。那既然是相同元素的分配问题，还得用”隔板法“。但因为不一定每个人都能分到书，所以和上面的题还是有点不一样的。
这时候的隔板和隔板可以相邻，也可以不相邻，还可以放两边的空吧？
那象这样子插空，怎么计数呢？
小明
先在7个空中选一个空放隔板个，然后再插一个。
插一个隔板后，就多了两个空，但因为后面的隔板和它是一样的，那这两个空插哪个都是相同的。所以第二个隔板在插空时，应该是8种方法。
那结果应该是8乘以7，等于56。
我觉得，如果两个隔板在插空放置的时候没有任何条件限制，那其实就是把6个相同的书和2个相同的隔板做一个全排列，应该看成是“有相同元素的排列问题”，按照以前老师的方法，从位置上去考虑更方便，8个元素共占了8位，其中有两个是隔板的，
那应该是：
这个方法好。
但，我觉得第一个思路，先放一个，再放一个，思路也挺好的，为什么会是56呢？
正好是28的两倍！
因为两个隔板是一样的，先放一个再放一个，就产生的顺序，正好是2的阶乘，等于2。 所以要除以2。
彭老师
数学教书匠
这位同学说的非常有道理！结果28也是没有问题的。
那象这种“相同元素的分配问题”，我们以后统一的考虑用“隔板法”，但在用隔板法时，如果隔板和隔板不能相邻，我们就插空，如果可以相邻也可以不相邻，也就是没有任何条件限制，那我们还是当作全排列问题，处理起来思路应该更加的清晰，当然，我们也一定要记住：有相同元素的排列问题，要从位置上去考虑，选空或留空处理。
彭老师
数学教书匠
当然，在具体问题中，题目的情境不一定就这么直白，那就要求我们要善于将一个陌生的情境转化成我们所熟悉的。比如我们看下面这两个例题：
重视化归
（1）可以考虑将10看为10个完全相同的小球，x、y、z看成三个盒子，则本题可以看作是将10个相同的小球放进三个不同的盒子，就是典型的相同元素的分配问题，而且因为是非负整数解，所以是可以允许某些盒子中是没有球的……结果为66.
（2）其实映射的定义和分配问题也真是非常吻合的。就拿“将球放进盒子的问题来对比”，记得，映射的定义中包含了“两允许两不允许”这两个条件：
“允许多对一、不允许一对多”其实就是说：不同的球可以放进一个盒子，但同一个球不能放进不同的盒子。但在放球时，这是显然的；
“允许B中元素有剩余、不允许A中有剩余元素”：其实也只要加条件“将球全部放进盒子”，就满足映射的这个条件了。
按这种分析，这个题就是“将编号为1~6的6个小球，放进编号是7~9的三个盒子，要求，编号较小的球放进的盒子的编号不能大于编号大的球放进盒子的编号”。
结果应该是