证明：从 n 个数中任选 k 个数作可有重复的组合，不同的组合种数为 C(n+k-1,k)

wintex

請問問題

luyuanhong

题 证明：从 n 个数中任选 k 个数作可有重复的组合，不同的组合种数为 C(n+k-1,k) 。

证 这个结论，通常可以用“隔板法”来证明。下面采用另一种证明方法：

   设 A1,A2,A3,…,Ak 是从 1,2,…,n 中选出的 k 个可有重复的数。

   将这 k 个数按照从小到大的次序排序，不妨设有 A1≤A2≤A3≤…≤Ak 。

   然后对它们依次加上 0,1,2,…,n-1 ，得到 A1+0,A2+1,A3+2,…,Ak+n-1 。

   因为 A1 是从 1,2,…,n 中选出的数，有 A1≥1 ，所以必有 A1+0≥1 。

   因为 Ak 是从 1,2,…,n 中选出的数，有 Ak≤n ，所以必有 Ak+n-1≤n+k-1 。

   在 A1,A2,A3,…,Ak 中，可以有两个相邻的数相等，但是依次加上 0,1,2,…,n-1 后，

在 A1+0,A2+1,A3+2,…,Ak+n-1 中，任何两个相邻的数，至少相差 1 ，不会相等。

   可见，A1+0,A2+1,A3+2,…,Ak+n-1 是从 n+k-1 个数 1,2,…,n+k-1 中选出的 k 个

无重复的数。

   上面的论述告诉我们：每一种从 n 个数中选 k 个数组成的可有重复的数的组合，都

对应于一种从 n+k-1 个数中选 k 个数组成的无重复的数的组合。

   反过来，设 B1,B2,B3,…,Bk 是从 1,2,…,n+k-1 中选出的 k 个无重复的数。

   将这 k 个数按照从小到大的次序排序，不妨设有 B1＜B2＜B3＜…＜Bk 。

   然后对它们依次减去 0,1,2,…,n-1 ，得到 B1-0,B2-1,B3-2,…,Bk-n+1 。

   因为 B1 是从 1,2,…,n+k-1 中选出的数，有 B1≥1 ，所以必有 B1-0≥1 。

   因为 Bk 是从 1,2,…,n+k-1 中选出的数，有 Bk≤n+k-1 ，所以必有 Bk-n+1≤k 。

   在 B1,B2,B3,…,Bk 中，任何两个相邻的数都不会相等，但是依次减去 0,1,2,…,n-1

后，在 B1-0,B2-1,B3-2,…,Bk-n+1 中，两个相邻的数，有可能相等。

   可见，B1-0,B2-1,B3-2,…,Bk-n+1 是从 n 个数 1,2,…,n 中选出的 k 个可有重复的数。

   上面的论述告诉我们：每一种从 n+k-1 个数中选 k 个数组成的无重复的数的组合，都

对应于一种从 n 个数中选 k 个数组成的可有重复的数的组合。

   综合上面的论述可知：从 n+k-1 个数中选 k 个数组成的无重复的数的组合，与从 n 个数

中选 k 个数组成的可有重复的数的组合，是一一对应的。

   因为从 n+k-1 个数中选 k 个数作无重复的组合，共有 C(n+k-1,k) 种不同的组合法，所以，

从 n 个数中选 k 个数作可有重复的组合，也有 C(n+k-1,k) 种不同的组合法。