📂レンマ

n個の要素を持つ有限集合の部分集合の数

式

有限集合 $X$ に対して $n(X)=n$ ならば $n(P(X))=2^{ n }$ だ。

導出

$n$ 個の要素の中から $k$ 個の要素を選ぶ部分集合の数は $_{ n }{ C }_{ k }$ だ。二項定理を使って全ての場合の数を足すと $\displaystyle \sum _{ k=0 }^{ n }{_{ n }{ C }_{ k } }=2^{ n }$ となり、従って $n(P(A))=2^{ n }$ だ。

■