初等组合

pipi

我又来自告奋勇，提一些初等组合的题目与大家分享，目前目标是
每天都放一，两题；为期一个月。


题目:
(1) 若 a, b, c 为正整数，有多少(a,b,c) 满足
    a + b + c  = 10 。
(2) 若 a_1, a_2,..., a_k 为正整数，有多少(a_1,a_2,..., a_k) 满足
    a_1 + a_2 + ... + a_k  = n， n 为正整数。

(3) 若 a, b, c 为非负整数，有多少(a,b,c) 满足
    a + b + c  = 10 。
(4) 若 a_1, a_2,..., a_k 为非负整数，有多少(a_1,a_2,..., a_k) 满足
    a_1 + a_2 + ... + a_k  = n， n 为非负整数。

[ 本帖最后由 pipi 于 3-11-2006 03:38 PM 编辑 ]

ministar84

(c.)
a+b+c=10
(10,0,0)有3个排法
(9,1,0)有6排法
(8,2,0)有6个排法
(8,1,1)有3个排法
(7,3,0)有6个排法
(7,2,1)有6个排法
(6,4,0)有6个排法
(6,3,1)有6个排法
(6,2,2)有3个排法
(5,5,0)有3个排法
(5,4,1)有6个排法
(5,3,2)有6个排法
(4,4,2)有3个排法
(4,3,3)有3个排法
所以有66个答案!!
笨方法!!哈哈哈...

(a)
就少掉有零的答案!!
66-30=36

pipi

原帖由 ministar84 于 3-11-2006 08:48 PM 发表
(c.)
a+b+c=10
(10,0,0)有3个排法
(9,1,0)有6排法
(8,2,0)有6个排法
(8,1,1)有3个排法
(7,3,0)有6个排法
(7,2,1)有6个排法
(6,4,0)有6个排法
(6,3,1)有6个排法
(6,2,2)有3个排法
(5,5,0)有3个排法
(5 ...

答案是对的！
这个方法也行，只是有点长了些！
是有更好方法的！请再试试！

pipi

原帖由 pipi 于 3-11-2006 03:34 PM 发表
(3) 若 a, b, c 为非负整数，有多少(a,b,c) 满足
    a + b + c  = 10 。

试试这个：

10个 ＂0＂ 及2个 ＂1＂ 排成一条直线，有多少不一样的方法？

这两题之间，有什么联系？

[ 本帖最后由 pipi 于 6-11-2006 11:35 AM 编辑 ]

pipi

过了这一两天，没有人回复，我来自得其乐！
首先，为了方便书写，设 C(n,r) = n choose r.
下面这一道题，SPM 程度也可轻松解到！

10个 ＂0＂ 及2个 ＂1＂ 排成一条直线，有多少不一样的方法？

明显的，答案是 12!/2!10! = C(12,2) = 66.

我们挑几个例子：
(a) 001000001000
(b) 010001000000
(c) 000000010001
(d) 110000000000

(a)(b)的两个“1” 把十个零分成 3 个部分，分别是：
(a) 001000001000  ---->  （2，5，3）
(b) 010001000000  ---->  （1，3，6）

严格上来说，(c)(d)的两个“1” 也把十个零分成 3 个部分
（只是它允许“零”部分），分别是：
(c) 000000010001  ---->  （7，3，0）
(d) 110000000000  ---->  （0，0，10）

所以，以上问题的每一个解法，都会"配对"与以下问题的一个解法。

(3) 若 a, b, c 为非负整数，有多少(a,b,c) 满足
    a + b + c  = 10 。

同样的，任何一组(a,b,c)，也出现唯一“01”的配对
比如：
(1,2,7)  -----> 010010000000
(8,2,0)  -----> 000000001001

所以，以上两个问题有同样多的解法，即：C(12,2)=66.

pipi

如贴 #5 的解释，

原帖由 pipi 于 3-11-2006 03:34 PM 发表
(1) 若 a, b, c 为正整数，有多少(a,b,c) 满足
    a + b + c  = 10 。

就好比是

10个 ＂0＂ 及2个 ＂1＂ 排成一条直线，
其中两个＂1＂不可以在一起，也不可以在最前或最后，
有多少不一样的方法？

那这类题目的一般性

(2) 若 a_1, a_2,..., a_k 为正整数，有多少(a_1,a_2,..., a_k) 满足
    a_1 + a_2 + ... + a_k  = n， n 为正整数。

(4) 若 a_1, a_2,..., a_k 为非负整数，有多少(a_1,a_2,..., a_k) 满足
    a_1 + a_2 + ... + a_k  = n， n 为非负整数。

也就不难解了！

若网友们解决这题目，我会再放新的！

dunwan2tellu

为了鼓励网友们的参与，我打算说，如果谁可以解上面的题目就加分奖励。

dunwan2tellu

我先来抛砖引玉吧！

a) a + b + c = 10 ,a,b,c 为正整数。
这表示 a,b,c>= 1 .
从左右两 -3 那么

(a-1) + (b-1) + (c-1) = 7

设 a-1=A,b-1=B,c-1=C ==> A+B+C = 7 , A,B,C = non-negative integer

有几种方法呢？先考虑 7 个 蛋。现在要把它分给 3 个人（就是我们的 A君，B君和C君），有几种分法？

我们可以用两个“栏”把蛋分成 3 份。比如

O O | O O | O O O  

如你所见 O = 蛋 ， 1 = 栏 。我把“栏”放在蛋中间不就把他们分成 3 份了吗？所以也像等于说 有 7 个 O 和 2 个 1 共有几种排法？
方法就是我们熟悉的 9C2 = 36 .

接下来看其他网友表现了。加油！

[ 本帖最后由 dunwan2tellu 于 7-11-2006 04:10 PM 编辑 ]

hamilan911

原帖由 pipi 于 3-11-2006 03:34 PM 发表
我又来自告奋勇，提一些初等组合的题目与大家分享，目前目标是
每天都放一，两题；为期一个月。


题目:
(1) 若 a, b, c 为正整数，有多少(a,b,c) 满足
    a + b + c  = 10 。
(2) 若 a_1, a_2,..., a_k  ...

既然版主说加分奖励，那我就献丑了。。
只解题目的一般性。。
（4） (n+k-1)C(k-1)               
（2） (n-k+k-1)C(k-1) = (n-1)C(k-1)
解释可以免了吧？

[ 本帖最后由 hamilan911 于 8-11-2006 10:25 PM 编辑 ]

pipi

现在来第 5 题吧！
5）设 S = {1,2,3,...,10}，从 S 选 3 个不连续的号码，有几种不同的方法？

flash

原帖由 hamilan911 于 7-11-2006 04:45 PM 发表

既然版主说加分奖励，那我就献丑了。。
只解题目的一般性。。
（2） (n+k-1)C(k-1)               
（4） (n-k+k-1)C(k-1) = (n-1)C(k-1)
解释可以免了吧？

应该是颠倒了吧。。。。

（2） (n-k+k-1)C(k-1) = (n-1)C(k-1)
（4） (n+k-1)C(k-1)

shingrons

原帖由 pipi 于 8-11-2006 10:46 AM 发表
现在来第 5 题吧！
5）设 S = {1,2,3,...,10}，从 S 选 3 个不连续的号码，有几种不同的方法？

10C3-9*8+8=120-72+8=56
对吧？

shingrons

原帖由 flash 于 8-11-2006 02:23 PM 发表


应该是颠倒了吧。。。。

（2） (n-k+k-1)C(k-1) = (n-1)C(k-1)
（4） (n+k-1)C(k-1)

我真想有人解释解释....请教大侠

pipi

原帖由 shingrons 于 12-11-2006 10:08 PM 发表
10C3-9*8+8=120-72+8=56
对吧？

对了！再来一般性：
6）设 S = {1,2,3,...,n}，从 S 选 k 个不连续的号码，有几种不同的方法？

shingrons

原帖由 pipi 于 13-11-2006 12:01 PM 发表

对了！再来一般性：
6）设 S = {1,2,3,...,n}，从 S 选 k 个不连续的号码，有几种不同的方法？

nCk-(n-k+2)(k-2)+(n-k+1)
对不对？？

pipi

原帖由 shingrons 于 13-11-2006 12:33 PM 发表
nCk-(n-k+2)(k-2)+(n-k+1)
对不对？？

不对!
再试试！也请解释你的答案！

flash

原帖由 pipi 于 13-11-2006 12:01 PM 发表

对了！再来一般性：
6）设 S = {1,2,3,...,n}，从 S 选 k 个不连续的号码，有几种不同的方法？

应该是  (n+1-k)Ck  吧....

pipi

原帖由 flash 于 13-11-2006 06:00 PM 发表
应该是  (n+1-k)Ck  吧....

对了！请解释你的答案！

让我们再看回第 5 题

5）设 S = {1,2,3,...,10}，从 S 选 3 个不连续的号码，有几种不同的方法？

我们知道
（1，3，5） 是其中一组，且 5 - 3 >= 2,  3 - 1 >= 2。
（2，5，9） 是其中一组，且 9 - 5 >= 2， 5 - 2 >= 2。
我们说 （a,b,c）是其中一组, a<b<c,  且 c - b >= 2， b - a >= 2。
在这种情况，我们说（a,b,c），a<b<c，是 2-分离。
有了这个定义，第 5 题也可以问：

5）设 S = {1,2,3,...,10}。S 有几种不同的（a,b,c），a<b<c，是 2-分离的？

也因为这个定义，我们可以再玩玩：

7i）设 S = {1,2,3,...,10}。S 有几种不同的（a,b,c），a<b<c，是 3-分离的？
7ii）设 S = {1,2,3,...,10}。S 有几种不同的（a,b,c），a<b<c，是 4-分离的？
7iii）设 S = {1,2,3,...,10}。S 有几种不同的（a,b,c），a<b<c，是 5-分离的？

明显的，7iii)的答案是 0，因为我们不可能拿到这样的（a,b,c）。

pipi

我给一些3-分离的例子：
(1,4,7), (2,7,10), (4,7,10)

4-分离的例子：
(1,5,9), (1,5,10)

dunwan2tellu

原帖由 pipi 于 14-11-2006 11:43 AM 发表

对了！请解释你的答案！

让我们再看回第 5 题

我们知道
（1，3，5） 是其中一组，且 5 - 3 >= 2,  3 - 1 >= 2。
（2，5，9） 是其中一组，且 9 - 5 >= 2， 5 - 2 >= 2。
我们说 （a,b,c） ...

我来试试看
我当作都是选 3 个号码
7(i) 6C3 = 20
7(ii) 4C3 = 4

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

(n-2k+2)C3