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}.
第 3/6 步:重新排列为可逐层化简的行
通俗地说

把加权和 ∑j aj\sum j\,a_j 改写成尾和之和 ∑i∑j≥iaj\sum_i \sum_{j\ge i} a_j 是把权重转化为重复区间的标准技巧,为使用曲棍球棒恒等式做好准备。

∑Smin⁡(S)=∑i=1n−r+1((n−ir−1)+(n−i−1r−1)+⋯+(r−1r−1))\sum_{S}\min(S) = \sum_{i=1}^{n-r+1}\Big(\binom{n-i}{r-1}+\binom{n-i-1}{r-1}+\cdots+\binom{r-1}{r-1}\Big)
详细分析

按列而非按项来读这个三角形和,(n−jr−1)\binom{n-j}{r-1} 上的权重 jj 可以通过对每个 i≤ji \le j 都写一次相同的二项式系数来吸收,从而产生 n−r+1n-r+1 个内部和,每个都是下指标同为 r−1r-1 的一串连续二项式系数。