{a1, a2, a3, ..., an} 이라는 집합이 있을 때, 부분집합의 공식은 2의 n 거듭제곱 이다.
예를들어 {1,2,3,4,5} 라는 집합이 있다면 부분집합의 수는 곧 1,2,3,4,5 이 다섯개의 원소들을 가지고 만들수 있는 경우의 수이다.
1: O X 2: O X 3: O X 4: O X 5: O X
위 처럼 각각 원소는 2가지 경우의 수가 있으며(있고, 없고)
모든 원소가 X일시 공집합이 되고
1,2만 O일시 부분집합 {1,2} 가 된다.
즉, 각각의 원소들의 경우의 수는 2가지이며 이를 통해 조합 할 수 있는 경우의 수는
2×2×2×2×2 = 32 즉, 2의 5 거듭제곱인 것이다.
일반화할시
K개의 원소를 가진 집합 {a1, a2, a3 ... , ak} 의 부분집합의 수는 2의 K거듭제곱이다.
