Counting

Discrete Mathematics and Its Applications · Kenneth H. Rosen · Ch. 5

Intuition

복잡한 전체 경우의 수는 쪼갤 수 있는 독립적인 단계들의 곱(Product)이나, 겹치지 않는 선택지들의 합(Sum)으로 치환하여 정복할 수 있다.

One-liner

기본적인 합·곱의 법칙에서 시작하여 비둘기집 원리, 순열과 조합, 이항 정리를 거쳐 구별 불가능한 객체의 배치와 생성 알고리즘까지 다루는 조합론(Combinatorics)의 종합 가이드.

Prerequisites

이 챕터를 이해하기 위해 필요한 선행 개념은 다음과 같다.

• Set Theory (집합론): 집합의 크기(Cardinality), 합집합, 교집합, 카테시안 곱 (Ch. 2).
• Functions (함수): 일대일 함수(One-to-one) 및 치역과 공역의 개념 (Ch. 2).
• Mathematical Induction (수학적 귀납법): 주요 공식의 증명 과정을 이해하기 위해 필요 (Ch. 4).

Goals

• 합의 법칙과 곱의 법칙을 적재적소에 적용하여 복잡한 경우의 수 문제를 해결한다.
• 비둘기집 원리와 그 일반화된 형태를 사용하여 존재성을 증명한다.
• 순열(Permutation)과 조합(Combination)의 차이를 이해하고 중복 허용 여부에 따른 공식을 적용한다.
• 이항 계수의 성질을 조합론적 증명(Combinatorial Proof) 방식으로 유도한다.
• 사전식 순서(Lexicographic Order)에 기반하여 순열과 조합을 생성하는 알고리즘을 이해한다.

Core Concepts

5.1 계수의 기본 원리 (The Basics of Counting)

Definition: Product Rule (곱의 법칙)

어떤 절차가 $m$개의 순차적인 작업 $T_1, T_2, \dots, T_m$으로 구성되고, 각 작업 $T_i$를 수행하는 방법이 $n_i$가지라면, 전체 절차를 수행하는 방법의 수는 다음과 같다. (p. 336)

$$n_1 \cdot n_2 \cdot \dots \cdot n_m$$

Definition: Sum Rule (합의 법칙)

어떤 작업이 $n_1$가지 방법 중 하나로 수행되거나, $n_2$가지 방법 중 하나로 수행될 수 있을 때, 두 방법의 집합이 서로소(Disjoint)라면 전체 작업의 경우의 수는 다음과 같다. (p. 338)

$$n_1 + n_2$$

Definition: Subtraction Principle (뺄셈 원리 / 포함-배제 원리)

두 작업이 동시에 발생할 수 있는 경우(집합이 겹치는 경우), 중복 계산된 부분을 제외한다. (p. 342)

$$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|$$

5.2 비둘기집 원리 (The Pigeonhole Principle)

Theorem: The Pigeonhole Principle

$k$가 양의 정수일 때, $k+1$개 이상의 객체를 $k$개의 상자에 넣으면 적어도 한 상자에는 두 개 이상의 객체가 들어있다. (p. 347)

Theorem: Generalized Pigeonhole Principle (일반화된 비둘기집 원리)

$N$개의 객체를 $k$개의 상자에 넣으면, 적어도 한 상자에는 다음 이상의 객체가 들어있다. (p. 349)

$$\lceil N/k \rceil$$

5.3 순열과 조합 (Permutations and Combinations)

순서의 유무가 핵심 차이이다. (p. 355)

• Permutation (순열): $n$개의 서로 다른 원소 중 $r$개를 선택하여 순서대로 나열함.
• Combination (조합): $n$개의 서로 다른 원소 중 $r$개를 순서 상관없이 선택함 (부분집합).

5.4 이항 계수 (Binomial Coefficients)

Theorem: The Binomial Theorem (이항 정리)

$n$이 비음의 정수일 때 다음이 성립한다. (p. 363)

$$(x+y)^n = \sum_{j=0}^{n} \binom{n}{j} x^{n-j} y^j$$

5.5 일반화된 순열과 조합 (Generalized Permutations and Combinations)

중복 허용 여부와 구별 가능 여부에 따라 분류된다. (p. 370-376)

• Permutations with Repetition: $n$개 중 $r$개를 중복 허용하여 순열 생성 $\rightarrow n^r$.
• Combinations with Repetition: $n$개 중 $r$개를 중복 허용하여 조합 생성 $\rightarrow C(n+r-1, r)$.
• Indistinguishable Objects: 구별 불가능한 객체 $n$개를 $k$개의 구별 가능한 상자에 배치하는 방법의 수.

Notation

기호	의미
$P(n, r)$	$n$개 중 $r$개를 택하는 순열의 수
$C(n, r)$ 또는 $\binom{n}{r}$	$n$개 중 $r$개를 택하는 조합의 수 (Binomial Coefficient)
$n!$	팩토리얼 (Factorial)
$\lceil x \rceil$	천장 함수 (Ceiling function)
$S(n, j)$	제2종 스털링 수 (Stirling numbers of the second kind)

Key Theorems & Formulas

Theorem: $P(n, r)$ 공식

조건: $1 \le r \le n$

결론:

$$P(n, r) = \frac{n!}{(n-r)!}$$

(p. 356)

Theorem: $C(n, r)$ 공식

조건: $0 \le r \le n$

결론:

$$C(n, r) = \frac{n!}{r!(n-r)!}$$

(p. 358)

Theorem: Pascal's Identity (파스칼의 항등식)

결론:

$$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$

증명 직관: $n+1$개 원소 중 $k$개를 뽑을 때, 특정 원소 $a$를 포함하는 경우($\binom{n}{k-1}$)와 포함하지 않는 경우($\binom{n}{k}$)의 합이다. (p. 366)

Worked Examples

Example 1: 복합적인 암호 계수 (Section 5.1)

문제: 대문자와 숫자로 구성된 6~8자 길이의 암호 중, 적어도 하나의 숫자가 포함된 암호의 개수는? (p. 340)

핵심 단계:

1. 분할: 암호 길이에 따라 6자($P_6$), 7자($P_7$), 8자($P_8$)인 경우로 나눈다 (Sum Rule).
2. 여사건 활용: 전체 암호 수(문자+숫자 조합)에서 숫자가 하나도 없는 암호(문자만 있는 경우)를 뺀다.
   • $P_6 = 36^6 - 26^6$
3. 최종 계산: $P = P_6 + P_7 + P_8$.

Example 2: 중복 조합과 방정식의 해 (Section 5.5)

문제: $x_1 + x_2 + x_3 = 11$을 만족하는 음이 아닌 정수 해의 개수는? (p. 373)

핵심 단계:

1. 문제를 11개의 '별(star)'을 3개의 '상자'에 나누어 담는 문제로 치환한다.
2. 구분선(bar)은 $3-1=2$개가 필요하다.
3. 전체 13개 자리($11+2$) 중 구분선이 들어갈 2곳을 고르는 조합과 같다.
   • $C(13, 2) = 78$.

Common Pitfalls

Pitfall: 중복 조합 $n$과 $r$의 혼동

중복 조합 공식 $C(n+r-1, r)$에서 $n$은 선택할 수 있는 종류의 수이고, $r$은 실제로 선택하는 개수이다. "12개의 도넛 종류 중 5개를 고르기"와 "5개의 도넛 종류 중 12개를 고르기"를 명확히 구분해야 한다. (p. 372)

Pitfall: 비둘기집 원리의 역설적 결론

비둘기집 원리는 "적어도 하나가 존재함"을 보장할 뿐, "정확히 몇 개인지"나 "어느 상자인지"는 알려주지 않는다. (p. 347)

Connections

• 선행 개념: Set Cartesian Products (Ch. 2, p. 338) - 곱의 법칙의 집합론적 근거.
• 후속 개념: Inclusion-Exclusion Principle (Ch. 7) - 3개 이상의 집합에 대한 확장. Discrete Probability (Ch. 6) - 경우의 수 계산을 확률 계산에 직접 활용한다.
• 응용 분야: Algorithm Complexity (Ch. 3, p. 335) - 중첩 루프의 실행 횟수 계산 시 곱의 법칙과 중복 조합이 사용됨.

Critical Notes

교재가 강조하는 것

• Combinatorial Proof (조합론적 증명): 대수적 계산보다 "양변이 같은 대상을 다른 방식으로 세고 있음"을 보여주는 논리의 우아함을 매우 강조한다. (p. 359)
• Modeling: 실생활 문제(암호, IP 주소, 회의 구성)를 순열, 조합, 비둘기집 모델로 치환하는 능력을 중시한다.

실제로 중요한 것 (요약자 관점)

• 단순 공식 암기보다 **중복 계산(Overcounting)**을 피하는 감각이 훨씬 중요하다. 특히 포함-배제 원리는 복잡한 문제의 거의 모든 곳에 숨어 있다.

교재가 생략하거나 얼버무리는 것

• 구별 불가능한 객체를 구별 불가능한 상자에 담는 경우(Partition of Integers)에 대해서는 닫힌 형태의 공식(Closed formula)이 없음을 명시하고 나열식으로만 설명한다. (p. 378)

Open Questions

이해하지 못한 것

• Ramsey Theory (5.2절)에서 $R(5,5)$의 정확한 값이 아직 밝혀지지 않았다는 점이 흥미로우면서도 그 상한/하한 산출 방식이 복잡하여 추가 학습이 필요함. (p. 353)

더 알고 싶은 것

• 제2종 스털링 수($S(n, j)$)를 이용한 분할 문제가 실제 컴퓨터 과학의 데이터 클러스터링 등에서 어떻게 구체적으로 활용되는지 궁금함. (p. 378)