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}.
第 2/6 步：明确写出加权和
上一步下一步
∑Smin⁡(S)=(n−1r−1)+2(n−2r−1)+⋯+(n−r+1)(r−1r−1)\sum_{S}\min(S) = \binom{n-1}{r-1} + 2\binom{n-2}{r-1} + \cdots + (n-r+1)\binom{r-1}{r-1}
详细分析

将第 1 步中的个数乘以 jj，再对 j=1,…,n−r+1j=1,\dots,n-r+1 求和，即得所有最小元素之总和，可写成二项式系数的三角形式之和。