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 について和をとると、すべての最小要素の総和が得られ、二項係数の三角形状の和として書ける。