이산수학 1강. 조합론: 세는 법의 과학
세는 것은 산수가 아니라 과학입니다. 그리고 제대로 세어 보면, 우리의 직관은 자주 배신당합니다.
풀고 시작
곱의 법칙과 합의 법칙
조합론(combinatorics)은 경우의 수를 세는 수학입니다. 그런데 도구 상자를 열어 보면 의외로 단출합니다. 딱 두 개뿐이거든요. 두 선택이 연달아 일어나면 경우의 수를 곱하고(곱의 법칙), 두 선택이 양자택일이면 더합니다(합의 법칙). 상의 4벌과 하의 3벌로 만드는 옷차림은 4 × 3 = 12가지이고, 버스 3개 노선 또는 지하철 2개 노선으로 가는 방법은 3 + 2 = 5가지죠. 규칙은 이 둘뿐이지만, 무엇이 "연달아"이고 무엇이 "양자택일"인지 문제를 구조로 분해하는 눈이 바로 조합론의 실력입니다.
이 세는 기술이 학문이 된 계기는 뜻밖에도 도박이었습니다. 1654년 파스칼과 페르마는 도박사 드 메레가 던진 판돈 분배 문제를 두고 서신을 주고받았고, 경우의 수를 체계적으로 세는 이 교환에서 확률론이 태어났습니다. 세는 법은 곧 불확실성을 다루는 법이었던 셈이죠.
순열과 조합: 순서가 있는가 없는가
n개에서 k개를 뽑아 줄 세우는 방법의 수가 순열(permutation)입니다. 첫 자리에 n가지, 다음 자리에 n−1가지가 오므로 곱의 법칙에 따라 P(n, k) = n × (n−1) × … × (n−k+1)이 됩니다. 순서를 무시하고 묶음만 고르면 조합(combination)이죠. 뽑은 k개를 줄 세우는 방법 k!만큼 중복이 생기므로, C(n, k) = n!/(k!(n−k)!)로 나눠 줍니다. 순열과 조합의 차이는 공식이 아니라 질문의 차이입니다. 반장과 부반장을 뽑는가(순서 있음), 청소 당번 두 명을 뽑는가(순서 없음).
수치는 금방 커집니다. 카드 52장을 섞는 방법은 52!로, 약 8 × 10⁶⁷가지입니다. 당신이 방금 제대로 섞은 카드 순서는 인류 역사상 한 번도 나온 적 없는 배열일 가능성이 압도적으로 높습니다. 조합도 마찬가지입니다. 로또처럼 45개 숫자에서 6개를 고르는 경우의 수는 C(45, 6) = 8,145,060가지로, 800만 분의 1이라는 당첨 확률이 여기서 나오죠.
생일 역설: 직관을 배반하는 계산
앞의 문제를 실제로 세어 봅시다. 요령은 여사건입니다. "적어도 두 명이 같다"의 반대인 "23명 전원의 생일이 다르다"를 계산하는 거죠. 첫 사람은 아무 날이나 되고(365/365), 둘째는 남은 364일 중 하나(364/365), 셋째는 363/365여야 합니다. 이렇게 23번째 사람의 343/365까지 전부 곱하면 약 0.493이 나옵니다. 따라서 겹칠 확률은 1 − 0.493 ≈ 0.507, 즉 절반을 넘습니다. 57명이면 99%를 넘죠.
직관이 틀리는 이유는 비교 대상을 잘못 세기 때문입니다. 사람은 23명이지만 두 사람의 쌍은 C(23, 2) = 253개입니다. 253번의 비교 기회가 있다고 생각하면 50%가 이상하지 않죠. 이 역설은 실무에서도 중요합니다. 해시 함수의 충돌 가능성을 추정하는 암호학의 "생일 공격"이 정확히 이 계산 위에 서 있거든요.
조합 폭발: 다 세어 볼 수 없는 세계
조합의 수는 지수적으로, 때로는 계승(factorial)적으로 폭발합니다. 이것을 조합 폭발(combinatorial explosion)이라 부릅니다. 암호가 안전한 이유가 바로 이것입니다. 정수론 4강에서 본 RSA도 결국 키 후보의 공간이 전수조사 불가능할 만큼 크다는 사실에 기댑니다. 바둑이 어려운 이유도 같습니다. 19 × 19 반상의 합법적 돌 배치는 약 10¹⁷⁰가지로, 관측 우주의 원자 수(약 10⁸⁰)보다 압도적으로 많습니다. 섀넌이 1950년에 추정한 체스의 게임 수 10¹²⁰(섀넌 수)도 같은 교훈을 줍니다. 완전한 계산이 불가능하니 기계도 사람도 탐색과 직관에 의존해야 하는 거죠.
계산 이론에서는 이 폭발이 문제의 난이도 그 자체가 됩니다. 도시 n개를 도는 최단 경로를 찾는 순회 판매원 문제의 후보 경로는 n!개 규모로 자라고, 이런 문제들을 다루는 것이 복잡성 이론의 P 대 NP 문제입니다. 세는 법의 과학은 이렇게 "무엇이 계산 가능한가"라는 질문으로 이어집니다.
인출 문제
생각해볼 질문 (정답 없음)
- 생일 역설처럼 직관이 계산을 배반하는 다른 사례를 일상에서 찾을 수 있을까요. 직관은 왜 하필 이런 유형의 문제에서 약할까요.