有關V同學前兩天問的那題今年台大的離散, 題目如下：
我回的時候只寫了一般遞迴的解法
忘記提醒同學若要用生成函數求和算子該怎麼做了
我把解法大概跟同學說一下:
Sn = t1 + ... + tn, 其中 tn = 1 + 2 + ... +n
欲求Sn, 令T(x)為tn的生成函數, t0 = 0
則 S(x) = T(x)/(1-x) 為Sn之生成函數
T(x) = ∑ [(n^2 + n)/2] x^n, n = 0~∞
求解T(x)這個應該沒甚麼問題,
把兩項拆開, 分別作一下微分可導出
T(x) = (1/2)*(x(1+x)/(1-x)^3 + x/(1-x)^2)
T(x)求出來S(x)也就沒問題了
求x^n之係數, 可得
s_n = [c(n+2,n-1)+c(n+1,n-2)+c(n+1,n-1)]/2
= [(n+2)(n+1)n/6 + (n+1)n(n-1)/6 + (n+1)n/2]/2
將 n 用 1 代入可求得係數和 a0 + a1 + a2 + ... = 1
我回的時候只寫了一般遞迴的解法
忘記提醒同學若要用生成函數求和算子該怎麼做了
我把解法大概跟同學說一下:
Sn = t1 + ... + tn, 其中 tn = 1 + 2 + ... +n
欲求Sn, 令T(x)為tn的生成函數, t0 = 0
則 S(x) = T(x)/(1-x) 為Sn之生成函數
T(x) = ∑ [(n^2 + n)/2] x^n, n = 0~∞
求解T(x)這個應該沒甚麼問題,
把兩項拆開, 分別作一下微分可導出
T(x) = (1/2)*(x(1+x)/(1-x)^3 + x/(1-x)^2)
T(x)求出來S(x)也就沒問題了
求x^n之係數, 可得
s_n = [c(n+2,n-1)+c(n+1,n-2)+c(n+1,n-1)]/2
= [(n+2)(n+1)n/6 + (n+1)n(n-1)/6 + (n+1)n/2]/2
將 n 用 1 代入可求得係數和 a0 + a1 + a2 + ... = 1
