Re: [理工] [離散]-遞迴

看板Grad-ProbAsk作者 (～口卡口卡　修～)時間14年前 (2010/02/07 20:10), 編輯推噓6(6推 0噓 25→)
留言31則, 4人參與, 最新討論串10/19 (看更多)
※ 引述《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)
→
02/07 20:27, , 1F
答案是對的~可是不懂你生成的式子為什麼是這樣列？
02/07 20:27, 1F
→
02/07 20:33, , 2F
你可以把 x^2、x^3、... 都當成是一個 "物件"
02/07 20:33, 2F
→
02/07 20:33, , 3F
所以 (x^2 + x^3 + x^4 + ...) ← 這樣寫的意思
02/07 20:33, 3F
→
02/07 20:34, , 4F
就有點像是從中選取一個物件
02/07 20:34, 4F
→
02/07 20:34, , 5F
選到 x^2 就代表吾人選取 2當作一個 summand
02/07 20:34, 5F
→
02/07 20:36, , 6F
k次方的意思，可以解讀成 "把n這個數拆成 k個數字"
02/07 20:36, 6F
推
02/07 20:37, , 7F
我懂你的意思了~不過第三個等式後面怎麼變出來的= =
02/07 20:37, 7F
→
02/07 20:37, , 8F
因為可以只拆一個數字，也能拆多個數字
02/07 20:37, 8F
→
02/07 20:38, , 9F
(1-x)^-n不是等於ΣC(n+r-1 r)x^r 嗎>?
02/07 20:38, 9F
→
02/07 20:40, , 10F
都對阿，那個是利用泰勒展開得來的
02/07 20:40, 10F
→
02/07 20:40, , 11F
我只是習慣這種寫法= =a
02/07 20:40, 11F
推
02/07 20:42, , 12F
我可能等級太低..不知道怎麼從同變數拆出兩個(k,m)ˊˋ
02/07 20:42, 12F
→
02/07 20:42, , 13F
你那樣寫是把 (-1)^r 併到 C(-n,r) 得來的
02/07 20:42, 13F
→
02/07 20:45, , 14F
我指的是..他們原本不是都同屬Σk=1~~怎麼拆成兩個的?
02/07 20:45, 14F
→
02/07 20:49, , 15F
不太懂 = =ll ,你是指哪一步有問題?
02/07 20:49, 15F
推
02/07 20:55, , 16F
ㄜ..第三個等號後面Σm..這邊原本不是都k? 該怎麼使用
02/07 20:55, 16F
→
02/07 20:58, , 17F
就泰勒展開，有時候會把它當成廣義的二項式定理
02/07 20:58, 17F
→
02/07 21:00, , 18F
接著就是算出 x^n 項的係數
02/07 21:00, 18F
→
02/07 21:01, , 19F
因此只要把滿足 n=2k+m 的所有 (k,m)都算出來即可
02/07 21:01, 19F
推
02/07 21:05, , 20F
這是利用生成函數解整數分割問題吧 ?
02/07 21:05, 20F
推
02/07 21:28, , 21F
問一下d大是數學系的嗎?
02/07 21:28, 21F
→
02/07 21:32, , 22F
不是XD
02/07 21:32, 22F
→
02/07 21:37, , 23F
我研究不出來= = ... 這是越級打怪嗎XD
02/07 21:37, 23F
→
02/07 21:46, , 24F
(1-x)^(-k) = Σ C(-k,m)*(-x)^m 這個@@?
02/07 21:46, 24F
→
02/07 21:46, , 25F
02/07 21:46, 25F
→
02/07 21:47, , 26F
往下拉到 Newton's generalized binomial theorem
02/07 21:47, 26F
→
02/07 21:48, , 27F
型態跟維基百科上的 (x+y)^r 展開式完全一樣
02/07 21:48, 27F
→
02/07 21:49, , 28F
對應上面的符號，就是 (x,y,r) ←→ (1,-x,-n)
02/07 21:49, 28F
→
02/07 21:50, , 29F
打錯，是 (x,y,r) ←→ (1,-x,-k)
02/07 21:50, 29F
推
02/07 21:58, , 30F
我的意思是 變數可以換?原來上一式是k..下面可以轉成m?
02/07 21:58, 30F
→
02/07 22:09, , 31F
不懂你的問題所在 OTZ
02/07 22:09, 31F
‣ 更多 doom8199 的文章
文章代碼(AID): #1BRgsoC1 (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 10 之 19 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共19篇)
‣ 更多 doom8199 的文章
文章代碼(AID): #1BRgsoC1 (Grad-ProbAsk)