作者doom8199 (～口卡口卡 修～)
看板Grad-ProbAsk
标题Re: [理工] [离散]-递回
时间Sun Feb 7 20:10:23 2010
※ 引述《assassin88 (2010)》之铭言：
: For n >= 1, let an be the number of ways to write n as an ordered sum of
: positive integer where each summand is at least 2.
: 请问这一题要怎麽想？
: 完全没有idea..麻烦指导了~感谢！
---
假设 x^n 的系数为题目所求
则考虑以下生成函数:
∞
f(x) = Σ (x^2 + x^3 + x^4 + ...)^k
k=1
∞ x^2 k
= Σ ( ───) if ｜x｜<1
k=1 1 - x
∞ 2k ∞ m
= Σ x Σ C(-k,m)*(-x)
k=1 m=0
∞ ∞ m 2k+m
= Σ Σ C(-k,m)*(-1) x
k=1 m=0
(-k)(-k-1)...(-k-m+1)
where C(-k,m)≡ ──────────
m!
m
因此 x^n 的系数 = Σ C(-k,m)(-1)
n=2k+m
[n/2] n-2k
= Σ C(-k,n-2k)(-1)
k=1
即为所求
----
例如当 n=8
有以下拆法:
8
6 + 2
2 + 6
5 + 3
3 + 5
4 + 4
4 + 2 + 2
2 + 4 + 2
2 + 2 + 4
3 + 3 + 2
3 + 2 + 3
2 + 3 + 3
2 + 2 + 2 + 2
共 13种
根据前面的推导
有 C(-1,6) + C(-2,4) + C(-3,2) + C(-4,0)
= 1 + 5 + 6 + 1
= 13 种拆法
希望没搞错题意 OTZ
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.64.93.41
※ 编辑: doom8199 来自: 61.64.93.41 (02/07 20:15)
1F：→ assassin88:答案是对的~可是不懂你生成的式子为什麽是这样列？ 02/07 20:27
2F：→ doom8199:你可以把 x^2、x^3、... 都当成是一个 "物件" 02/07 20:33
3F：→ doom8199:所以 (x^2 + x^3 + x^4 + ...) ← 这样写的意思 02/07 20:33
4F：→ doom8199:就有点像是从中选取一个物件 02/07 20:34
5F：→ doom8199:选到 x^2 就代表吾人选取 2当作一个 summand 02/07 20:34
6F：→ doom8199:k次方的意思，可以解读成 "把n这个数拆成 k个数字" 02/07 20:36
7F：推 assassin88:我懂你的意思了~不过第三个等式後面怎麽变出来的= = 02/07 20:37
8F：→ doom8199:因为可以只拆一个数字，也能拆多个数字 02/07 20:37
9F：→ assassin88:(1-x)^-n不是等於ΣC(n+r-1 r)x^r 吗>? 02/07 20:38
10F：→ doom8199:都对阿，那个是利用泰勒展开得来的 02/07 20:40
11F：→ doom8199:我只是习惯这种写法= =a 02/07 20:40
12F：推 assassin88:我可能等级太低..不知道怎麽从同变数拆出两个(k,m)ˊˋ 02/07 20:42
13F：→ doom8199:你那样写是把 (-1)^r 并到 C(-n,r) 得来的 02/07 20:42
14F：→ assassin88:我指的是..他们原本不是都同属Σk=1~~怎麽拆成两个的? 02/07 20:45
15F：→ doom8199:不太懂 = =ll ,你是指哪一步有问题? 02/07 20:49
16F：推 assassin88:ㄜ..第三个等号後面Σm..这边原本不是都k? 该怎麽使用 02/07 20:55
17F：→ doom8199:就泰勒展开，有时候会把它当成广义的二项式定理 02/07 20:58
18F：→ doom8199:接着就是算出 x^n 项的系数 02/07 21:00
19F：→ doom8199:因此只要把满足 n=2k+m 的所有 (k,m)都算出来即可 02/07 21:01
20F：推 EntHeEnd:这是利用生成函数解整数分割问题吧 ? 02/07 21:05
21F：推 JMD:问一下d大是数学系的吗? 02/07 21:28
22F：→ doom8199:不是XD 02/07 21:32
23F：→ assassin88:我研究不出来= = ... 这是越级打怪吗XD 02/07 21:37
24F：→ doom8199:(1-x)^(-k) = Σ C(-k,m)*(-x)^m 这个@@? 02/07 21:46
26F：→ doom8199:往下拉到 Newton's generalized binomial theorem 02/07 21:47
27F：→ doom8199:型态跟维基百科上的 (x+y)^r 展开式完全一样 02/07 21:48
28F：→ doom8199:对应上面的符号，就是 (x,y,r) ←→ (1,-x,-n) 02/07 21:49
29F：→ doom8199:打错，是 (x,y,r) ←→ (1,-x,-k) 02/07 21:50
30F：推 assassin88:我的意思是 变数可以换?原来上一式是k..下面可以转成m? 02/07 21:58
31F：→ doom8199:不懂你的问题所在 OTZ 02/07 22:09