趣味组合问题 :)

dunwan2tellu

几好玩一下的组合题目  

1)

(i)水果店里有卖 5 种不同的水果。若你要买 8 个水果(可以不买某些水果) ,那么共有几种方法买呢?

(ii)条件用第(i)题，但是现在每一种水果必须买至少一个。

(iii)条件还是和第(i)题一样 ，不过，请问若你任意买 8 个水果时，里面包含了五种不同水果的机率是多少呢?

dunwan2tellu

2)

某人书房有３个不同的书橱。某天那人买了 10 本不同的书籍想将它们放置在那 3 个书橱里。若允许有空书橱，且必须考虑书摆放的位置(比如橱1 里有放两本书 A,B . 那么AB 和 BA 是不同的排法.),请问共有几种方法放置书本呢 ?

dunwan2tellu

3)

相信每个人都知道Fibbonanci Number 吧？ 1,2,3,5,8,13,21...
或一般来说 F_n = F_{n-1} + F_{n-2}  , n>= 3

考虑一个有Fibbonanci Number 组合而成的集合 ，S

S = {1,2,3,5,8,13,21,34,55,89,144}

(i)请问自然数 1 到 144 , 有几个数不能以 S 里两个不同的元素的和来表示 ? (比如143 就不能)

(ii) 若 S = {1,2,3,5...., F_n} , F_n 为第n个Fibbonanci Number.
那么自然数 1 到 F_n 又有几个数不能以 S 里两个不同的元素的和来表示呢？(这是把(i)的题目一般化,generalised)

hamilan911

1)
i)方法 = 5H8 = 12C8 = 495

ii)方法 = 5H3 = 7C3 = 35

iii)机率 = 5H3 / 5H8 = 35/495 = 7/99

hamilan911

2)方法 = 3H10 x 10! = 12C10 x 10! =  239500800

hamilan911

3)
i)144 - 9 - 9(10)/2 = 90
  已知{3.....144}都能被任何两个S元素的和来表示,即9个。
  设那两个S的元素为{1，x} ,则能被任何两个S元素的和来表示的数字有9个。即{1，3}，{1，5}，{1,8}....
  而当两个S的元素为{2，x}，则能被任何两个S元素的和来表示的数字有8个。即{2，5}，{2,8}....
  以此类推。。。。
  即1+2+3+4...9 = 9(10)/2


ii)数量 = F_n - (n-2) - (n-2)(n-1)/2

[ 本帖最后由 hamilan911 于 28-11-2005 09:38 PM 编辑 ]

dunwan2tellu

1,2 的解答有给解释会较好。

3 的题目你 -9 因为 {3,5,8,..,144}可以用两个Fibbonanci 的和来表示。不过这其实已经包括在 10(9)/2 里面了

hamilan911

谢谢提醒，其实昨晚也发觉到错误了。
3)
i)144 - 9 - 8(9)/2 = 99
  已知{3.....144}都能被任何两个S元素的和来表示,即9个。
  设那两个S的元素为{1，x} ,则能被任何两个S元素的和来表示的数字有8个。即{1，3}，{1，5}，{1,8}....{1，89}
  而当两个S的元素为{2，x}，则能被任何两个S元素的和来表示的数字有7个。即{2，5}，{2,8}....{2，89}
  以此类推。。。。
  即1+2+3+4...8 = 8(9)/2 = 36
  也可简化为144 - 9(10)/2 = 99

ii)数量 = F_n - (n-2) - (n-3)(n-2)/2
        = F_n - (n-2)(n-1)/2

[ 本帖最后由 hamilan911 于 29-11-2005 10:20 AM 编辑 ]

hamilan911

1)
i)把题目化为 a+b+c+d+e = 8
  用5H8来解题,nHr = (n+r-1)Cr
  所以5H8 = 12C8 = 495
ii)由于每一种水果必须买至少一个，所以把题目化为a+b+c+d+e = 3
   用5H3解题。
   5H3 = 7C3 = 35
iii)这题机率的情况其实就是(ii)/(i)

2）a+b+c = 10
   先用3H10。
   由于有关系到书本的排法，所以必须乘上10!
   即 3H10 x 10!

whitelighter

1.
i)有和hamilan911不同的意见…
不是应该5^8吗？
因为
---------------------------------
| 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
---------------------------------
既是，每一次，买者可以选择5种水果里面的其中一种。（当做你买八次的水果）

ii)应该是(5^4)*4!
也和上一个一样…只是，到了最后，买者就必须买5个其中一个，然后4个其中一个…如此类推吧…

iii)这…是(ii)/(i)

我的做法…好象有点错的…但是哦，什么是nHr？？？

whitelighter

2)
220*10!
吗？？？！！！

hamilan911

原帖由 whitelighter 于 29-11-2005 11:52 AM 发表
1.
i)有和hamilan911不同的意见…
不是应该5^8吗？
因为
---------------------------------
| 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
---------------------------------
既是，每一次，买者可以选择5种水果里 ...

你的做法错了，你的做法使用permutation的，关系到排法，可是问题根本与permutation没关系。。。

其实nCr和nHr的不同在于nHr可以所谓的不“摆放”进去，而nCr就要。。。
解释有点含糊，明白吗？？

whitelighter

不是很明白nHr的…有比较详细的解释吗？

顺便问一下哦…这个题目…
Residents at a bording school can choose either fish or bacon or egg or sausage as breakfast. In how many ways can a man arrange his breakfast for a week?
题目取自Advanced Algebra Vol. 1 by Durell。

它的解答是4^7…我开始做第一题时，也很怀疑自己的解答。后来再看看Durell的解释…不知道，Durell的题目和第一题有何差别…导致做法不同呢？

hamilan911

Durell这题不一样，因为题目注明or，每天只可选一样作为早餐,所以这题只是纯粹的4^7。
而那题买水果的是说买五样水果（有些可以不买），共买8个。
设那五样水果为a,b,c,d,e。
a+b+c+d+e = 8    a,b,c,d,e >= 0
所以（a,b,c,d,e）可以等于（8,0,0,0,0) , (6,1,0,1,0) , (2,2,2,1,1) , (4,2,2,0,0)等等。。。
这就要用到nHr。
a+b+c+d+e = 8
n = 5    r = 8
nHr = (n+r-1)Cr
所以5H8 = 12C8

dunwan2tellu

让我来做较具体的解释吧。

有5种水果，买8个。

想象你已买了8个水果 ,称他们为 Fruit (F) 。

F F F F F F F F

现在你把这8个F分类成五个部分(每个部分有同样的水果),那么你就需要 4 个分割栏。Example

F F | F | F F | F | F F

所以你现在共有(8+4=)12 样"物品" ,8 个 F 和 ４ 个 | 。题目就变成 排列上面的物品的方法，也就是 12C4 = 495

whitelighter

明白了！谢谢。。。不错的题目。。。开学后就要拿回这些course了，趁现在可以活动、活动脑筋。。。

dunwan2tellu

这里有题组合题目，我还没想到如何解，就放上来大家一起想吧。

集合 A = {1,2,3...,150}
集合 B = {x*y | x,y ε A ,x =/= y}  

请问集合 B里有多少个元素(elements)呢?

注释 :

* = 乘
ε  = is element of

必须小心的就是，9*2 = 6*3 = 18 . 虽然 (x,y)=(9,2),(6,3)ε A ,但是他们乘起来是一样的(=18)，所以这只算是 B 里的一个元素罢了。

dunwan2tellu

我又来了！组合题目万岁！哈哈

某某中学有一班，里面共有１２个学生。而且，这１２个学生竟然是６个双胞胎！某天，老师想把他们分组比赛。不过他不希望每对双胞胎在同一组，那么

(i) 若老师要分成两组A,B(每组6人)的话有几种方法？

(ii)若老师只是要分成两组罢了又有几种方法？

(iii)若老师要分成三组A,B,C(每组4人)有几种方法？

(iv)若老师要两人一组，有几种方法？

dunwan2tellu

zomok 没人来test看的 >.< ... 这里还有另一个问题：

从0开始一直写到 100 , 请问 1 出现几次?

写到 1000 呢 ？100000 呢 ？甚至是 10^1000 呢 ？ 大家不妨试试看。解法很简单一下哦！

hamilan911

原帖由 dunwan2tellu 于 11-12-2005 05:56 PM 发表
zomok 没人来test看的 >.< ... 这里还有另一个问题：

从0开始一直写到 100 , 请问 1 出现几次?

写到 1000 呢 ？100000 呢 ？甚至是 10^1000 呢 ？ 大家不妨试试看。解法很简单一下哦！

0到100，1出现21次。。。
0到1000，1出现301次。。。
100 = 10^2
算法= 2 x 10^(2-1) + 1

General formula = n x 10^(n-1) + 1