作者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/cn.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