排列组合

p16

重复组合

[说明]

由ｎ类相异物中，任取ｒ个为一组，其中每类物品的个数均不小于ｒ且可重复选取，则称此种组合为ｎ中取ｒ之重复组合，其组合数以n r H 表之。

如何求n r H 之值呢？我们先看一简单的问题。

问题１：假设红、蓝、白三种颜色的球均超过４个，从其中取４个球，试问其可能的取法数34H 为多少？

在此问题中，对于我们所取出的４个球分别以X 1表示红色球的个数、以X 2表示蓝色球的个数、 以X 3表示白色球的个数，则可知X 1＋X 2＋X 3＝4。 所取４个球的每一种组合对应到一组 ( X 1，X 2，X 3 )的值，但必须满足 X 1＋X 2＋X 3＝4。 反之，方程式X 1＋X 2＋X 3＝4的任一非负整数解，可代表所取４个球的某一组合。 例如， X 1＝1，X 2＝1，X 3＝2即表示所取的４个球中有１个红色球，１个蓝色球及２个白色球。 因此3

4H 亦是方程式 X 1＋X 2＋X 3＝4的非负整数解之个数，即问题１和下列的问题２是相同的。

问题２： X 1＋X 2＋X 3＝4有几组非负整数解？

解问题２，可将所有可能的解一一列举出来，即( X 1，X 2，X 3 )可为：

(4，0，0)、(0，4，0)、(0，0，4)、(3，1，0)、(3，0，1)、(1，3，0)、(1，0，3)、(0，3，1)、(0，1，3)、(2，2，0)、(2，0，2)、(0，2，2)、(1，2，1)、(2，1，1)、(1，1，2)共 15 种。 我们现考虑另一种解法，以便能推广到更一般的问题上。我们以连续的"︱"来表示 X 1，X 2，X 3之值，例如" ∥"表示２。则当解为X 1＝1，X 2＝1，X 3＝2时，以"︱＋︱＋∥"表示，其中我们以"＋"号将相隔二数分间，又当其解为X 1＝1，X 2＝0，X 3＝3时，以" ︱＋ ＋III"表示。(因为X 2＝0，所以２个"＋"号中间就没有"︱")，因此， X 1＋X 2＋X 3＝4的每一组解都是４个"︱"及２个"＋"的一种直线排列，而这样的排列数为 !

2!4!6⨯=62C =15，即 34H =62C =15。 而对一般的情况，由ｎ类相异物中，任取ｒ个为一组的重复组数n r H 如何求呢？同样地，令X i 表所取ｒ个中，第ｉ类物品之个数， i=1，2，………，n ，则n r H 即为方程式 X 1＋X 2＋…..X n ＝r 之非负整数解个数，而此方程式之非负整数解个数，等于ｒ个"︱"及(ｎ－１)个"＋"的直线排列数，即 [])!1(!!)1(-⨯-+n r n r =11-+-n r n C 。

总结上述的说明，我们有如下之定理：

[定理] 由ｎ类相异物中，任取ｒ个的重复组合数与方程式 X 1＋X 2＋…..X n ＝r