✔ 最佳答案
Sn ={1,2,3,…n}
S 為Sn的非空子集
考慮n,n-1,n-2,…,m,…,3,2,1中的m值,有n-m數個比m大,m-1個數比m小.
若子集S只有一個元素,則會有一個S包含m,而在求f({m})時m必排第一,
所以f({m}) = m*1
若S有2個元素,則m排第一的組合有(m-1)C1個(因二個元素中要包含一個m,另一個一定要比m小)。
若S有3個元素,則m排第一的組合有(m-1)C2,諸如此類.
因此m排第一的可能組合共 1 + (m-1)C1 + (m-1)C2 + … + (m-1)C(m-1) = 2^(m-1)個
[考慮(1+x)^(m-1)展開式及代入x=1求得]
以相同邏輯求m排第三的可能組合:
S最小有三個元素. 三個元素時,m排第三的組合,條件是要比m大的有兩個,比m小的0個,即(n-m)C2 * (m-1)C0個組合
S四個元素時,排第三的組合:比m大的有兩個,比m小的一個,即(n-m)C2 * (m-1)C1.
諸如此類…
因此m排第三的可能組合共(n-m)C2*(m-1)C0 + (n-m)C2*(m-1)C1 + (n-m)C2*(m-1)C2 + … + (n-m)C2*(m-1)C(m-1) = (n-m)C2*2^(m-1)
m排單數(排第一,第三,第五,,…)共2^(m-1)[1 + (n-m)C2 + (n-m)C4 + (n-m)C6 + …]個組合
m排雙數共2^(m-1)[(n-m)C1 + (n-m)C3 + (n-m)C5 + …]個組合
在∑f(s)關乎m的計算中,若m排單數則為正, m排雙數則為負.
因此m相關計算 = {2^(m-1)[1 + (n-m)C2 + (n-m)C4 + (n-m)C6 + …] - 2^(m-1)[n-m)C1 + (n-m)C3 + (n-m)C5 + …]} * m
考慮(1 + x)^(n-m)展開式及代入x = -1, [1 + (n-m)C2 + (n-m)C4 + (n-m)C6 + …] - [n-m)C1 + (n-m)C3 + (n-m)C5 + …] = 0,除非n = m.
換句話說,除了n以外,其他所有Sn的元素在計算∑f(s)時的淨值都是0.
當S有一個元素時,n排第一的組合有一個, 當S有2個元素時,n排第一的組合(n-1)C1個, 當S有3個元素時,n排第一的組合(n-1)C2個,…,所以n排第一的組合共1+(n-1)C1 + (n-1)C2 + … + (n-1)C(n-1) = 2^(n-1)
∑f(s) = (n)[2^(n-1)]
例: S4 = {1,2,3,4}
f({1}) = 1; f({2}) = 2; f({3}) = 3; f({4}) = 4
f({1,2}) = 1; f({1,3}) = 2; f({1,4}) = 3;
f({2,3}) = 1; f({2,4}) = 2; f({3,4}) = 1;
f({1,2,3}) = 2; f({1,2,4}) = 3; f({1,3,4}) = 2; f({2,3,4}) = 3
f({1,2,3,4}) = 2
∑f(S) = 1+2+3+4+1+2+3+1+2+1+2+3+2+3+2 = 32 = (4)[2^(4-1)]