[離散] 生成函數 r個相同球 n個相異箱子

看板Math作者 (片翼碎夢)時間3年前 (2020/11/19 11:30), 編輯推噓0(0推 0噓 28→)
留言28則, 2人參與, 3年前最新討論串1/1
有個地方不太懂，他的說明是這樣講的： 箱子no.1之GF:1+x+x^2+...+x^r 到 箱子no.n 1代表可放顆數0，x代表可放顆數1，x^r代表可放顆數r 總共情形之GF A(x)=(1+x+x^2+...+x^r)^n 他這個總結讓我覺得有點奇怪 比如說 箱子no.1放入r顆時 其他箱子就不會放入球 可是如果把A(x)展開 那就會得出箱子no.1有r顆球乘上其他箱子有球的狀況 不知道要怎麼理解這個A(x)會比較好 求板上大大幫忙 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.212.52 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1605756639.A.3A9.html
→
11/19 11:48, 3年前 , 1F
先不管是不是總共r顆球這件事 令f1=f2=...=fn=
11/19 11:48, 1F
→
11/19 11:50, 3年前 , 2F
1+x+x^2+...+x^r=c0+c1*x+c2*x^2+...+cr*x^r
11/19 11:50, 2F
→
11/19 11:52, 3年前 , 3F
則在fk的係數c_i則如你所述 是在第k個箱子可以放i顆
11/19 11:52, 3F
→
11/19 11:54, 3年前 , 4F
球的情況數 (ci都是1 代表情況數都只有一種)
11/19 11:54, 4F
→
11/19 11:56, 3年前 , 5F
現在考慮A(x)=f1*f2*...*fn=d0+d1*x+d2*x^2+...
11/19 11:56, 5F
→
11/19 11:58, 3年前 , 6F
則A(x)的第j項係數dj代表的是這n個箱子的球總數為j
11/19 11:58, 6F
→
11/19 12:00, 3年前 , 7F
時的情況數 這是因為dj= Σc{i1}*c{i2}*...*c{in}
11/19 12:00, 7F
→
11/19 12:01, 3年前 , 8F
where the sum runs over all i1,i2,...,in with
11/19 12:01, 8F
→
11/19 12:02, 3年前 , 9F
i1+i2+...+in=j
11/19 12:02, 9F
→
11/19 12:03, 3年前 , 10F
若看其中每一項c{i1}*c{i2}*...*c{in} 則其意義為
11/19 12:03, 10F
→
11/19 12:04, 3年前 , 11F
{第一個箱子有i1顆球的情況數}*...*{第n個箱子有in
11/19 12:04, 11F
→
11/19 12:06, 3年前 , 12F
顆球的情況數} 所以總球數是i1+i2+...+in=j
11/19 12:06, 12F
→
11/19 12:08, 3年前 , 13F
而sum起來就代表了總球數為j時的所有可能情況數
11/19 12:08, 13F
→
11/19 12:09, 3年前 , 14F
所以如果我們要看"r個相同球 n個相異箱子" 那就只看
11/19 12:09, 14F
→
11/19 12:10, 3年前 , 15F
dr這個數 也就是A(x)中 x^r的係數即可
11/19 12:10, 15F
→
11/19 12:10, 3年前 , 16F
感謝h大 我搞懂了
11/19 12:10, 16F
→
11/19 12:11, 3年前 , 17F
例如說A(x)中 x^3
11/19 12:11, 17F
→
11/19 12:12, 3年前 , 18F
那就是000111 300000等等 全部組合起來的狀況
11/19 12:12, 18F
→
11/19 12:12, 3年前 , 19F
1. 你說的沒錯 當箱子no.1放入r顆球時 其他箱子再放
11/19 12:12, 19F
→
11/19 12:13, 3年前 , 20F
各箱子次方乘起來時 係數也相乘 加總起來
11/19 12:13, 20F
→
11/19 12:13, 3年前 , 21F
就會對應到A(x)中該次方總和相同的係數
11/19 12:13, 21F
→
11/19 12:14, 3年前 , 22F
入球時 球的總數就超過r個 但此時他所貢獻的是更高
11/19 12:14, 22F
→
11/19 12:14, 3年前 , 23F
次的係數
11/19 12:14, 23F
→
11/19 12:15, 3年前 , 24F
而例如r+1次時 總球數是r+1而非r
11/19 12:15, 24F
→
11/19 12:15, 3年前 , 25F
2.這個問題等價於e1+e2+...+en=r, 0<=ei<=r的解個數
11/19 12:15, 25F
→
11/19 12:16, 3年前 , 26F
A(x)表示的是球總數有多少時對應方法數
11/19 12:16, 26F
→
11/19 12:17, 3年前 , 27F
[11/19 12:12][11/19 12:15]你的回文>>>沒錯
11/19 12:17, 27F
→
11/19 12:17, 3年前 , 28F
[11/19 12:16]也沒錯
11/19 12:17, 28F
‣ 更多 fragmentwing 的文章
文章代碼(AID): #1VjURVEf (Math)