排列组合之同素分堆问题
2023-06-27 14:11 作者:xuexuenahaha | 我要投稿
排列组合——同素分堆
特征：将相同元素分成不同堆，求情况数。
结论：
1. 将n个相同元素分成m个不同堆，每堆至少分得1个元素，有多少种情况。
02:03
结论1：将n个相同元素分成m个不同堆，每堆至少分得1个元素，情况数为：C(n-1,m-1)
2. 将n个相同元素分成m个不同堆，每堆至少分得x个元素，有多少种情况。
思路：将问题转换为至少分得一个，有多少种情况。
方法：先分别给每一堆分（x-1个），则题目转换为：将n-(x-1)*m个相同元素分成m个不同堆，每堆至少分得1个元素，有多少种情况。
07:59
结论2：将n个相同元素分成m个不同堆，每堆至少分得x个元素，情况数为C(n-(x-1)*m-1,m-1)。
3. 将n个元素分成4堆，a至少分得1个，b至少分得2个，c至少分得3个，d至少分得4个，有多少种情况。
思路：将问题转换为至少分得一个，有多少种情况。
方法：先满足部分要求，即，先给a分0个，给b分1个、给c分2个、给d分3个，则题目转换为：将n-6个相同元素分成4个不同堆，每堆至少分得1个元素，有多少种情况。
09:25
4. 将n个相同元素分成m个不同堆，有多少种情况。
思路：将问题转换为至少分得一个，有多少种情况。
方法：可能有人分得0个，故先每人借1个，则题目转换为：将n+m个相同元素分成m个不同堆，每堆至少分得1个元素，有多少种情况。
11:32
结论3：将n个相同元素分成m个不同堆，情况数为C(n+m-1,m-1)。
思考题
14:51
利用同素分堆及其相关结论求解：
