Re: [代數] 非負整數加權和為定值 求解的數目
※ 引述《Asvaghosa (葉)》之銘言：
: 求解大家 最近想到一個問題 本來是一個組合學的問題 也可以轉化成代數形式：
: 若 1 A1 + 2 A2 + 3 A3 + ... + n An = n, Ai 都是非負整數
: 求對於一般正整數n 有幾組 (A1,A2,...,An)?
: 我嘗試用計數法去拆 不過還沒看出端倪。
: 想請問強者這是有解析解的問題嗎? 又如果有改怎麼找關鍵字?
Let S_i = sum_(k=1)^i A_i
then sum_(k=1)^n S_k = n
for all 1<=i<j<=n, 0<=S_i<=S_j
這等同是有0號到n號共n+1個籃子
放n個球進去之後，從左至右編號S_i的情況
因此是重複排列的H(n+1, n) = C(2n, n)種
------------------------------
以上是錯的
不過應該還是可以整理成 S1 + S2 + S3 + ... + Sn = m, S1>=S2>=S3>=...>=Sn>=0
令其解數目是S(n, m) (最後再給n=m)
邊界條件是 S(n, 0) = 1 以及 S(1, m) = 1
對任意S(n, m)，想像有n個空格及m個球
最右邊的空格0顆，有S(n-1, m)種作法
最右邊的空格1顆，把每個空格都扣1顆球，有S(n-1, m-n)種作法
最右邊的空格2柯，把每個空格都扣2顆球，有S(n-1, m-2n)種作法
因此 S(n, m) = S(n-1, n) + S(n-1, n-m) + S(n-1, n-2m) + ...
可是這樣的話 S(n, m-n) 就是 S(n-1, n-m) + S(n-1, n-2m) + ...
所以得到遞迴式 S(n, m) = S(n-1, n) + S(n, m-n)
S(n, m)可以遞迴寫成表格如下
m=0 1 2 3 4 5 6 7 8 9 10 11 12
----------------------------------------
n=1 | 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 1 2 2 3 3 4 4 5 5 6 6 7
3 | 1 1 2 3 4 5 7 8 10 12 14 16 19
4 | 1 1 2 3 5 6 9 11 15 18 23 27 34
5 | 1 1 2 3 5 7 10 13 18 23 30 37 47
6 | 1 1 2 3 5 7 11 14 20 26 35 44 58
7 | 1 1 2 3 5 7 11 15 21 28 38 49 65
8 | 1 1 2 3 5 7 11 15 22 29 40 52 70
S(n, n)是白色的斜線，找不到什麼關係就是了...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.87.238
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1441545844.A.EE0.html
→
09/06 21:43, , 1F
09/06 21:43, 1F
推
09/06 21:56, , 2F
09/06 21:56, 2F
→
09/06 23:04, , 3F
09/06 23:04, 3F
→
09/06 23:10, , 4F
09/06 23:10, 4F
※ 編輯: Desperato (39.12.87.238), 09/06/2015 23:37:58
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：