|
|
kuing
Posted at 2014-1-12 18:21:04
对于 $[1,n]$ 中的某个整数 $k$，在 $\{1,2,\ldots,n\}$ 的所有非空子集中，以 $k$ 作为最大元素的集合个数等于集合 $\{1,2,\ldots,k-1\}$ 的子集个数，共 $2^{k-1}$ 个；以 $k$ 作为最小元素的集合个数等于集合 $\{k+1,k+2,\ldots,n\}$ 的子集个数，共 $2^{n-k}$ 个。
（注：当 $k=1$ 或 $n$ 时容易验证也符合此数目，故不必另作讨论）
故此在所有的 $G(B)$ 中，$k$ 共出现了 $2^{k-1}+2^{n-k}$ 次，因此，设所有 $G(B)$ 的和为 $S$，则
\begin{align*}
S&=\sum_{k=1}^nk(2^{k-1}+2^{n-k})\\
& =\sum_{k=1}^nk2^{k-1}+\sum_{k=1}^nk2^{n-k} \\
& =\sum_{k=1}^nk2^{k-1}+\sum_{k=1}^n(n+1-k)2^{n-(n+1-k)} \\
& =\sum_{k=1}^nk2^{k-1}+\sum_{k=1}^n(n+1-k)2^{k-1} \\
& =(n+1)\sum_{k=1}^n2^{k-1} \\
& =(n+1)(2^n-1),
\end{align*}
而 $G(B)$ 共有 $2^n-1$ 个，故所求的平均值就是 $n+1$。 |
|
goft
Posted at 2014-1-12 18:50:54
