作者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