回復 25# koeagle 的帖子
14. n ∈ N,則 C(n,1) + 2² C(n,2) + 3² C(n,3) + ... + n² C(n,n) = ?
解四:
想法: 為所求式構思一個計數的模型,再利用 double counting ("算兩次") 解之。
所求式意義: 今有 n 個人,欲由若干人組隊參加益智問答比賽。該賽事有 2 題,每題限由 1 人回答,答題者可重複 ⇒ 隊伍陣容與答題者的組合數。
所求式是先考慮組隊方式,再考慮答題者。現改為: 先考慮答題者,再由其它人選出答題者的隊友,則方法數為
恰 1 人答題的方法 + 恰 2 人答題的方法
= n*2ⁿ⁻¹ + n(n-1)*2ⁿ⁻²
理論上這個推論過程只適合於 n ≥ 2,故對於 n = 1 應另行說明。
這個方法可以較易地推至更高次方,例如 n ∈ N,求
C(n,1) + 2³ C(n,2) + 3³ C(n,3) + ... + n³ C(n,n)
= 恰 1 人答題的方法 + 恰 2 人答題的方法 + 恰 3 人答題的方法
= n*2ⁿ⁻¹ + 3n(n-1)*2ⁿ⁻² + n(n-1)(n-2)*2ⁿ⁻³
當然,大家所熟悉的
C(n,1) + 2* C(n,2) + 3* C(n,3) + ... + n* C(n,n) = n*2ⁿ⁻¹
也可以用這個想法得出。