조합론

1. 순열·치환과 순환 Permutations and Cycles

조합론(combinatorics)은 유한한 대상들을 세고, 배열하고, 그 구조를 분석하는 수학 분야이다. 그 가장 기본적인 대상의 하나가 순열(permutation, 치환)이다. 집합 {1, 2, …, n}의 순열이란 이 집합을 자기 자신 위로 대응시키는 일대일 함수이며, 그러한 순열은 모두 n!개 있다. 한 순열은 각 원소 i가 어디로 가는지를 적어 다음과 같이 나타낼 수 있다.

이 순열을 분석하는 유용한 방법이 순환(cycle)으로 분해하는 것이다. 한 원소에서 출발해 "그 원소가 가는 곳"을 따라가다 처음 원소로 되돌아오면 하나의 순환이 닫힌다. 위 순열은 다음 순환들을 가진다.

순환들은 순열을 유일하게 결정한다. 그리고 길이가 1인 순환(자기 자신으로 가는 원소)은 짝맞춤(match, 고정점)에 대응한다. 그렇다면 "무작위 순열에서 순환들에 대해 무엇을 말할 수 있는가?"라고 물을 수 있다.

2. 중국집 과정(호페의 항아리) The Chinese Restaurant Process / Hoppe's Urn

순환구조를 분석하는 데 유용한, 1980년경 도입된 절차를 설명한다. 이것은 때때로 중국집 과정(Chinese Restaurant Process) 또는 호페의 항아리(Hoppe's urn)라 불린다.

처음에 리스트는 비어 있고, 항아리에는 검은 공 하나가 들어 있다. 공을 항아리에서 무작위로 차례로 뽑는다. 뽑은 공은 다시 넣되, 뽑은 순서 번호가 적힌 새 공 하나를 함께 넣는다. 그 번호는 리스트에도 기록한다. 첫 번째 뽑기에서는 1을 쓴다. j > 1번째 뽑기에서 검은 공을 뽑으면 j를 리스트의 맨 왼쪽에 쓰고, 그렇지 않으면 뽑은 공의 번호 오른쪽에 j를 쓴다.

예컨대 9번 뽑은 뒤 리스트가 9 5 8 3 6 4 1 2 7이라 하자. 그러면 검은 공은 1, 3, 5, 9번째 뽑기에서 나왔다. 그 번호들로 시작하는 구간들, 즉 1 2 7, 3 6 4, 5 8, 9 를 한 순열의 순환들이라 하면(이는 1절의 순열과 같다), n번 뽑은 뒤 이 절차는 1, 2, …, n의 n!개 순열 각각을 같은 확률로 만들어 낸다.

검은 공을 뽑을 때마다 새 순환이 시작된다. 그리고 이전에 무슨 일이 있었든 독립적으로, j번째 뽑기에서 검은 공을 뽑을 확률은 다음과 같다.

3. 순환의 개수와 제1종 스털링 수 Number of Cycles and Stirling Numbers

따라서 순환의 개수는, j번째 시행에서 성공확률이 1/j인 n개의 독립 시행에서의 성공 횟수와 같다.

이를 이용하면, 임의의 s에 대해 다음 항등식이 성립함을 보일 수 있다.

여기서 (부호 없는) 제1종 스털링 수(Stirling number of the first kind) [n k]는, 1, …, n의 순열 가운데 순환이 정확히 k개인 것의 수이다.

4. 가중 일반화와 푸아송–디리클레 분포 Weighted Generalization and the Poisson–Dirichlet Law

이제 검은 공이 무게 θ > 0을 갖고, 다른 모든 공의 무게는 1이며, 뽑기가 무게에 비례하여 이루어진다고 하자. 그러면 j번째 뽑기에서 검은 공을 뽑을 확률은 θ/(θ+j−1)이 된다.

θ > 1(θ < 1)이면 이는 순환이 많은(적은) 순열을 선호하게 되어, 이렇게 순열 위에 비균등(nonuniform) 분포를 얻는다. 나아가, 검은 공을 뽑을 때마다 이전에 쓰지 않은 새 색깔의 새 공 하나와 함께 다시 넣고, 다른 공을 뽑으면 같은 색의 새 공 하나와 함께 다시 넣는다고 하자(폴리아 항아리 모형(Pólya's urn model) 참조).

예를 들어, 항아리 속 서로 다른 색 공의 상대빈도를 크기 순으로 정렬한 것이, n → ∞일 때 이른바 푸아송–디리클레 분포(Poisson–Dirichlet distribution)로 수렴함을 증명할 수 있다.

5. 응용 Applications

위 절차에는 놀랄 만큼 많은 흥미로운 응용이 있으며, 그 분야도 해석적 정수론, 베이즈통계, 집단유전학, 생태학 등으로 매우 다양하다. 순열의 순환구조와 호페의 항아리는, 겉보기에 무관해 보이는 이런 영역들을 하나의 확률적 틀로 묶어 준다.

참고 및 관련 표제어

부록. 이 글에 나온 용어 (배경지식 보충)

• 조합론 (combinatorics) — 유한 대상을 세고 배열하며 그 구조를 분석하는 수학 분야.
• 순열·치환 (permutation) — {1,…,n}을 자기 자신으로 보내는 일대일 대응. 모두 n!개.
• 순환 (cycle) — 한 원소에서 시작해 상(image)을 따라가 되돌아오는 닫힌 구조. 순열을 유일하게 결정.
• 짝맞춤·고정점 (match / fixed point) — 길이 1의 순환. 짝맞춤 문제와 연결됨.
• 중국집 과정 / 호페의 항아리 — 균등 무작위 순열의 순환구조를 차례로 만들어 내는 항아리 절차.
• 제1종 스털링 수 [n k] — 순환이 정확히 k개인 n-순열의 수. 상승계승의 전개계수.
• 폴리아 항아리 모형 (Pólya's urn) — 뽑은 공을 같은 색 공과 함께 되넣는 강화(reinforcement) 모형.
• 푸아송–디리클레 분포 — 크기 정렬한 색 빈도의 극한분포. 매개변수 θ로 다양성 조절.
• 조화수 H_n — 1+1/2+…+1/n. 무작위 순열의 순환 수 기대값 ≈ ln n.
• 베르누이 시행 (Bernoulli trial) — 성공/실패 두 결과의 시행. 여기서 j번째 성공확률 1/j(또는 θ/(θ+j−1)).

한국보험시장 현황 Korea Market Practice

조합론은 보험 계리 실무에서 직접 언급되는 경우가 드물지만, 복수의 보험사건·담보·계약이 조합·교차할 때의 경우의 수를 정확히 다루는 기초 수학으로서 곳곳에 내재해 있다. 가장 직관적인 적용은 단체보험(단체생명·단체실손)의 구성원 중 k명이 동시에 보험사고를 당할 경우의 수를 셀 때다. 이항분포의 계수 C(n,k)가 그 핵심이며, 단체연금의 연생(joint-life) 분석에서도 조합론적 조건부 계산이 기초를 이룬다.

손해보험 요율 산정에서 조합론이 쓰이는 영역은 다중 담보 번들과 할인 구조다. 화재·배상책임·도난 등 N개 담보 중 일부를 선택하는 경우의 수, 상호배타적 사건들의 분할, 다중 위험원의 동시 발생 조합이 요율 분류 체계와 결합 한도 설계에 반영된다. GLM 기반 요율 모형에서도 범주형 변수들의 상호작용항(interaction) 개수는 조합론적으로 폭발적으로 증가하므로, 모형 복잡성 관리의 배경 논리로서 조합론적 사고가 작동한다.

IFRS17의 보험계약 묶음(group) 정의와 K-ICS 집합위험 분류에서도 조합론적 관점이 필요하다. 수익성 유사 계약을 25개 이내 집합으로 묶는 IFRS17 집합(cohort) 구성 규칙은 계약 분류의 경우의 수를 체계적으로 다루는 문제이며, 대규모 보험사의 수백 개 상품 포트폴리오에서 이를 자동화할 때 조합론적 알고리즘이 활용된다.