作者fragmentwing (片翼碎夢)
看板Math
標題[離散] 生成函數 r個相同球 n個相異箱子
時間Thu Nov 19 11:30:36 2020
有個地方不太懂，他的說明是這樣講的：
箱子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://webptt.com/m.aspx?n=bbs/Math/M.1605756639.A.3A9.html
1F：→ hwanger : 先不管是不是總共r顆球這件事 令f1=f2=...=fn= 11/19 11:48
2F：→ hwanger : 1+x+x^2+...+x^r=c0+c1*x+c2*x^2+...+cr*x^r 11/19 11:50
3F：→ hwanger : 則在fk的係數c_i則如你所述 是在第k個箱子可以放i顆 11/19 11:52
4F：→ hwanger : 球的情況數 (ci都是1 代表情況數都只有一種) 11/19 11:54
5F：→ hwanger : 現在考慮A(x)=f1*f2*...*fn=d0+d1*x+d2*x^2+... 11/19 11:56
6F：→ hwanger : 則A(x)的第j項係數dj代表的是這n個箱子的球總數為j 11/19 11:58
7F：→ hwanger : 時的情況數 這是因為dj= Σc{i1}*c{i2}*...*c{in} 11/19 12:00
8F：→ hwanger : where the sum runs over all i1,i2,...,in with 11/19 12:01
9F：→ hwanger : i1+i2+...+in=j 11/19 12:02
10F：→ hwanger : 若看其中每一項c{i1}*c{i2}*...*c{in} 則其意義為 11/19 12:03
11F：→ hwanger : {第一個箱子有i1顆球的情況數}*...*{第n個箱子有in 11/19 12:04
12F：→ hwanger : 顆球的情況數} 所以總球數是i1+i2+...+in=j 11/19 12:06
13F：→ hwanger : 而sum起來就代表了總球數為j時的所有可能情況數 11/19 12:08
14F：→ hwanger : 所以如果我們要看"r個相同球 n個相異箱子" 那就只看 11/19 12:09
15F：→ hwanger : dr這個數 也就是A(x)中 x^r的係數即可 11/19 12:10
16F：→ fragmentwing: 感謝h大 我搞懂了 11/19 12:10
17F：→ fragmentwing: 例如說A(x)中 x^3 11/19 12:11
18F：→ fragmentwing: 那就是000111 300000等等 全部組合起來的狀況 11/19 12:12
19F：→ hwanger : 1. 你說的沒錯 當箱子no.1放入r顆球時 其他箱子再放 11/19 12:12
20F：→ fragmentwing: 各箱子次方乘起來時 係數也相乘 加總起來 11/19 12:13
21F：→ fragmentwing: 就會對應到A(x)中該次方總和相同的係數 11/19 12:13
22F：→ hwanger : 入球時 球的總數就超過r個 但此時他所貢獻的是更高 11/19 12:14
23F：→ hwanger : 次的係數 11/19 12:14
24F：→ fragmentwing: 而例如r+1次時 總球數是r+1而非r 11/19 12:15
25F：→ hwanger : 2.這個問題等價於e1+e2+...+en=r, 0<=ei<=r的解個數 11/19 12:15
26F：→ fragmentwing: A(x)表示的是球總數有多少時對應方法數 11/19 12:16
27F：→ hwanger : [11/19 12:12][11/19 12:15]你的回文>>>沒錯 11/19 12:17
28F：→ hwanger : [11/19 12:16]也沒錯 11/19 12:17