확률·통계집합의 분할#340

집합의 분할

Set Partitions

집합의 분할은 서로 다른 원소 전체를 겹치지 않는 비어 있지 않은 부분집합들로 나누는 것이다. 모둠의 이름과 순서는 구별하지 않는다. 마지막 원소의 위치로 점화식을 증명하고, 이름 있는 상자와 빈 상자를 허용한 분배로 넓힌다.

읽는 시간
약 8분
선수 개념
조합

직관 — 이름표 없는 모둠 만들기

직관

서로 다른 학생을 몇 모둠으로 나눈 뒤 모둠 이름표를 모두 떼어 보자. 같은 학생들끼리 모여 있다면 모둠을 늘어놓은 순서를 바꿔도 같은 나누기다. 빈 모둠은 세지 않는다.

학생은 원소, 모둠은 부분집합이다. 이 글의 학생과 상자는 계산을 위해 만든 가상 상황이다. 조합이 한 부분집합을 고른다면, 여기서는 원소 전체를 빠짐없이 여러 부분집합에 나눈다. 모둠 나누기, 빈 상자가 없는 분배, 치역이 공역 전체인 함수의 개수가 모두 이 수로 정리된다.

집합의 분할은 원소를 한 블록에만 넣는다

집합의 분할은 집합의 모든 원소를 서로 겹치지 않는 비어 있지 않은 부분집합들로 나누는 것이다. 각 부분집합을 블록이라 한다. 블록 안의 원소 순서도, 블록을 쓰는 순서도 구별하지 않는다. 교과서는 집합 AA를 A=B1∪B2∪⋯∪BkA=B_1\cup B_2\cup\cdots\cup B_k처럼 쓰고 각 BiB_i를 블록이라 부른다.

원소가 서로 다른 nn개인 집합을 정확히 kk개 블록으로 나누는 수를 S(n,k)S(n,k)로 쓴다. 우선 n,kn,k는 1≤k≤n1\le k\le n인 정수다. 영문 자료는 이 수를 제2종 스털링 수(Stirling number of the second kind)라 부른다. 예를 들어 {1,2,3,4}\{1,2,3,4\}를 두 블록으로 나누는 경우는

S(4,2)=7.(1)S(4,2)=7. \tag{1}
정의
기호이름원어뜻
nn원소의 수number of elements나눌 서로 다른 원소의 개수
kk블록의 수number of blocks비어 있지 않은 부분집합의 개수
S(n,k)S(n,k)집합의 분할 수Stirling number of the second kindnn개 원소를 이름 없는 kk블록으로 나누는 수
k!k!계승factorialkk개 블록에 서로 다른 이름을 붙이는 방법 수

그림 1에서 한 줄이 하나의 분할이다. 예를 들어 {1,2},{3,4}\{1,2\},\{3,4\}와 {3,4},{1,2}\{3,4\},\{1,2\}는 같은 분할이므로 한 줄만 그렸다. 반면 {1,3},{2,4}\{1,3\},\{2,4\}는 실제로 함께 묶인 원소가 다르므로 다른 분할이다.

네 원소 1, 2, 3, 4를 두 블록으로 나눈 일곱 분할을 블록 크기 3+1의 네 줄과 2+2의 세 줄로 묶었다. 각 줄의 두 상자는 비어 있지 않고 네 원소를 한 번씩 포함하며, 마지막 원소 4가 든 블록을 강조했다.
그림 1 네 원소 1, 2, 3, 4를 두 블록으로 나눈 일곱 분할을 블록 크기 3+1의 네 줄과 2+2의 세 줄로 묶었다. 각 줄의 두 상자는 비어 있지 않고 네 원소를 한 번씩 포함하며, 마지막 원소 4가 든 블록을 강조했다. figures/seven_partitions.py

각 블록은 서로소인 집합이고 합집합은 원래 집합이다. 따라서 같은 원소를 두 모둠에 넣거나 한 원소를 빼놓은 것은 분할이 아니다.

집합의 분할 수는 블록 크기별로 어떻게 셀까?

블록 크기의 모양을 먼저 정하고, 모양마다 원소를 고르는 수를 더하면 된다. 이때 크기가 같은 블록끼리는 순서가 없으므로 그 개수의 계승으로 나눈다.

네 원소를 두 블록으로 나누면 블록 크기는 3과 1이거나 2와 2다. 그림 1의 위 네 줄이 3+1, 아래 세 줄이 2+2다. 3+1에서는 세 원소 블록을 4C3=4{}_4C_3=4가지로 고르면 남은 원소가 나머지 블록이 된다.

2+2에서 첫 블록을 4C2=6{}_4C_2=6가지로 고르면 {1,2}\{1,2\}를 먼저 고른 경우와 {3,4}\{3,4\}를 먼저 고른 경우가 같은 분할로 두 번 세어진다. 크기가 같은 두 블록의 순서를 지우려고 2!2!로 나눈다.

S(4,2)=4C3+4C2×2C22!=4+3=7.(2)S(4,2)={}_4C_3+\frac{{}_4C_2\times{}_2C_2}{2!}=4+3=7. \tag{2}

블록 크기의 모양 3+1과 2+2는 4를 두 양의 정수의 합으로 나타낸 자연수의 분할이다. 원소와 블록이 많아지면 따져야 할 모양이 늘어나므로, 다음 절의 점화식이 계산을 줄여 준다.

집합의 분할에서는 모둠 크기가 같아도 다른 분할인가요?

함께 들어간 원소가 다르면 모둠 크기가 같아도 다른 분할이다. {1,2},{3,4}\{1,2\},\{3,4\}와 {1,3},{2,4}\{1,3\},\{2,4\}는 모두 두 명씩이지만 같은 모둠이 아니다. 개수만 나누는 자연수의 분할과 구별한다.

집합의 분할 점화식은 마지막 원소의 두 경우에서 나온다

마지막 원소 nn이 혼자 블록을 이루는 경우와, 다른 원소와 같은 블록에 들어가는 경우로 나누면 다음 점화식을 얻는다. 점화식은 작은 입력의 분할 수로 다음 분할 수를 나타내는 관계다.

S(n,k)=S(n−1,k−1)+kS(n−1,k).(3)S(n,k)=S(n-1,k-1)+kS(n-1,k). \tag{3}

먼저 nn이 혼자라면 그 블록 {n}\{n\}을 떼어 낸 뒤 n−1n-1개 원소와 k−1k-1개 블록이 남는다. 반대로 남은 원소의 분할 하나에 {n}\{n\}을 붙이면 원래 경우 하나가 된다. 따라서 이 경우의 수는 S(n−1,k−1)S(n-1,k-1)이다.

nn이 혼자가 아니라면 그 원소만 지워도 블록은 비지 않아 kk개가 그대로 남는다. 반대로 n−1n-1개 원소의 kk블록 분할 하나에서 nn을 넣을 블록을 kk가지로 고른다. 넣은 블록이 다르면 nn과 함께 있는 원소들이 달라져 다른 분할이다. 또한 완성된 분할에서 nn을 지우면 출발 분할과 넣은 블록을 복원할 수 있으므로 중복이 없다.

두 경우는 동시에 일어나지 않고 모든 분할이 어느 한쪽에 속한다. 따라서 합의 법칙으로 더하면 식 (3)이 증명된다. 블록에 이름이 없어도 이미 원소 구성이 다른 kk개 블록 중 어디에 넣는지는 구별할 수 있다.

그림 1의 강조한 블록이 4가 든 블록이다. 4가 혼자인 줄은 하나이고, 다른 원소와 함께인 줄은 여섯이다. 이는 식 (3)의 두 항 S(3,1)=1S(3,1)=1과 2S(3,2)=2×3=62S(3,2)=2\times3=6에 해당한다.

집합의 분할 수에 왜 블록 수를 곱하나요?

마지막 원소가 혼자가 아닌 경우에는 이미 만든 kk개 블록 중 들어갈 곳을 고를 수 있기 때문이다. 예를 들어 세 원소의 두 블록 분할이 3가지이고 새 원소를 넣을 곳은 각각 2곳이므로 이 부분은 2×3=62\times3=6가지다.

집합의 분할 수 표는 경계값에서 시작한다

n≥1n\ge1일 때 모두 한 블록에 넣는 방법과 각 원소를 따로 두는 방법은 각각 하나이므로 S(n,1)=S(n,n)=1S(n,1)=S(n,n)=1이다. 원소보다 많은 비어 있지 않은 블록을 만들 수 없어 k>nk>n이면 0이다.

계산을 통일하기 위해 빈 집합을 0블록으로 나누는 빈 분할을 하나로 정하여 S(0,0)=1S(0,0)=1로 둔다. 양의 nn에서 S(n,0)=0S(n,0)=0이며, k>0k>0에서 S(0,k)=0S(0,k)=0이다. 이 경계값을 사용하면 식 (3)은 정수 n≥1n\ge1, 1≤k≤n1\le k\le n에 적용된다. 교과서는 n>k≥2n>k\ge2인 자연수에서 식 (3)을 쓰고 S(n,1)=S(n,n)=1S(n,1)=S(n,n)=1을 따로 둔다.

작은 값부터 계산하면 S(3,2)=S(2,1)+2S(2,2)=1+2=3S(3,2)=S(2,1)+2S(2,2)=1+2=3이다. 이어

S(4,2)=S(3,1)+2S(3,2)=1+2×3=7,S(4,3)=S(3,2)+3S(3,3)=3+3×1=6,S(5,3)=S(4,2)+3S(4,3)=7+3×6=25.(4)\begin{aligned} S(4,2)&=S(3,1)+2S(3,2)=1+2\times3=7,\\ S(4,3)&=S(3,2)+3S(3,3)=3+3\times1=6,\\ S(5,3)&=S(4,2)+3S(4,3)=7+3\times6=25. \end{aligned} \tag{4}

식 (4)의 수치 계산은 점화식의 적용이다. 일반 증명은 앞 절의 두 대응이며 표 몇 줄이 증명을 대신하지 않는다.

그림 2는 이 계산을 n=7n=7까지 이어 놓은 표다. 한 칸의 값은 왼쪽 위 칸의 값에 바로 위 칸의 값을 열 번호 kk배 하여 더한 것이다. 각 행의 양 끝은 경계값 1이다.

식 (3)으로 채운 집합의 분할 수 S(n,k)의 표(1≤ k≤ n≤7). 화살표는 S(5,3)=25를 왼쪽 위 칸 S(4,2)=7과 바로 위 칸 S(4,3)=6의 3배에서 얻는 과정이다.
그림 2 식 (3)으로 채운 집합의 분할 수 S(n,k)S(n,k)의 표(1≤k≤n≤71\le k\le n\le7). 화살표는 S(5,3)=25S(5,3)=25를 왼쪽 위 칸 S(4,2)=7S(4,2)=7과 바로 위 칸 S(4,3)=6S(4,3)=6의 3배에서 얻는 과정이다. figures/stirling_table.py

집합의 분할과 이름 있는 상자의 수는 다르다

서로 다른 nn개 물건을 이름 있는 kk개 상자에 빈 상자 없이 나누면, 먼저 kk개 블록으로 분할한 뒤 블록에 상자 이름을 붙인다. 각 분할의 블록은 서로 다른 원소를 담고 있어서 이름을 붙이는 k!k!가지가 모두 다른 분배다.

이름 있는 상자에 빈 곳 없이 분배하는 수=k!S(n,k).(5)\text{이름 있는 상자에 빈 곳 없이 분배하는 수}=k!S(n,k). \tag{5}
분할 {1,2}, {3,4}에 두 상자 이름 X와 Y를 붙인 두 분배. 같은 분할이라도 X에 어느 블록을 넣었는지에 따라 결과가 달라진다.
그림 3 분할 {1,2}, {3,4}에 두 상자 이름 X와 Y를 붙인 두 분배. 같은 분할이라도 X에 어느 블록을 넣었는지에 따라 결과가 달라진다. figures/labeled_blocks.py

네 물건을 두 이름 있는 상자에 모두 사용하도록 넣으면 그림 3처럼 분할마다 두 분배가 생겨 2!S(4,2)=2×7=142!S(4,2)=2\times7=14가지다. 빈 상자도 허용하면 각 물건이 두 상자 중 하나를 선택하므로 중복순열 24=162^4=16가지다. 전부 X에 넣는 경우와 전부 Y에 넣는 경우가 추가된 것이다.

이름 있는 상자에 넣는 일은 함수로 볼 수 있다. 물건의 집합 AA에서 상자 이름의 집합 BB로 가는 함수에서 각 물건의 함숫값은 들어간 상자다. 빈 상자가 없다는 조건은 치역이 공역 BB 전체라는 조건과 같다. 원소가 7개인 AA에서 원소가 4개인 BB로 가는 함수 가운데 치역이 BB인 함수는 그림 2의 S(7,4)=350S(7,4)=350을 써서 4!×350=24×350=84004!\times350=24\times350=8400개다.

블록이 두 개인 경우에는 식 (5)를 거꾸로 써서 일반식을 얻는다. 이름 있는 상자 X, Y에 nn개를 넣는 2n2^n가지 중 한쪽이 비는 2가지를 빼면 2!S(n,2)2!S(n,2)가 남는다.

S(n,2)=2n−22!=2n−1−1.(6)S(n,2)=\frac{2^n-2}{2!}=2^{n-1}-1. \tag{6}

n=4n=4이면 (16−2)÷2=7(16-2)\div2=7로 식 (1)과 같다.

빈 상자를 허용하면 집합의 분할 수를 어떻게 바꿀까?

똑같은 상자에 빈 상자를 허용하면 실제로 사용한 상자 수별 분할 수를 더한다. 사용한 상자 하나하나가 비어 있지 않은 블록이기 때문이다. 서로 다른 네 물건을 똑같은 상자 세 개에 넣으면 사용한 상자는 1개, 2개, 3개 중 하나다.

S(4,1)+S(4,2)+S(4,3)=1+7+6=14.(7)S(4,1)+S(4,2)+S(4,3)=1+7+6=14. \tag{7}

상자가 네 개 이상이면 S(4,4)=1S(4,4)=1이 더해져 15가 되고, 그 뒤로는 늘지 않는다. 블록 수를 정하지 않은 네 원소의 분할은 모두 15가지다.

이름 있는 상자 세 개에 빈 상자를 허용한 배치 34=813^4=81가지와 비교해 보자. 그림 4처럼 한 블록에 모두 넣은 분할은 빈 상자 둘을 서로 바꿔도 같은 배치라 이름이 3가지만 붙는다. 블록이 두 개나 세 개인 분할은 3×2=63\times2=6가지씩 이름을 받는다.

34=3S(4,1)+6S(4,2)+6S(4,3)=3+42+36=81.(8)3^4=3S(4,1)+6S(4,2)+6S(4,3)=3+42+36=81. \tag{8}
네 원소를 한 블록으로 둔 분할을 이름 있는 상자 X, Y, Z에 넣은 세 배치. 빈 상자 두 개는 서로 바꿔도 같은 배치이므로 이름을 붙이는 방법이 3!=6이 아니라 3가지다.
그림 4 네 원소를 한 블록으로 둔 분할을 이름 있는 상자 X, Y, Z에 넣은 세 배치. 빈 상자 두 개는 서로 바꿔도 같은 배치이므로 이름을 붙이는 방법이 3!=63!=6이 아니라 3가지다. figures/empty_box_placements.py
핵심

집합의 분할은 서로 다른 원소 전체를 이름 없는 비어 있지 않은 블록으로 나눈다. 정수 n≥1n\ge1, 1≤k≤n1\le k\le n에서 마지막 원소가 혼자인 경우와 기존 블록에 들어간 경우를 나누면 S(n,k)=S(n−1,k−1)+kS(n−1,k)S(n,k)=S(n-1,k-1)+kS(n-1,k)가 된다.

집합의 분할에서 빈 블록을 넣어도 되나요?

아니다. 집합의 분할에서 블록은 비어 있지 않아야 한다. 네 원소를 다섯 블록으로 나누는 수는 0이며, 빈 상자를 허용하는 분배는 식 (7)처럼 사용한 블록 수별 분할 수를 더해 따로 센다.

제2종 스털링 수는 집합의 분할 수와 같은 것인가요?

그렇다. 제2종 스털링 수는 서로 다른 원소 nn개를 비어 있지 않은 kk개 블록으로 나누는 수로, 이 글의 S(n,k)S(n,k)다. 기호와 인자 순서는 자료에 따라 다를 수 있으므로 S(4,2)=7S(4,2)=7 같은 작은 값으로 뜻을 맞춰 본다.

집합의 분할의 흔한 오해

  • 블록 순서가 없으므로 원소 자체도 구별하지 않는다 — 원소 1과 2는 서로 다른 대상이다. 순서를 지우는 것은 원소의 이름을 지우는 것과 다르다.
  • 이름 있는 상자도 항상 분할 수와 같다 — 그림 3처럼 동일한 두 블록에 X와 Y를 바꾸어 붙이면 다른 분배다. 네 물건의 두 블록 분할 7가지와 이름 있는 빈 곳 없는 분배 14가지는 다르다.
  • 똑같은 상자에 빈 상자를 허용하면 이름 있는 배치 수를 상자 수의 계승으로 나누면 된다 — 네 물건과 세 상자에서 34÷3!=13.53^4\div3!=13.5는 정수도 아니다. 식 (8)처럼 한 블록 분할은 이름을 3가지만 받으므로, 실제 수는 식 (7)의 14다.

직접 해보기

다음 모둠·상자는 가상 상황이며 모든 원소와 물건은 서로 다르다.

  1. S(5,2)S(5,2)를 점화식으로 계산하고 식 (6)으로 확인하라.
  2. S(5,3)=25S(5,3)=25, S(5,2)=15S(5,2)=15를 이용해 S(6,3)S(6,3)을 구하라. 마지막 원소가 혼자인 경우도 따로 적어라. 블록 크기별로도 세어 같은 값인지 확인하라.
  3. 다섯 물건을 이름 있는 두 상자에 빈 곳 없이 넣는 방법은 몇 가지인가? 빈 상자를 허용하면 어떻게 바뀌는가?
  4. 여섯 원소를 다섯 블록으로 분할하는 수를 점화식 없이 구하라. 어떤 두 원소를 같은 블록에 넣는지 생각하라.
  5. 서로 다른 책 다섯 권을 똑같은 상자 세 개에 넣는다. 빈 상자를 허용할 때의 수를 구하라. 상자에 X, Y, Z 이름을 붙이고 빈 상자를 금지하면 몇 가지인가?
답과 풀이
  1. S(5,2)=S(4,1)+2S(4,2)=1+2×7=15S(5,2)=S(4,1)+2S(4,2)=1+2\times7=15다. 식 (6)으로도 24−1=152^4-1=15다.
  2. 마지막 원소가 혼자이면 S(5,2)=15S(5,2)=15가지, 혼자가 아니면 3S(5,3)=753S(5,3)=75가지다. 합하면 S(6,3)=15+75=90S(6,3)=15+75=90이다. 블록 크기로 세면 4+1+1은 6C4=15{}_6C_4=15, 3+2+1은 6C3×3C2=20×3=60{}_6C_3\times{}_3C_2=20\times3=60, 2+2+2는 6C2×4C2÷3!=15×6÷6=15{}_6C_2\times{}_4C_2\div3!=15\times6\div6=15로 합이 90이다.
  3. 빈 곳 없이 넣으면 2!S(5,2)=2×15=302!S(5,2)=2\times15=30가지다. 빈 곳을 허용하면 25=322^5=32가지로, 한 상자에만 모두 넣는 두 경우가 추가된다.
  4. 두 원소로 된 블록 하나와 한 원소 블록 네 개여야 한다. 짝이 될 두 원소를 고르는 6C2=6×5/2=15{}_6C_2=6\times5/2=15가지다. 나머지 블록은 자동으로 정해진다.
  5. 사용한 상자가 1, 2, 3개인 경우를 더해 S(5,1)+S(5,2)+S(5,3)=1+15+25=41S(5,1)+S(5,2)+S(5,3)=1+15+25=41가지다. 이름 있는 세 상자를 모두 쓰면 식 (5)에서 3!×S(5,3)=6×25=1503!\times S(5,3)=6\times25=150가지다.

더 읽기

영상 노트

영상 노트
  • 00:00 이름 없는 모둠과 블록 순서를 구별한다.
  • 00:30 그림 1의 일곱 분할로 식 (1)을 확인하고, 블록 크기별로 식 (2)를 센다.
  • 01:20 마지막 원소를 떼고 되돌리는 두 대응으로 식 (3)을 증명한다.
  • 02:20 경계값에서 식 (4)를 한 줄씩 계산하고 그림 2의 표를 채운다.
  • 03:00 그림 3에 상자 이름을 붙여 식 (5), 치역이 공역 전체인 함수, 식 (6)으로 잇는다.
  • 03:50 빈 상자를 허용한 식 (7)과 그림 4, 식 (8)로 나눗셈이 안 되는 이유를 보인다.

지도에서의 위치

순열확률·통계조합확률·통계집합의 분할지금 이 페이지자연수의 분할확률·통계
선수 개념
이 페이지
다음 개념
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 블록 크기별 세기, 분할 수 표, 치역이 공역 전체인 함수와 두 블록 일반식, 같은 상자에 빈 상자를 허용한 분배, 질문·연습 보강 (에이전트 수정, 그림 2→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림