집합-부분합 정리

집합-부분합 정리

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

실수 전체의 원소가

$n$

개인 부분집합

$X$

에 대하여

$X$

의 원소 중 오직

$r$

개

$(0\le r\le n)$

의 원소만을 포함하는 모든 부분집합의 원소의 합을

$S$

라 할 때,

$X$

의 모든 원소의 합

$S_x$

에 대하여

$S=S_x\times \frac{r\times nCr}{n}$

이 성립한다.

증명

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