홍라이프 계산기멱집합 계산기 쉽게 이해하기 — 개념과 원리
이 계산기는 집합의 멱집합, 즉 공집합부터 집합 자신까지 모든 부분집합을 크기별로 나열합니다. 부분집합의 개수, 진부분집합의 개수, 크기별 개수도 세어 줍니다. 이산수학, 집합 과제, 확률에서 사건 나열, 모든 조합을 검사하는 프로그래밍에 씁니다.
계산 방법
- 원소가 n개인 집합의 부분집합 수 = 2ⁿ
- 원소가 정확히 k개인 부분집합 수 = C(n, k) = n! ÷ (k!(n − k)!)
- 진부분집합 수(S 자신 제외) = 2ⁿ − 1
- 집합은 같은 원소를 한 번만 가지므로 중복 입력은 제거합니다.
원소 8개(부분집합 256개)까지 목록을 보여 주고, 개수는 20개까지 계산합니다. 목록은 입력한 원소 순서를 따릅니다.
원리
부분집합을 만들려면 원소를 하나씩 보며 '넣는다' 또는 '뺀다'를 정합니다. 선택지가 2개인 결정을 n번 하므로 2 × 2 × … × 2 = 2ⁿ가지입니다. 모두 뺀 공집합과 모두 넣은 S 자신도 포함됩니다. 크기별로 묶으면 n개 중 k개를 고르는 방법의 수, 즉 이항계수가 되므로 크기별 개수는 파스칼 삼각형의 한 줄이고 합하면 2ⁿ입니다. 멱집합을 2^S로 쓰기도 하는 이유입니다.
예제 풀이
기본 입력은 S = {a, b, c}입니다.
- n = 3이므로 부분집합은 2³ = 8개입니다.
- 크기 0: ∅
- 크기 1: {a}, {b}, {c}
- 크기 2: {a, b}, {a, c}, {b, c}, 크기 3: {a, b, c}
- 크기별 개수는 1, 3, 3, 1(파스칼 삼각형 3번째 줄)이고, 진부분집합은 2³ − 1 = 7개입니다.
결과 해석
개수는 매우 빠르게 늘어 원소 10개면 1,024개, 20개면 백만 개가 넘습니다. 크기별 개수는 예를 들어 세 사람 중 두 명으로 팀을 만드는 방법이 3가지임을 알려 줍니다. 교재에 따라 진부분집합에서 S만 빼기도 하고(여기서의 방식), 공집합까지 빼기도 하므로 정의를 확인하십시오. 확률 문제에서는 표본공간의 모든 사건이 곧 멱집합의 원소이므로, 사건의 개수를 셀 때도 2ⁿ을 이용합니다. 프로그래밍에서는 0부터 2ⁿ − 1까지의 이진수 각 자리를 원소의 포함 여부로 읽어 모든 부분집합을 만들 수 있습니다.
흔한 실수
- 공집합이나 집합 자신을 빠뜨리는 경우
- {a, b}와 {b, a}를 다른 부분집합으로 세는 경우(집합에서는 순서가 없습니다)
- 부분집합을 순열이나 수열과 혼동하는 경우
- 중복 원소를 입력하고 원소가 늘어난다고 생각하는 경우
자주 묻는 질문
원소가 5개인 집합의 부분집합은 몇 개인가요?
공집합과 자신을 포함해 2⁵ = 32개입니다.
공집합은 모든 집합의 부분집합인가요?
네. 원소가 없으므로 어떤 집합에서도 빠진 원소가 없습니다.
공집합의 멱집합은 무엇인가요?
2⁰ = 1이므로 원소가 하나인 {∅}입니다.
출처: Wolfram MathWorld, "Power Set" · OpenStax, Contemporary Mathematics (2023), §1.2 Subsets