23. Counting Subsets

 22단원(Counting)에서 기본 카운팅 원칙을 배웠다면, 이번 단원은 "어떤 방식으로 고르느냐"에 따라 공식이 달라지는 걸 다룬다. 핵심은 딱 두 가지 질문이다.

---

1. 핵심 프레임워크: 4가지 Selection Type

문제를 보면 먼저 이 두 가지를 파악해라:

1. 순서가 중요한가? (ordered vs unordered)
2. 중복이 허용되는가? (with replacement vs without replacement)

Type	순서	중복	공식	예시
1	O	O	nᵏ	주사위 3개 던지기
2	O	X	nPk = n!/(n-k)!	1등~3등 뽑기
3	X	X	C(n,k) = n!/k!(n-k)!	팀원 3명 뽑기
4	X	O	C(k+n-1, k)	아이스크림 중복 선택

 

* Type 4 주의: 중복이 있으면 nᵏ/k!로 계산하면 안 된다! 중복된 항목은 k!번보다 적게 나타나서 틀린 답이 나온다.

---

2. Type 4 — Stars and Bars

공식: C(k+n-1, k)

• k = 고르는 개수
• n = 종류(상자) 수

직관: k개의 ★와 n-1개의 |를 배열하는 문제로 변환!

예시: 아이스크림 5가지 중 3개 고르기 (중복 허용, 순서 없음)

x₁ + x₂ + x₃ + x₄ + x₅ = 3 의 비음정수 해의 수

★★★||      → 첫 번째 맛 3개
★|★|★      → 첫 번째, 세 번째, 다섯 번째 각 1개
||★★★      → 다섯 번째 맛 3개

 

★ 3개 + | 4개 = 7개 슬롯 → C(7, 3) = C(3+5-1, 3) = 35

---

3. 분할 (Partitioning)

분할 문제는 구별되는 항목/동일한 항목 × 이름 있는 그룹/이름 없는 그룹 으로 나뉜다.

① 구별되는 항목 → 이름 있는 그룹 (다항계수)

n! / k_1​!⋅k_2​!⋅⋯⋅k_m​!​

 

예시: 12명을 4명씩 이름 있는 팀 A, B, C로 나누기
→ 12! / (4! · 4! · 4!) = 34,650

 

② 구별되는 항목 → 이름 없는 그룹

같은 크기의 그룹끼리는 구별이 안 되므로, 다항계수에서 같은 크기 그룹 수의 계승으로 나눈다.

n! / k_1​!⋅k_2​!⋅⋯⋅k_m​!⋅μ_1​!⋅μ_2​!⋯

 

예시: 12명을 4명씩 이름 없는 팀 3개로 나누기
→ 크기 4짜리 그룹이 3개 반복 → μ(4) = 3
→ 12! / (4! · 4! · 4! · 3!) = 5,775

 

③ 동일한 항목 → 이름 있는 그룹 (Stars and Bars)

• 0개 가능: C(k+n-1, k)
• 최소 1개: 먼저 각 그룹에 1개씩 미리 배정 → 나머지 k-n개를 Stars and Bars로 분배 → C((k-n)+n-1, k-n) = C(k-1, k-n)

예시: 공 7개를 이름 있는 상자 3개에 넣기

• 0개 가능: C(7+3-1, 7) = C(9, 7) = 36
• 최소 1개: 먼저 1개씩 배정 → 남은 4개를 분배 → C(4+3-1, 4) = C(6, 4) = 15

 

④ 동일한 항목 → 이름 없는 그룹 (정수 분할)

pₖ(n) = n을 k개의 양의 정수로 분할하는 방법의 수

 

점화식: pₖ(n) = pₖ₋₁(n-1) + pₖ(n-k)

• 앞 항: 1이 포함된 분할
• 뒤 항: 1이 없는 분할

기저 조건:

• p₁(n) = 1 (모두 1개짜리)
• pₙ(n) = 1 (전부 1씩)
• pₖ(n) = 0 (k > n이면)

 closed form이 없어서 점화식으로만 계산한다.

 

예) p₃(5) = p₂(4) + p₃(2)
     = 2 + 0
     = 2

중간 계산:
- p₂(4) = 2 → {3+1, 2+2}
- p₃(2) = 0 → 불가능 (2 < 3)

최종: 5를 3개로 분할 = {3+1+1, 2+2+1} → 2가지

 

---

4. 정리

상황	공식
순서 O, 중복 O	nᵏ
순서 O, 중복 X	nPk = n!/(n-k)!
순서 X, 중복 X	C(n,k) = n!/k!(n-k)!
순서 X, 중복 O	C(k+n-1, k)
구별 항목 → 이름 있는 그룹	n! / (k₁!·k₂!·...·kₘ!)
구별 항목 → 이름 없는 그룹	위 ÷ μ(같은 크기)!
동일 항목 → 이름 있는 그룹 (0개 가능)	C(k+n-1, k)
동일 항목 → 이름 있는 그룹 (최소 1개)	C(k-1, k-n)
동일 항목 → 이름 없는 그룹	정수 분할 pₖ(n), 점화식 사용

 

문제 풀이 순서: 순서 있나? → 중복 있나? → 공식 적용!