직관 — 이름표 없는 모둠 만들기
서로 다른 학생을 몇 모둠으로 나눈 뒤 모둠 이름표를 모두 떼어 보자. 같은 학생들끼리 모여 있다면 모둠을 늘어놓은 순서를 바꿔도 같은 나누기다. 빈 모둠은 세지 않는다.
학생은 원소, 모둠은 부분집합이다. 이 글의 학생과 상자는 계산을 위해 만든 가상 상황이다. 조합이 한 부분집합을 고른다면, 여기서는 원소 전체를 빠짐없이 여러 부분집합에 나눈다. 모둠 나누기, 빈 상자가 없는 분배, 치역이 공역 전체인 함수의 개수가 모두 이 수로 정리된다.
집합의 분할은 원소를 한 블록에만 넣는다
집합의 분할은 집합의 모든 원소를 서로 겹치지 않는 비어 있지 않은 부분집합들로 나누는 것이다. 각 부분집합을 블록이라 한다. 블록 안의 원소 순서도, 블록을 쓰는 순서도 구별하지 않는다. 교과서는 집합 를 처럼 쓰고 각 를 블록이라 부른다.
원소가 서로 다른 개인 집합을 정확히 개 블록으로 나누는 수를 로 쓴다. 우선 는 인 정수다. 영문 자료는 이 수를 제2종 스털링 수(Stirling number of the second kind)라 부른다. 예를 들어 를 두 블록으로 나누는 경우는
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 원소의 수 | number of elements | 나눌 서로 다른 원소의 개수 | |
| 블록의 수 | number of blocks | 비어 있지 않은 부분집합의 개수 | |
| 집합의 분할 수 | Stirling number of the second kind | 개 원소를 이름 없는 블록으로 나누는 수 | |
| 계승 | factorial | 개 블록에 서로 다른 이름을 붙이는 방법 수 |
그림 1에서 한 줄이 하나의 분할이다. 예를 들어 와 는 같은 분할이므로 한 줄만 그렸다. 반면 는 실제로 함께 묶인 원소가 다르므로 다른 분할이다.
figures/seven_partitions.py각 블록은 서로소인 집합이고 합집합은 원래 집합이다. 따라서 같은 원소를 두 모둠에 넣거나 한 원소를 빼놓은 것은 분할이 아니다.
집합의 분할 수는 블록 크기별로 어떻게 셀까?
블록 크기의 모양을 먼저 정하고, 모양마다 원소를 고르는 수를 더하면 된다. 이때 크기가 같은 블록끼리는 순서가 없으므로 그 개수의 계승으로 나눈다.
네 원소를 두 블록으로 나누면 블록 크기는 3과 1이거나 2와 2다. 그림 1의 위 네 줄이 3+1, 아래 세 줄이 2+2다. 3+1에서는 세 원소 블록을 가지로 고르면 남은 원소가 나머지 블록이 된다.
2+2에서 첫 블록을 가지로 고르면 를 먼저 고른 경우와 를 먼저 고른 경우가 같은 분할로 두 번 세어진다. 크기가 같은 두 블록의 순서를 지우려고 로 나눈다.
블록 크기의 모양 3+1과 2+2는 4를 두 양의 정수의 합으로 나타낸 자연수의 분할이다. 원소와 블록이 많아지면 따져야 할 모양이 늘어나므로, 다음 절의 점화식이 계산을 줄여 준다.
집합의 분할에서는 모둠 크기가 같아도 다른 분할인가요?
함께 들어간 원소가 다르면 모둠 크기가 같아도 다른 분할이다. 와 는 모두 두 명씩이지만 같은 모둠이 아니다. 개수만 나누는 자연수의 분할과 구별한다.
집합의 분할 점화식은 마지막 원소의 두 경우에서 나온다
마지막 원소 이 혼자 블록을 이루는 경우와, 다른 원소와 같은 블록에 들어가는 경우로 나누면 다음 점화식을 얻는다. 점화식은 작은 입력의 분할 수로 다음 분할 수를 나타내는 관계다.
먼저 이 혼자라면 그 블록 을 떼어 낸 뒤 개 원소와 개 블록이 남는다. 반대로 남은 원소의 분할 하나에 을 붙이면 원래 경우 하나가 된다. 따라서 이 경우의 수는 이다.
이 혼자가 아니라면 그 원소만 지워도 블록은 비지 않아 개가 그대로 남는다. 반대로 개 원소의 블록 분할 하나에서 을 넣을 블록을 가지로 고른다. 넣은 블록이 다르면 과 함께 있는 원소들이 달라져 다른 분할이다. 또한 완성된 분할에서 을 지우면 출발 분할과 넣은 블록을 복원할 수 있으므로 중복이 없다.
두 경우는 동시에 일어나지 않고 모든 분할이 어느 한쪽에 속한다. 따라서 합의 법칙으로 더하면 식 (3)이 증명된다. 블록에 이름이 없어도 이미 원소 구성이 다른 개 블록 중 어디에 넣는지는 구별할 수 있다.
그림 1의 강조한 블록이 4가 든 블록이다. 4가 혼자인 줄은 하나이고, 다른 원소와 함께인 줄은 여섯이다. 이는 식 (3)의 두 항 과 에 해당한다.
집합의 분할 수에 왜 블록 수를 곱하나요?
마지막 원소가 혼자가 아닌 경우에는 이미 만든 개 블록 중 들어갈 곳을 고를 수 있기 때문이다. 예를 들어 세 원소의 두 블록 분할이 3가지이고 새 원소를 넣을 곳은 각각 2곳이므로 이 부분은 가지다.
집합의 분할 수 표는 경계값에서 시작한다
일 때 모두 한 블록에 넣는 방법과 각 원소를 따로 두는 방법은 각각 하나이므로 이다. 원소보다 많은 비어 있지 않은 블록을 만들 수 없어 이면 0이다.
계산을 통일하기 위해 빈 집합을 0블록으로 나누는 빈 분할을 하나로 정하여 로 둔다. 양의 에서 이며, 에서 이다. 이 경계값을 사용하면 식 (3)은 정수 , 에 적용된다. 교과서는 인 자연수에서 식 (3)을 쓰고 을 따로 둔다.
작은 값부터 계산하면 이다. 이어
식 (4)의 수치 계산은 점화식의 적용이다. 일반 증명은 앞 절의 두 대응이며 표 몇 줄이 증명을 대신하지 않는다.
그림 2는 이 계산을 까지 이어 놓은 표다. 한 칸의 값은 왼쪽 위 칸의 값에 바로 위 칸의 값을 열 번호 배 하여 더한 것이다. 각 행의 양 끝은 경계값 1이다.
figures/stirling_table.py집합의 분할과 이름 있는 상자의 수는 다르다
서로 다른 개 물건을 이름 있는 개 상자에 빈 상자 없이 나누면, 먼저 개 블록으로 분할한 뒤 블록에 상자 이름을 붙인다. 각 분할의 블록은 서로 다른 원소를 담고 있어서 이름을 붙이는 가지가 모두 다른 분배다.
figures/labeled_blocks.py네 물건을 두 이름 있는 상자에 모두 사용하도록 넣으면 그림 3처럼 분할마다 두 분배가 생겨 가지다. 빈 상자도 허용하면 각 물건이 두 상자 중 하나를 선택하므로 중복순열 가지다. 전부 X에 넣는 경우와 전부 Y에 넣는 경우가 추가된 것이다.
이름 있는 상자에 넣는 일은 함수로 볼 수 있다. 물건의 집합 에서 상자 이름의 집합 로 가는 함수에서 각 물건의 함숫값은 들어간 상자다. 빈 상자가 없다는 조건은 치역이 공역 전체라는 조건과 같다. 원소가 7개인 에서 원소가 4개인 로 가는 함수 가운데 치역이 인 함수는 그림 2의 을 써서 개다.
블록이 두 개인 경우에는 식 (5)를 거꾸로 써서 일반식을 얻는다. 이름 있는 상자 X, Y에 개를 넣는 가지 중 한쪽이 비는 2가지를 빼면 가 남는다.
이면 로 식 (1)과 같다.
빈 상자를 허용하면 집합의 분할 수를 어떻게 바꿀까?
똑같은 상자에 빈 상자를 허용하면 실제로 사용한 상자 수별 분할 수를 더한다. 사용한 상자 하나하나가 비어 있지 않은 블록이기 때문이다. 서로 다른 네 물건을 똑같은 상자 세 개에 넣으면 사용한 상자는 1개, 2개, 3개 중 하나다.
상자가 네 개 이상이면 이 더해져 15가 되고, 그 뒤로는 늘지 않는다. 블록 수를 정하지 않은 네 원소의 분할은 모두 15가지다.
이름 있는 상자 세 개에 빈 상자를 허용한 배치 가지와 비교해 보자. 그림 4처럼 한 블록에 모두 넣은 분할은 빈 상자 둘을 서로 바꿔도 같은 배치라 이름이 3가지만 붙는다. 블록이 두 개나 세 개인 분할은 가지씩 이름을 받는다.
figures/empty_box_placements.py집합의 분할은 서로 다른 원소 전체를 이름 없는 비어 있지 않은 블록으로 나눈다. 정수 , 에서 마지막 원소가 혼자인 경우와 기존 블록에 들어간 경우를 나누면 가 된다.
집합의 분할에서 빈 블록을 넣어도 되나요?
아니다. 집합의 분할에서 블록은 비어 있지 않아야 한다. 네 원소를 다섯 블록으로 나누는 수는 0이며, 빈 상자를 허용하는 분배는 식 (7)처럼 사용한 블록 수별 분할 수를 더해 따로 센다.
제2종 스털링 수는 집합의 분할 수와 같은 것인가요?
그렇다. 제2종 스털링 수는 서로 다른 원소 개를 비어 있지 않은 개 블록으로 나누는 수로, 이 글의 다. 기호와 인자 순서는 자료에 따라 다를 수 있으므로 같은 작은 값으로 뜻을 맞춰 본다.
집합의 분할의 흔한 오해
- 블록 순서가 없으므로 원소 자체도 구별하지 않는다 — 원소 1과 2는 서로 다른 대상이다. 순서를 지우는 것은 원소의 이름을 지우는 것과 다르다.
- 이름 있는 상자도 항상 분할 수와 같다 — 그림 3처럼 동일한 두 블록에 X와 Y를 바꾸어 붙이면 다른 분배다. 네 물건의 두 블록 분할 7가지와 이름 있는 빈 곳 없는 분배 14가지는 다르다.
- 똑같은 상자에 빈 상자를 허용하면 이름 있는 배치 수를 상자 수의 계승으로 나누면 된다 — 네 물건과 세 상자에서 는 정수도 아니다. 식 (8)처럼 한 블록 분할은 이름을 3가지만 받으므로, 실제 수는 식 (7)의 14다.
직접 해보기
다음 모둠·상자는 가상 상황이며 모든 원소와 물건은 서로 다르다.
- 를 점화식으로 계산하고 식 (6)으로 확인하라.
- , 를 이용해 을 구하라. 마지막 원소가 혼자인 경우도 따로 적어라. 블록 크기별로도 세어 같은 값인지 확인하라.
- 다섯 물건을 이름 있는 두 상자에 빈 곳 없이 넣는 방법은 몇 가지인가? 빈 상자를 허용하면 어떻게 바뀌는가?
- 여섯 원소를 다섯 블록으로 분할하는 수를 점화식 없이 구하라. 어떤 두 원소를 같은 블록에 넣는지 생각하라.
- 서로 다른 책 다섯 권을 똑같은 상자 세 개에 넣는다. 빈 상자를 허용할 때의 수를 구하라. 상자에 X, Y, Z 이름을 붙이고 빈 상자를 금지하면 몇 가지인가?
답과 풀이
- 다. 식 (6)으로도 다.
- 마지막 원소가 혼자이면 가지, 혼자가 아니면 가지다. 합하면 이다. 블록 크기로 세면 4+1+1은 , 3+2+1은 , 2+2+2는 로 합이 90이다.
- 빈 곳 없이 넣으면 가지다. 빈 곳을 허용하면 가지로, 한 상자에만 모두 넣는 두 경우가 추가된다.
- 두 원소로 된 블록 하나와 한 원소 블록 네 개여야 한다. 짝이 될 두 원소를 고르는 가지다. 나머지 블록은 자동으로 정해진다.
- 사용한 상자가 1, 2, 3개인 경우를 더해 가지다. 이름 있는 세 상자를 모두 쓰면 식 (5)에서 가지다.
더 읽기
- 우리교과서 2022 개정 고등학교 이산 수학 — 이준열 외, 인쇄25–29쪽. 블록 정의, 마지막 원소로 나누는 증명, 이름 있는 분배의 관계를 확인했다.
- More Discrete Mathematics — Stirling Numbers of the Second Kind — Oscar Levin. 점화식과 경계값을 읽었다. 원문의 은 원소 수를 먼저 쓰므로, 이 글의 와 문자 이름만 바뀐다.
영상 노트
- 00:00 이름 없는 모둠과 블록 순서를 구별한다.
- 00:30 그림 1의 일곱 분할로 식 (1)을 확인하고, 블록 크기별로 식 (2)를 센다.
- 01:20 마지막 원소를 떼고 되돌리는 두 대응으로 식 (3)을 증명한다.
- 02:20 경계값에서 식 (4)를 한 줄씩 계산하고 그림 2의 표를 채운다.
- 03:00 그림 3에 상자 이름을 붙여 식 (5), 치역이 공역 전체인 함수, 식 (6)으로 잇는다.
- 03:50 빈 상자를 허용한 식 (7)과 그림 4, 식 (8)로 나눗셈이 안 되는 이유를 보인다.
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 블록 크기별 세기, 분할 수 표, 치역이 공역 전체인 함수와 두 블록 일반식, 같은 상자에 빈 상자를 허용한 분배, 질문·연습 보강 (에이전트 수정, 그림 2→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림