MathLabs

第2题

设 nn 和 rr 是满足 1≤r≤n1 \le r \le n 的整数,考虑集合 {1,2,…,n}\{1,2,\dots,n\} 的所有 rr 元子集(共 (nr)\binom{n}{r} 个)。每个这样的子集都有一个最小元素。设 F(n,r)F(n,r) 为这些最小元素的算术平均值。证明 F(n,r)=n+1r+1.F(n,r) = \frac{n+1}{r+1}.
第 1/5 步:写出最小元素之和
通俗地说

与其直接求平均,不如按最小值对子集分组,数出共享每个可能最小值的子集个数。

∑Smin⁡(S)=∑k=1nk(n−kr−1)\sum_{S} \min(S) = \sum_{k=1}^{n} k\binom{n-k}{r-1}
详细分析

固定 kk。最小元素等于 kk 的 {1,…,n}\{1,\dots,n\} 的 rr 元子集数为 (n−kr−1)\binom{n-k}{r-1},因为其余 r−1r-1 个元素必须从大于 kk 的 n−kn-k 个数中选取。乘以 kk 并对所有可能的最小值求和,就得到所有 rr 元子集的最小元素之和。