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}.
第 4/6 步:对每一行运用曲棍球棒恒等式
(n−ir−1)+(n−i−1r−1)+⋯+(r−1r−1)=(n−i+1r)\binom{n-i}{r-1}+\binom{n-i-1}{r-1}+\cdots+\binom{r-1}{r-1} = \binom{n-i+1}{r}
详细分析

由曲棍球棒恒等式 ∑k=r−1m(kr−1)=(m+1r)\sum_{k=r-1}^{m}\binom{k}{r-1}=\binom{m+1}{r},每个内部序列都化简为单个二项式系数 (n−i+1r)\binom{n-i+1}{r}。