题 证明:从 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) 种不同的组合法。 |