22. Counting

확통에서 배운 순열 개념이랑 거의 동일하다. 새로운 내용보다는 수학적으로 정리하는 느낌.

---

기본 원칙

Sum Rule

A와 B가 겹치지 않을 때 (disjoint):

|A ∪ B| = |A| + |B|

 

Subtraction Rule은 Sum Rule의 응용. 전체에서 여집합을 빼는 것.

|A| = |U| - |Ā|

 

예시: 공 100개 중 빨간 공 37개 → 파란 공 = 100 - 37 = 63개.

 

Product Rule

순서가 있는 선택을 할 때 경우의 수를 곱한다.

|A × B| = |A| · |B|

 

예시: 상의 3가지 × 하의 4가지 = 12가지 코디.

 

Generalized Product Rule: k개의 선택을 순서대로 할 때 각 단계의 선택지가 n1, n2, ..., nk개면 총경우의 수는 n1 · n2 · ... · nk.

---

문제 풀이 전략

전략 1: Exclusion (전체에서 빼기)

직접 세기 어려우면 전체에서 원하지 않는 걸 빼는 방식으로 접근.

예시: 0, 1로 시작하거나 911로 시작하지 않는 7자리 전화번호의 수

1. 0이나 1로 시작하지 않는 수: 8 × 10^6 = 8,000,000
2. 그 중 911로 시작하는 수: 1^3 × 10^4 = 10,000
3. 최종: 8,000,000 - 10,000 = 7,990,000

전략 2: 제약 많은 것 먼저 세기

조건이 복잡할 때 가장 제약이 많은 자리부터 정하면 경우를 나눌 필요가 없어진다.

예시: leading zero 없고 반복 없는 홀수 4자리 수

• d4 먼저 (홀수여야 함): 5가지
• d1 (0과 d4 제외): 8가지
• d2 (d1, d4 제외): 8가지
• d3 (d1, d2, d4 제외): 7가지
• 결과: 5 × 8 × 8 × 7 = 2,240

d1부터 세면 앞에서 홀수를 몇 개 썼는지에 따라 d4의 선택지가 달라져서 경우를 나눠야 한다. 제약이 많은 자리를 먼저 고정하면 이런 복잡함이 사라진다.

---

순열 세 가지

Linear Permutation (일반 순열)

n개를 일렬로 나열하는 경우의 수:

n!

Cyclic Permutation (원형 순열)

n개를 원형으로 배열할 때는 회전한 배열이 동일하게 취급된다. 한 명을 고정하고 나머지를 배열하면 되니까:

(n-1)! = n! / n

Multiset Permutation (중복 원소가 있는 순열)

같은 원소가 여러 개 있을 때, 같은 원소끼리 자리를 바꿔봤자 동일한 배열이다. 그래서 각 원소의 중복 수만큼 나눠줘야 한다.

m! / (μ(x1)! × μ(x2)! × ...)

 

예시: ANAGRAM → 7! / (3! × 1! × 1! × 1! × 1!) = 840

A가 3개라서 3!만큼 중복 계산되기 때문에 3!으로 나눠줌.

---

정리

유형	공식	조건
Linear	n!	중복 없는 일렬 배열
Cyclic	(n-1)!	중복 없는 원형 배열
Multiset	m! / Π μ(x)!	중복 원소 있는 배열