부분집합 계산기란?
부분집합이란 더 큰 집합에서 골라낸 원소들의 모임을 말하며, 공집합과 집합 자기 자신도 부분집합에 포함됩니다. 이 계산기는 조합론에서 자주 나오는 두 가지 질문에 답해 줍니다. 첫째, 원소가 n개인 집합의 부분집합은 모두 몇 개인가? 둘째, 그중에서 정확히 k개의 원소를 가진 부분집합은 몇 개인가? 집합론, 확률, 이산수학을 공부하는 학생은 물론, 가능한 조합의 수를 세어야 하는 누구에게나 유용합니다.
사용 방법
집합의 크기, 즉 서로 다른 원소의 개수를 n에 입력하세요. 그러면 계산기가 곧바로 전체 부분집합 수(\(2^n\))와 공집합을 뺀 부분집합 수(\(2^n - 1\))를 보여 줍니다. 원하면 부분집합 크기 k도 입력할 수 있는데, 이 경우 이항계수 \(C(n, k)\)를 이용해 정확히 k개의 원소를 가진 부분집합의 수까지 함께 알려 줍니다. 전체 개수만 필요하다면 k는 비워 두면 됩니다.
공식 풀이
집합의 각 원소는 부분집합에 들어가거나 빠지거나, 둘 중 하나로 독립적으로 정해집니다. 즉 원소 하나당 선택지가 2가지입니다. 원소가 n개라면 전체 경우의 수는 다음과 같습니다.
$$2 \times 2 \times \cdots \times 2 = 2^n$$크기가 정해진 k개짜리 부분집합을 세려면 조합 공식을 사용하는데,
$$C(n, k) = \frac{n!}{k!\,(n - k)!}$$이는 순서를 따지지 않고 k개의 원소를 고르는 방법의 수입니다. 0부터 n까지 모든 k에 대해 \(C(n, k)\)를 더하면 다시 \(2^n\)이 됩니다.
예제 풀이
n = 5라고 해 봅시다. 전체 부분집합 수는 \(2^5 = 32\)이고, 공집합을 뺀 부분집합 수는 31입니다. 원소 2개짜리 부분집합의 수는 다음과 같습니다.
$$C(5, 2) = \frac{5!}{2! \cdot 3!} = \frac{120}{2 \cdot 6} = 10$$즉 원소가 5개인 집합에서 만들 수 있는 쌍은 정확히 10가지입니다.
자주 묻는 질문
전체 개수에 공집합도 포함되나요? 네, 포함됩니다. \(2^n\)에는 공집합과 전체 집합이 모두 들어 있습니다. 공집합만 제외하려면 1을 빼고, 진부분집합 중 공집합까지 제외하려면 2를 빼면 됩니다.
k가 n보다 크면 어떻게 되나요? 그런 부분집합은 존재하지 않으므로, \(k > n\)이거나 \(k < 0\)이면 \(C(n, k) = 0\)이 됩니다.
최댓값이 왜 170 근처인가요? \(2^n\)과 팩토리얼은 매우 빠르게 커지기 때문에, n이 대략 170을 넘으면 그 값이 일반적인 부동소수점 숫자가 표현할 수 있는 범위를 벗어납니다.
