📂보조정리

원소가 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 }$ 이다.

■