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 について同じ二項係数を1回ずつ書くことで吸収できる。その結果、下側の添字が r−1r-1 で共通する連続した二項係数からなる n−r+1n-r+1 個の内側の和が得られる。