199管综——分组分配问题

长春学子

例．将3封信投入4个不同的信箱,则不同的投信方法种数是多少？
这是一个典型的分房问题，3个人4间房，每个人都有4种选择，所以结果就是3个4相乘，是4^3，也就是“房”的“人”次方。非常简单的一类问题，但是其中却隐藏着很多的条件，主要是以下6个：
1.房是不同的(组别或编号)
2.人是不同的(元素是否相同)
3.房子的容量是无限的（1对多）
4.一个人只能住到一个房子里（1对1）
5.房子可以空(组内元素数是否可以为0)
6.人必须都住到房子里（是否分尽）
下面分别给大家介绍一下每个条件的运用：
1. 房是不同的，这个限定条件在分组问题上体现为是否有组别或者编号，如果房间是相同的没有区别，那么就会比房间不同的情况分类要少，因为会出现重复的情况。
2. 人是不同的，这说明分配的元素是不相同的，如若元素相同，那么每个组的区别可能就体现在元素的数量上了。
3. 房子的容量是无限的，这是分组问题一个很重要的条件，就是每个组的人数没有限制，所有人都可以在一个组，而这个组的元素数量没有上限。
4. 一个人只能住到一个房子里，这个同样也是一个很重要的条件，结合上面的条件（3），如果一间房只能容纳一个人，而一个人只能住到一个房子里，那么这个问题转化成了排列组合的问题，“一对一”是排列组合问题的基本要求。
5. 房子可以空，也就是组内元素数是否可以为0 的情况，这个在实际中会有这样的问题，如果把10个元素分成三组，三组元素数如果是5，5，0的情况，那么我们们会理解成分成了两组，如果认为有一组是0的话，那么也可以理解成分为4组或更多组，其他组的元素数为0，这个就会有些冲突。
6. 人必须都住到房子里，这个条件所分元素是否分尽，没有分尽的话，我们要讨论分了多少，也即是分尽了多少，还是转移到分尽的情况之下。
上面6条就是根据分房问题的隐含条件进行了分析，也是构成分组问题的基础，根据更
改不同的条件把分组问题分成不同的类型，一般条件（3）和（4）是不变的，因为是构成分组问题的基础，如果改变那么很有可能就不是分组问题而是排列组合问题或者其他问题了，下面我们改变一些条件，讨论下常见的两种分组类型：
1.保留条件（2），这个时候问题变成了不同元素的分组问题，根据是否改变条件（1），又分成是否有编号的两类不同元素分组，不同元素分组问题一般会确定每组人数，也就是条件（5）组内元素数是固定的，这个时候又根据任意每两组人数是否相同分为均匀分组和不均匀分组，至于条件（6）是否分尽，对于不同元素分组问题是没有影响的。
2.保留条件（1），改变条件（2），这个时候变成了相同元素分组的问题，这种问题一般选用隔板法去做，比起不同元素的分组问题，相同元素的分组问题有着更严格的要求，比如条件（5）要求每组至少有一个人，而条件（6）要求必须分尽。

阿莱moon

太有帮助了

考霸霸霸霸霸霸

太有帮助了