# 조합론 (Combinatorics)

조합론(combinatorics)은 유한 집합에서 원소를 고르거나(조합), 순서대로 배열하거나(순열), 특정 조건을 만족하는 구조의 개수를 세는 방법을 연구하는 수학 분야입니다. 경우의 수를 정확히 알면 어떤 사건이 일어날 확률을 계산할 수 있어, 확률론·컴퓨터 과학·암호학의 기초 도구가 됩니다.

## 자세히 알아보기

기본 공식은 다음과 같습니다.
- 곱의 법칙: 독립적인 선택 a가지와 b가지를 함께 하면 a × b가지.
- 순열: n개 중 r개를 순서 있게 고르는 방법 nPr = n!/(n−r)!.
- 조합: n개 중 r개를 순서 없이 고르는 방법 nCr = n!/(r!(n−r)!).
- 중복 순열: n가지 기호로 길이 r인 문자열을 만드는 방법 n^r.

이 밖에 포함-배제 원리, 비둘기집 원리, 생성 함수, 그래프 이론, 라틴 방진 같은 조합 설계도 조합론에 속합니다. 비둘기집 원리는 '입력이 출력보다 많으면 반드시 충돌이 있다'는 사실을 보장하며, 해시 함수에 충돌이 존재할 수밖에 없는 이유입니다.

## 블록체인·암호화폐에서는

- 키 공간: 256비트 개인 키 공간은 약 2^256가지이며, secp256k1에서 유효한 개인 키는 1부터 n−1까지 약 1.16 × 10^77개입니다. 무차별 대입이 불가능하다는 판단은 이런 경우의 수 계산에서 나옵니다.
- 니모닉: BIP-39 단어 목록은 2,048개이고 12단어 문구는 2048^12 = 2^132가지 단어열 중 체크섬을 만족하는 2^128가지가 유효합니다. 단어 몇 개를 잃어버렸을 때 복구 가능성도 조합 계산으로 판단합니다. 4단어를 모르고 위치도 모르면 경우의 수가 급격히 늘어납니다.
- 생일 문제: N가지 값 중 무작위로 뽑을 때 충돌이 일어날 확률이 50%에 이르려면 약 1.18√N번이면 됩니다. 그래서 256비트 해시의 충돌 저항성은 128비트 수준이며, 160비트 주소 공간의 충돌 탐색은 약 2^80번 수준입니다.
- 조합 최적화: 블록 생산자가 수수료를 최대화하도록 트랜잭션을 고르는 문제는 배낭 문제와 비슷한 조합 최적화입니다.

## 쉽게 말하면

조합론은 '가능한 경우가 모두 몇 가지인가'를 빠짐없이, 중복 없이 세는 기술입니다.

## 예시

45개 번호 중 6개를 고르는 로또의 경우의 수는 45C6 = 8,145,060가지입니다. 같은 6개를 순서까지 따지면 6! = 720배가 됩니다.

BIP-39 12단어 중 단어 1개를 잊었고 위치도 모른다면 12 × 2,048 = 24,576가지만 시도하면 됩니다. 그러나 위치를 알더라도 단어 4개를 모르면 2048^4 ≈ 1.8 × 10^13가지로 늘어납니다.

---
출처: https://achivx.kr/glossary/combinatoric-%EC%A1%B0%ED%95%A9%EB%A1%A0%EC%A0%81-jo-hab-ron-jeok/ · ACHIVX 용어 사전 · 수정일 2026-10-20