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

쉽게 말하면

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

예시

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

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