推 lio00567 :感謝！！ 10/23 13:46
※ 引述《lio00567 (隨便)》之銘言：
: Give a combinational proof that if n is a positive integer,then
: n
: Σ k^2(n,K)=n(n+1)2^(n-2)
: k=1
: 想了好久都想不出來 麻煩各位大大解惑了!!
題目要的是一個 combinatorial proof...
(以下的 Σ 都是 k 從 1 到 n; 敘述中有關 k 的都是要從 1 到 n 全部算進去)
Σk^2 C(n,k) 表示 n 個東西中取 k 個後在這 k 個當中可重覆地選兩個
這樣的選法數如果先考慮選兩個的話有 n^2 種 (因為可重覆)
其中 n 種選到同一樣東西 這樣補到 k 個的補法有 ΣC(n-1,k-1) = 2^(n-1) 種
另外 n^2-n 種選到不同的東西 這樣補到 k 個的補法有 ΣC(n-2,k-2) = 2^(n-2) 種
故全部共有 n * 2^(n-1) + (n^2-n) * 2^(n-2)
= 2^(n-2) [2n + n^2 - n]
= (n^2 + n) 2^(n-2)
= n(n+1) 2^(n-2) 種 證畢
--
実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」
亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」
実琴：「難道你沒有男人的尊嚴了嗎?!」
亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」
－－プリンセス・プリンセス 第二話
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.218.108.125