可重复排列组合问题，由2019小米秋招笔试题所想

最近看到了一道小米的笔试题，感觉有点意思，在此记录一下。

一、题目描述

二、可重复组合问题

其实这是一个很典型的可重复组合问题，其定义如下：

重复组合(combination with repetition)是一种特殊的组合，从n个不同元素中可重复地选取r个元素，不管其顺序合成一组，称为从n个元素中取r个元素的可重复组合。两可重复组合相同当且仅当所取的元素相同且同一元素所取的次数相同。

一般地，从n个不同的元素中，每次取出r个可以重复的元素并成一组，叫做从n个不同的元素每次取出r个元素的允许重复的组合，即重复组合，其组合总数记作H(r,n)。

从n个不同的元素每次取出r个元素的允许重复的组合总数为：

故此题答案为C(4,7) = 35.

三、其他解法：隔板法

隔板法的例子：将20个大小形状完全相同的小球放入3个不同的盒子，允许有盒子为空，但球必须放完，有多少种不同的方法？

解析：将20个小球分成三组需要两块隔板，因为允许有盒子为空，不符合隔板法的原理，那就人为的再加上3个小球，保证每个盒子都至少分到一个小球，那就符合隔板法的要求了

（分完后，再在每组中各去掉一个小球，即满足了题设的要求）。

然后就变成待分小球总数为23个，球中间有22个空档，需要在这22个空档里加入2个隔板来分隔为3份，共有C（22，2）= 231 种不同的方法.

在我们知道了隔板法的用法时，将上面题目类比成卡尔三个球时的情况。

将3个大小形状完全相同的小球放入3个不同的技能格（冰、雷、火），允许有技能格为空（可以不含冰或者雷或者火），但球必须放完，有多少种不同的方法？

C(3 + 3 - 1，2) = C(5, 2) = 10 种

然后，再看看四种球时候。

将4个大小形状完全相同的小球放入4个不同的技能格（冰、雷、火、风），允许有技能格为空（可以不含冰或者雷或者火或者风），但球必须放完，有多少种不同的方法？

C(4 + 4 - 1, 3) = C(7, 3) = 35 种

隔板法的例子：将20个大小形状完全相同的小球放入3个不同的盒子，允许有盒子为空，但球必须放完，有多少种不同的方法？

解析：将20个小球分成三组需要两块隔板，因为允许有盒子为空，不符合隔板法的原理，那就人为的再加上3个小球，保证每个盒子都至少分到一个小球，那就符合隔板法的要求了（分完后，再在每组中各去掉一个小球，即满足了题设的要求）。然后就变成待分小球总数为23个，球中间有22个空档，需要在这22个空档里加入2个隔板来分隔为3份，共有C（22，2）= 231 种不同的方法.

在我们知道了隔板法的用法时，将上面题目类比成卡尔三个球时的情况。

将3个大小形状完全相同的小球放入3个不同的技能格（冰、雷、火），允许有技能格为空（可以不含冰或者雷或者火），但球必须放完，有多少种不同的方法？

C(3 + 3 - 1，2) = C(5, 2) = 10 种

然后，再看看四种球时候。

将4个大小形状完全相同的小球放入4个不同的技能格（冰、雷、火、风），允许有技能格为空（可以不含冰或者雷或者火或者风），但球必须放完，有多少种不同的方法？

C(4 + 4 - 1, 3) = C(7, 3) = 35 种

PS：听说最终的正确答案是48，不知道怎么算出来的，请有解法的同学告知一下 。