집합-부분합 정리

집합-부분합 정리

집합-부분합 정리(Set-Partial Sum Theorem)이란 실수 전체의 부분집합에 대하여, 해당 집합과 그 부분집합의 관계에 관한 정리이며, 아래와 같이 정의된다.

실수 전체의 원소가 $n$개인 부분집합 $X$에 대하여 $X$의 원소 중 오직 $r$개$(0\leq r\leq n)$의 원소만을 포함하는 모든 부분집합의 원소의 합을 $S$라 할 때, $X$의 모든 원소의 합 $S_{x}$에 대하여 $S=S_{x}\times {r\times nCr \over n}$이 성립한다.

증명

1. $n$개의 원소를 가진 실수 전체의 부분집합 $X$에 대하여 $X$의 원소 중 오직 $r(0\leq r\leq n)$개의 원소만을 포함하는 $X$의 부분집합의 개수는 $nCr$개이다.
2. $r$개의 원소를 가진 모든 부분집합에 대하여 집합 $X$의 원소들은 모두 $r\times nCr$개 존재한다.
3. $X$의 원소가 $n$개이므로 각각의 $X$의 원소에 대하여 원소의 개수가 $r$개인 모든 부분집합에서 각각의 $X$의 원소들은 ${r\times nCr \over n}$ 개 존재한다.
4. 3에 의해서, 집합 $X$의 모든 원소의 합을 $S_{x}$라 하고, 원소의 개수가 $r$개인 모든 부분집합의 합을 $S$라 하면, $S=S_{x}\times {r\times nCr \over n}$이 성립한다.