Combinatorics & Counting

1. Overview

조합론과 카운팅(Combinatorics & Counting, CAC)은 세상 모든 가능한 경우의 수를 수학적으로 쥐어짜 내어, 우리가 짠 알고리즘이 "1초 안에 끝날지, 아니면 우주가 멸망할 때까지 돌아갈지"를 런타임 전에 미리 확정 짓는 '무한성 통제 공학'입니다.

학습자는 무식하게 하나씩 세는(Brute Force) 행위를 멈추고, 순서와 중복의 물리적 제약 조건을 수식으로 치환하는 **순열(Permutation)**과 **조합(Combination)**의 극한 물리를 배웁니다. 나아가 포함-배제 원리(PIE)와 점화식(Recurrence Relations)을 통해 겹치는 데이터를 쳐내고 이전 결과를 재활용하는 **동적 계획법(Dynamic Programming)**의 수학적 근원을 해부하며, 암호의 해독(Brute-force) 불가능성을 증명하는 아키텍처적 시야를 확보합니다.

2. Scope & Boundaries

In-Scope

• 기초 카운팅 물리 (Basic Counting): 합의 법칙(Rule of Sum), 곱의 법칙(Rule of Product), 비둘기집 원리(Pigeonhole Principle).
• 순열과 조합 (Permutations & Combinations): $nPr$ (순서 O), $nCr$ (순서 X), 중복 순열, 중복 조합(Stars and Bars) 메커니즘.
• 고급 조합론 (Advanced Combinatorics): 포함-배제 원리(Principle of Inclusion-Exclusion, PIE), 이항 정리(Binomial Theorem), 파스칼의 삼각형.
• 재귀와 점화식 (Recurrence & Induction): 점화식(Recurrence Relations), 선형 점화식의 특성 방정식, 카탈란 수(Catalan Numbers).

Out-of-Scope

• 알고리즘 코드의 구현 최적화: 동적 계획법(DP)을 배열을 써서 메모이제이션(Memoization) 코드로 옮기는 팁 $\rightarrow$ 04-03. Algorithm Design Techniques 영역.
• 연속 확률 분포 (Continuous Probability): 정규분포 적분 구하기 $\rightarrow$ 01-04. Probability & Statistics 영역.

Boundaries

• CAC vs. Algorithms (04-03): 알고리즘 설계(04-03)가 "어떻게 하면 CPU를 덜 쓰고 코드를 짤까?"라면, CAC는 코드를 짜기 전에 "이 문제의 전체 탐색 공간(Search Space) 크기가 팩토리얼($O(N!)$)인지, 지수($O(2^N)$)인지 수리적으로 증명하여 알고리즘의 한계를 미리 그어버리는" 예언자적 역할입니다.

3. Counterexample

• 조합 폭발의 무지 (Combinatorial Explosion Fallacy): "도시가 20개밖에 안 되니까, 모든 경로를 다 탐색해서 가장 짧은 길을 찾는 코드를 짜면 금방 돌겠지"라는 순진한 착각. 20개의 도시를 방문하는 경우의 수(순열)는 $20!$(약 $2.4 \times 10^{18}$)입니다. 초당 10억 번 연산하는 슈퍼컴퓨터로 돌려도 77년이 걸리는 무지막지한 '조합 폭발' 현상을 수학적으로 미리 계산(카운팅)하지 않고 코딩부터 시작하면 서버는 영원히 응답하지 않습니다.
• 중복 산정의 함정 (Double Counting Fallacy): A 집합과 B 집합의 크기를 더한 뒤, 교집합이 존재함에도 불구하고 빼주지 않는(포함-배제 원리 누락) 치명적 버그. 넷플릭스에서 '액션을 좋아하는 유저' 수와 'SF를 좋아하는 유저' 수를 더해서 마케팅 이메일을 돌렸는데, 둘 다 좋아하는 유저에게 이메일이 두 번 날아가 불만을 터뜨리는 사고는 기초적인 수리적 카운팅 실패에서 기인합니다.

4. Prerequisites

• 함수와 사상 (Basic): 팩토리얼(!) 연산과 단사/전사 함수의 맵핑 개념을 알면 비둘기집 원리를 이해하기 쉽습니다. (01-01-02 FAM)
• 기초 대수학 (Recommended): 다항식의 전개와 거듭제곱 연산에 익숙해야 이항 정리를 따라갈 수 있습니다.

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 합의 법칙, 곱의 법칙과 비둘기집 원리 (Basic Rules)

• Why to Learn: 프로그램이 가질 수 있는 상태(State)의 가짓수를 가장 직관적이고 빠르게 추산하여, switch-case 문이 몇 개나 필요할지 예측하기 위해서입니다.
• What to Learn:
  • Concepts: 합의 법칙(Mutually Exclusive), 곱의 법칙(Independent Events).
  • Skills: 의사 결정 트리(Decision Tree)의 잎(Leaf) 노드 수 계산, 비둘기집 원리(Pigeonhole Principle).
  • Tools: Tree Diagram.
  • Trade-offs: 모든 분기점마다 곱의 법칙으로 경우의 수가 폭발($2^N$)하여 코드가 복잡해지는 상태 머신 vs 도달 불가능한 상태를 수학적으로 쳐내어(합의 법칙) 상태의 수를 $O(N)$으로 억제하는 아키텍처 제어력.
• How to Learn:
  • 1단계: 티셔츠 3벌, 바지 2벌이 있을 때 코디하는 방법은 $3 \times 2 = 6$가지(동시성, 곱의 법칙)지만, 점심으로 한식 3개 중 하나 '또는' 중식 2개 중 하나를 고르는 방법은 $3 + 2 = 5$가지(배타성, 합의 법칙)인 물리적 분기를 뜯어봅니다.
  • 2단계: "서울시 인구가 1,000만 명이면, 머리카락 개수가 100% 똑같은 사람이 최소 2명 이상 존재한다"(사람 머리카락 수는 최대 10만 개 안팎)는 것을 비둘기집 원리로 수리적 증명합니다.
• Implement: 비밀번호를 영문 알파벳 26자와 숫자 10자리를 섞어 8자리로 만들 때, 가능한 전체 해시 공간(Hash Space)의 크기를 곱의 법칙으로 계산하여 해커가 무차별 대입(Brute-force)으로 뚫는 데 걸리는 시간(ms)을 출력하는 보안 스크립트.

Recommended

Core Topic 02: 순열과 조합, 그리고 별과 막대기 (Permutations & Combinations)

• Why to Learn: 데이터 배열에서 "순서를 유지해야 하는가?"와 "중복 선택을 허용하는가?"라는 물리적 제약을 단 한 줄의 수학 공식으로 압축해 버리기 위함입니다.
• What to Learn:
  • Concepts: 순열($nPr$), 조합($nCr$), 팩토리얼($n!$).
  • Skills: 중복 순열($n^r$), 중복 조합($nHr = {n+r-1 \choose r}$), 별과 막대기(Stars and Bars) 모델.
  • Tools: Python itertools.permutations, combinations.
  • Trade-offs: $N$개의 요소를 다 뒤집어 까서 완벽한 최적해를 찾는 순열 탐색($O(N!)$)의 절대적 정확성 vs 팩토리얼의 살인적인 연산량 때문에 15개만 넘어가도 컴퓨터가 뻗어버리는 런타임 참사.
• How to Learn:
  • 1단계: 10명의 유저 중 3명을 뽑아 1, 2, 3등 경품을 다르게 주는 상황(순서가 중요, 순열 $10P3$)과 3명 모두에게 동일한 쿠폰을 주는 상황(순서 무관, 조합 $10C3$)의 메모리 크기 차이를 수리적으로 분해합니다.
  • 2단계: 3명의 자녀에게 10개의 사탕을 나누어 주는 경우의 수를 구할 때, 사탕 10개(별) 사이사이에 칸막이 2개(막대기)를 배치하는 '별과 막대기(Stars and Bars)' 수학적 트릭을 해부합니다.
• Implement: 주어진 배열 요소들로 생성 가능한 모든 부분집합과 순열을 코드로 생성하되, 크기가 12개를 넘어가면 팩토리얼 폭발을 경고하며 연산을 강제 차단($Fail-fast$)하는 조합론 방어 모듈 작성.

Practical

Core Topic 03: 포함-배제 원리와 이항 정리 (PIE & Binomial Theorem)

• Why to Learn: 데이터베이스 쿼리를 짤 때, 여러 개의 OR 조건이 복잡하게 얽혀서 벤 다이어그램이 겹치는 부분의 유저 수를 중복 없이(Unique) 완벽하게 카운팅하기 위해서입니다.
• What to Learn:
  • Concepts: 포함-배제 원리(Principle of Inclusion-Exclusion, PIE), 이항 정리(Binomial Theorem).
  • Skills: 파스칼의 삼각형(Pascal's Triangle), 집합의 교차 크기 계산.
  • Tools: SQL UNION vs UNION ALL 역학.
  • Trade-offs: 3개 이상의 집합 조건이 겹칠 때, 이를 $A \cup B \cup C = A + B + C - (A \cap B + B \cap C + C \cap A) + (A \cap B \cap C)$처럼 수리적으로 완벽히 빼고 더하는(PIE) 논리적 정교함 vs 코드가 기하급수적으로 길어지는 쿼리 복잡도.
• How to Learn:
  • 1단계: "1부터 100까지의 숫자 중 2의 배수이거나 3의 배수인 것의 개수"를 찾을 때, 2의 배수와 3의 배수를 더하고 6의 배수(교집합)를 빼주어 중복 카운트를 제거하는 수순을 뜯어봅니다.
  • 2단계: $(x+y)^n$을 전개할 때 계수가 어떻게 떨어지는지 보여주는 이항 정리가 파스칼의 삼각형과 완벽하게 일치하며, 이것이 동전 던지기 확률(조합)과 물리적으로 연결되는 경이로움을 분석합니다.
• Implement: $N$개의 특성을 가진 데이터를 필터링할 때, 교집합 크기를 배열로 받아서 PIE 공식을 재귀적으로 돌려 최종 순수 유니크(Unique) 개수를 $O(2^N)$ 만에 도출하는 수학적 카운터 작성.

Advanced

Core Topic 04: 점화식과 카탈란 수 (Recurrence & Catalan)

• Why to Learn: "오늘의 결과는 어제와 그제의 결과의 합이다"라는 점화식 패턴을 발견하여, 지수 시간($O(2^N)$)이 걸리는 재귀 함수를 $O(N)$의 동적 계획법(DP) 코드로 폭발적으로 최적화하기 위함입니다.
• What to Learn:
  • Concepts: 선형 점화식(Linear Recurrence Relations), 카탈란 수(Catalan Numbers).
  • Skills: 특성 방정식(Characteristic Equation)을 이용한 일반항 도출, 분할 정복(Divide and Conquer) 상태 트리의 깊이 계산.
  • Tools: 하노이의 탑(Tower of Hanoi) 시뮬레이션.
  • Trade-offs: 피보나치 수열을 구할 때 이전 값을 변수에 저장해 두고 더해가는(DP) $O(N)$ 메모리 희생 vs 황금비 방정식(Binet's Formula)을 통해 $O(1)$ 만에 답을 때려 맞추는 수학적 우아함과 실수(Float) 연산 오차 한계.
• How to Learn:
  • 1단계: 하노이의 탑에서 $N$개의 원반을 옮기는 횟수가 $T_n = 2T_{n-1} + 1$이라는 점화식으로 표현되며, 이것을 풀면 $2^N - 1$이라는 닫힌 형태(Closed-form)의 지수 함수가 튀어나오는 물리적 역학을 뜯어봅니다.
  • 2단계: 괄호 ()()를 올바르게 닫는 경우의 수, 이진 탐색 트리(BST)의 모양 가짓수를 결정하는 신비로운 수열인 카탈란 수(Catalan Number, $\frac{1}{n+1}{2n \choose n}$)의 패턴을 분석합니다.
• Implement: 점화식 $F_n = F_{n-1} + F_{n-2}$ (피보나치)를 순수 재귀(Recursive), 메모이제이션(Top-down DP), 그리고 행렬 거듭제곱(Matrix Exponentiation) 알고리즘으로 각각 구현하고 $N=1000$일 때의 연산 틱(Tick)을 파괴적으로 비교하는 리포트 작성.

7. Terminology

8. References

Primary References

• [P1] CS2023 - DS/Basic Counting — Foundations of combinatorics.
• [P2] SWEBOK v4.0 - Computing Foundations / Discrete Mathematics — Counting for software metrics.

Secondary References

• [Concrete Mathematics] Knuth, Graham, Patashnik — The definitive guide to counting for CS.
• [A Walk Through Combinatorics] Miklos Bona — Comprehensive problem-solving guide.

Industry References

• [Cryptographic Key Space Analysis] — Counting in security standards.
• [Google Search Index Size Metrics] — Practical application of counting principles.

9. Final Checklist

Primary Checklist

• '독립적인 사건'과 '상호 배타적인 사건'의 차이를 곱의 법칙과 합의 법칙 사용 관점에서 물리적으로 설명할 수 있는 가? (P1)
• 이항 계수 $\binom{n}{r}$가 파스칼의 삼각형과 이항 정리에서 각각 어떤 물리적 의미를 갖는지 기술 가능한가? (P1)

Secondary Checklist

• 12자리의 무작위 문자열 비밀번호를 생성할 때, 대소문자와 숫자를 혼합하는 것이 단순 소문자 조합보다 경우의 수를 얼마나 물리적으로 확장시키는지 계산 가능한가?
• 정렬 알고리즘의 최악의 경우를 '순열의 역순 배치' 관점에서 보고 전체 탐색 공간을 계승(Factorial)으로 증명할 수 있는가?

Industry Checklist

• 대규모 분산 시스템에서 ID 생성을 위해 128비트 UUID를 쓸 때, 충돌 가능성(Collision Probability)을 생일 문제 모델로 산출하여 시스템 안정성을 입증할 수 있는 가? (SFIA)
• 웹 크롤링 시, 방문한 URL의 포함-배제 조건을 설계하여 불필요한 중복 요청을 수학적으로 최소화하는 로직을 제안할 수 있는 가?