第2問

n

と

r

を

1 \le r \le n

を満たす整数とし、集合

\{1,2,\dots,n\}

の

r

個の要素からなるすべての部分集合、すなわち

\binom{n}{r}

個の部分集合を考える。それぞれの部分集合には最小の要素がある。これらの最小要素の相加平均を

F(n,r)

とする。

F(n,r) = \frac{n+1}{r+1}.

を証明せよ。

ステップ 4/5: 相加平均を作る

F(n,r) = \frac{\sum_{S}\min(S)}{\binom{n}{r}} = \frac{\binom{n+1}{r+1}}{\binom{n}{r}}

詳しい解説

部分集合は全部で $\binom{n}{r}$ 個あるので、ステップ3で得た総和を $\binom{n}{r}$ で割れば、最小要素の相加平均 $F(n,r)$ が得られる。