Re: [中學] 101家齊─重複組合問題

[ckchi (飄)]

※ 引述《maskangel ()》之銘言：
: 填充7
: 將相同大小的20 顆紅球、20 顆黑球、20 顆白球，分成各30 個的兩堆，
: 試問有幾種不同分法??
: Ans:166
: 麻煩各位大大了~感激不盡~

考慮 A 堆的取球法：

紅球 20 個 : 剩下10個餘額分給黑和白，共11種分法 (黑0~10)
     19    :     11                    12       (黑0~11)
      .           .                     .
      .           .                     .
      .           .                     .
     11    :     19                    20        (黑0~19)
     10    :     20                    21        (黑0~20)
      9    : 剩下21個餘額分給黑和白，但單色最多20個！，共20種分法 (黑1~20)
      8    :     22                                      19       (黑2~20)
      .           .                                       .
      .           .                                       .
      .           .                                       .
      0    :     30                                      11       (黑10~20)

所以共 11+12+...+20+21+20+...+11 種
     = 2*[(11+20)*10/2] + 21
     = 331 種

然而，這種算法其實是有重複的
ex: A取 10 15  5 / B剩 10  5 15
    A取 10  5 15 / B剩 10 15  5
上面兩組其實是一樣的
因此最後在算時要除以2

但其中當A和B完全相等這一組 (A:10 10 10 / B:10 10 10)是沒重覆算到的
因此總共有：

(331-1)/2 + 1 = 166 種分堆法

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.116.89.133
→ geniuskoj   :前面可用H算 H(3,30)-3H(3,9)=331
推 maskangel   :謝謝C大與G大~感激不盡~
推 thisday     :推兩位大大^^  g大的作法讓我回憶起骰子和的問題^^
推 peter579    :但看不出為何是  H(3,9)
推 thisday     :x1+x2+x3=30     xi介於0~20之間
→ thisday     :先 C3取1 選某個x  放21在他裡面
→ thisday     :剩下的就是30-21=9
→ maskangel   :令其中一個為(x1+21)+x2+x3=30
→ maskangel   :之非負整數解