Combinatorics & Counting

1. Overview

조합론 및 카운팅(Combinatorics & Counting, CNC)은 유한한 구조 내에서 특정 조건을 만족하는 객체의 개수를 물리적으로 세는 원리와 기법을 다룹니다.

컴퓨터 과학에서 '몇 가지 경우인가'라는 질문은 곧 '얼마나 많은 자원이 필요한가'라는 질문과 같습니다. 학습자는 순서의 유무에 따른 **순열(Permutations)**과 조합(Combinations), 복잡한 중복을 제거하는 포함-배제 원리(Inclusion-Exclusion), 그리고 점화식을 통해 변화를 추적하는 재귀적 카운팅을 배웁니다. 이를 통해 알고리즘의 최악/평균 시간 복잡도를 계산하고, 암호학적 공격 가능성이나 네트워크 경로의 가짓수를 정밀하게 예측하는 능력을 갖춥니다.

2. Scope & Boundaries

In-Scope

• Counting Principles: 합의 법칙, 곱의 법칙 및 나눗셈의 법칙을 통한 논리적 분해
• Arrangements: 순열, 조합, 중복 순열/조합의 수리적 공식과 결정 물리
• Advanced Counting: 카탈란 수(Catalan numbers), 이항 계수와 파스칼의 삼각형 역학
• Identity Proofs: 이항 정리(Binomial Theorem) 및 대칭적 조합 법칙의 수리 증명

Out-of-Scope

• 무한 집합의 카운팅 (01-02 FAM 영역으로 위임)
• 연속 확률 분포에서의 적분 연산 (04-01 PSR 영역으로 위임)

Boundaries

• CNC vs. Complexity Theory: 복잡도 이론이 '연산의 증가 추세'에 집중한다면, CNC는 그 추세의 기반이 되는 '정확한 개별 경우의 수'를 물리적으로 산출하는 기법에 집중합니다.

3. Counterexample

• 단순히 "공식에 대입해 답을 구하는 것"은 CNC 학습이 아닙니다. 왜 특정 문제에서 중복 조합 모델을 적용해야 하는지 데이터의 '구분 불가능성'을 수학적으로 논증할 수 있어야 하고, 대규모 시스템 설계 시 생일 역설(Birthday Paradox) 원리에 따라 충돌 발생 예상 시점을 물리적으로 계산하지 못하는 것은 CNC적 사고가 결여된 것입니다.

4. Prerequisites

• 집합론 및 관계 (Basic): 원소의 개수 및 집합 연산 개념이 필수입니다. (01-01 STR)
• Functions & Mappings (Recommended): 정의역과 공역 사이의 관계를 통한 카운팅 이해가 권장됩니다. (01-02 FAM)

5. Learning Map

1. Foundational Rules: 합과 곱의 법칙을 통해 복잡한 문제를 단순한 조각으로 쪼개는 법을 익힙니다.
2. Selection Mechanics: 순서와 중복 여부에 따라 대상을 뽑고 나열하는 물리적 케이스를 분류합니다.
3. Advanced Symmetry: 이항 계수 등 숫자의 대칭성과 패턴을 이용해 거대한 계산을 간소화합니다.
4. Algorithmic Projection: 계산된 경우의 수를 알고리즘 수행 시간이나 공간 비용으로 전사(Projection)합니다.

6. Learning Topics

Basic

Core: 카운팅의 기본 법칙 (Counting Basics)

• Why to Learn: 복잡한 상황을 논리적 합(OR)과 곱(AND)으로 분해하여 오류 없이 개수를 세기 위함입니다.
• What to Learn:
  • 합의 법칙: 서로소인 사건들의 결합 물리
  • 곱의 법칙: 독립적인 단계가 연속될 때의 가짓수 증폭
  • 트리 다이어그램: 체계적인 경우의 수 나열과 시각화
• How to Learn:
  • 비밀번호 설정 규칙(소문자 1개 이상 등)에 따른 전체 가능 조합 수를 단계별로 계산
  • 중복 포함을 방지하기 위해 집합의 크기를 뺄셈으로 보정하는 나눗셈 법칙 적용 실습
• Implement: 메뉴 선택지 조합에 따른 전체 결과물 생성기(Enumerator)

Recommended

Core: 순열과 조합의 물리 (Permutations & Combinations)

• Why to Learn: 데이터가 정렬되어 있는지, 혹은 구분이 되는지에 따라 처리 방식을 결정하기 위해서입니다.
• What to Learn:
  • 순열($P$): 순서가 중요한 배열 물리 (암호 해독 가짓수 등)
  • 조합($C$): 순서와 상관없는 선택 물리 (그룹핑, 부분집합 개수 등)
  • 중복 허용 모델: 중복 순열($n^r$)과 중복 조합($H$)의 구분 및 변환 역학
• How to Learn:
  • $n$명의 사원을 $k$개의 팀으로 나누는 방법의 수를 순열과 조합 중 어떤 모델이 적합한지 토론
  • 칸막이 기법(Stars and Bars)을 이용해 구분되지 않는 아이템을 구분되는 상자에 담는 방법 계산
• Implement: 주어진 배열로부터 모든 순열과 조합을 생성하는 재귀 알고리즘

Practical

Core: 포함-배제 원리와 뫼비우스 반전 (Inclusion-Exclusion)

• Why to Learn: 겹치는 영역이 많은 복잡한 조건부 데이터셋의 총량을 정확히 계산하기 위함입니다.
• What to Learn:
  • 포함-배제 원리: 2개, 3개 이상의 집합이 얽혔을 때의 가감 시퀀스
  • 완전 순열(Derangements): 어떤 원소도 자기 자리에 있지 않은 특수한 재배치 물리
  • 비둘기집 원리의 응용: 최소한 동일한 결과가 발생하는 지점의 물리적 확정
• How to Learn:
  • 1부터 1000 사이에서 2, 3, 5의 배수가 아닌 숫자의 개수를 수동 및 수식으로 비교 계산
  • 이메일 수신함에서 여러 필터가 겹칠 때 실제 보여질 메시지 수를 예산(Pre-counting)하는 시나리오 분석
• Implement: 다중 교집합을 갖는 데이터 세그먼트의 전체 유니크 카운트 산출 모듈

Advanced

Core: 생성 함수와 점화식 분석 (Generating Functions)

• Why to Learn: 반복되는 패턴의 개수를 일반화된 수식으로 고정하여 초고속 연산을 수행하기 위해서입니다.
• What to Learn:
  • 선형 점화식: 피보나치 수열 등 이전 단계가 다음 단계의 개수를 결정하는 물리
  • 생성 함수(Generating Functions): 카운팅 문제를 다항식의 계수(Coefficient) 분석 문제로 치환
  • 이항 정리와 특수 숫자: 파스칼 삼각형의 행 합계가 $2^n$이 되는 물리적 이유
• How to Learn:
  • 괄호 쌍의 유효한 조합 수(Catalan Numbers)를 점화식으로 유도하고 그 기하학적 의미 탐구
  • 동전 바꾸기 문제(Partition problem)를 생성 함수를 이용해 수식으로 풀어보는 실습
• Implement: 특정 점화식을 입력받아 $n$번째 경우의 수를 즉각 도출하는 다항식 연산기

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의 포함-배제 조건을 설계하여 불필요한 중복 요청을 수학적으로 최소화하는 로직을 제안할 수 있는 가?