初等组合

pipi

原帖由 dunwan2tellu 于 15-11-2006 05:49 PM 发表
我来试试看
我当作都是选 3 个号码
7(i) 6C3 = 20
7(ii) 4C3 = 4

一般性，从 S = {1,2,3...,n} 选 3 个 k-分离,方法有

(n-2k+2)C3

对了！请解释你的答案！
再来一般性：
8）设 S = {1,2,3,...,n}。S 有几种不同的（a_1,a_2,...,a_k），a_i < a_j if i < j，是 k-分离的？

相信这题难不了你吧！请与大家分享你的方法吧！

dunwan2tellu

原帖由 pipi 于 15-11-2006 09:13 PM 发表

对了！请解释你的答案！
再来一般性：
8）设 S = {1,2,3,...,n}。S 有几种不同的（a_1,a_2,...,a_k），a_i < a_j if i < j，是 k-分离的？

相信这题难不了你吧！请与大家分享你的方法吧！

我就解释选 3 个 2-分离 的方法。

S = {1,2,3...,n}

想象 3 个球 O ，排成一排，它们之间就有 2 个空位。 如下

O _ O _ O

空位加上球就有 3 + 2 = 5 个 物品

总共 n 个物品，去掉 5 个剩下 n-5 个 。

现在我要把 n-5 个物品放进 4 个空位。哪4个？除了原本的两个空位，还有最左和最右两个 ， 图画如下

_ O _ O _ O _

方法就相等于 a + b + c + d = n-5 , a,b,c,d>=0 是整数，那么 (a,b,c,d) 几种方法？这个就和 (4) 同样，方法有 (n-2)C3

用同样的逻辑，让其他网友来想想为何从 S 里选 3 个 k-分离的方法有 (n-2k+2)C3 ,从而推广到从 S 里选 m 个 k-分离的方法。

答对者就加分奖励。