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/6 步:统计具有固定最小值的子集
通俗地说

这与解法 1 的第 1 步类似,但接下来采用不同的求和策略。

#{S:min⁡S=j}=(n−jr−1),j=1,…,n−r+1\#\{S : \min S = j\} = \binom{n-j}{r-1}, \quad j=1,\dots,n-r+1
详细分析

若 jj 是某个 rr 元子集的最小元素,则其余 r−1r-1 个元素来自大于 jj 的 n−jn-j 个数,共有 (n−jr−1)\binom{n-j}{r-1} 种选法。