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

[fragmentwing (片翼碎夢)]

有個地方不太懂，他的說明是這樣講的：

箱子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
→ hwanger     : 先不管是不是總共r顆球這件事 令f1=f2=...=fn=
→ hwanger     : 1+x+x^2+...+x^r=c0+c1*x+c2*x^2+...+cr*x^r
→ hwanger     : 則在fk的係數c_i則如你所述 是在第k個箱子可以放i顆
→ hwanger     : 球的情況數 (ci都是1 代表情況數都只有一種)
→ hwanger     : 現在考慮A(x)=f1*f2*...*fn=d0+d1*x+d2*x^2+...
→ hwanger     : 則A(x)的第j項係數dj代表的是這n個箱子的球總數為j
→ hwanger     : 時的情況數 這是因為dj= Σc{i1}*c{i2}*...*c{in}
→ hwanger     : where the sum runs over all i1,i2,...,in with
→ hwanger     : i1+i2+...+in=j
→ hwanger     : 若看其中每一項c{i1}*c{i2}*...*c{in} 則其意義為
→ hwanger     : {第一個箱子有i1顆球的情況數}*...*{第n個箱子有in
→ hwanger     : 顆球的情況數} 所以總球數是i1+i2+...+in=j
→ hwanger     : 而sum起來就代表了總球數為j時的所有可能情況數
→ hwanger     : 所以如果我們要看"r個相同球 n個相異箱子" 那就只看
→ hwanger     : dr這個數 也就是A(x)中 x^r的係數即可
→ fragmentwing: 感謝h大 我搞懂了
→ fragmentwing: 例如說A(x)中 x^3
→ fragmentwing: 那就是000111 300000等等 全部組合起來的狀況
→ hwanger     : 1. 你說的沒錯 當箱子no.1放入r顆球時 其他箱子再放
→ fragmentwing: 各箱子次方乘起來時 係數也相乘 加總起來
→ fragmentwing: 就會對應到A(x)中該次方總和相同的係數
→ hwanger     : 入球時 球的總數就超過r個 但此時他所貢獻的是更高
→ hwanger     : 次的係數
→ fragmentwing: 而例如r+1次時 總球數是r+1而非r
→ hwanger     : 2.這個問題等價於e1+e2+...+en=r, 0<=ei<=r的解個數
→ fragmentwing: A(x)表示的是球總數有多少時對應方法數
→ hwanger     : [11/19 12:12][11/19 12:15]你的回文>>>沒錯
→ hwanger     : [11/19 12:16]也沒錯