중복조합 (Combinations with Repetition)
쉽게 풀면
일반적인 조합은 "사과, 배, 포도 중 2개를 고르는데 이미 고른 과일은 다시 못 고른다"는 규칙이지만, 중복조합은 "과일 가게에서 사과, 배, 포도 중 2개를 사는데 같은 과일을 두 개 사도 된다"는 상황입니다. 즉 사과 2개, 배 2개, 포도 2개, 사과+배, 사과+포도, 배+포도까지 모두 가능한 경우로 셉니다. 이런 "중복 허용" 경우의 수는 보통 조합 공식을 그대로 쓰면 틀리기 때문에, 뽑을 개수 r개와 종류 사이의 경계를 막대기로 표시하는 방식(칸막이 기법)으로 바꿔 계산합니다.
왜 중요한가
중복조합은 "같은 대상을 여러 번 선택할 수 있는데 순서는 상관없는" 상황을 셀 때 쓰이는 기본 도구로, 조합론 자체뿐 아니라 알고리즘의 경우의 수 분석, 확률·통계에서의 표본공간 계산, 자원 배분 문제 등 여러 분야에서 밑바탕이 됩니다. 예를 들어 유한한 종류의 자원을 여러 사람이나 항목에 나누어주는 문제, 또는 동일한 라벨을 여러 곳에 중복 배정하는 문제는 중복조합으로 환원되는 경우가 많습니다. 이 때문에 조합론을 다루는 논문뿐 아니라 실험 설계, 컴퓨터공학의 자료구조·알고리즘 논문에서도 경우의 수를 정당화하는 도구로 자주 인용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 응답자가 여러 선택지 중 일부를 중복으로 골라도 되는 상황에서, 가능한 응답 조합의 총 개수를 중복조합 공식으로 구했다는 뜻입니다.
이 문장은 생산 공정이나 자원 배분 최적화 연구에서, 동일한 부품 종류를 여러 곳에 중복해서 배정할 수 있을 때 가능한 배정 방식의 수를 중복조합으로 어림잡아 상한선을 계산했다는 의미입니다.
이 문장은 생물정보학에서 특정 길이의 서열을 이루는 구성 요소(염기 등)가 반복해서 등장할 수 있을 때, 순서를 따지지 않고 그 조성의 가짓수를 세는 데 중복조합 개념이 쓰였다는 뜻입니다.
조금 더 깊게 보면
중복조합의 개수는 흔히 "별과 막대(stars and bars)" 기법으로 유도되며, n종류에서 중복을 허용해 r개를 뽑는 경우의 수는 (n+r-1)개 중 r개를 고르는 일반 조합의 개수와 같다는 대응 관계로 표현됩니다. 이 대응 덕분에 복잡해 보이는 중복 선택 문제를 이미 잘 알려진 조합 공식으로 바꿔 계산할 수 있습니다. 논문에서는 이 값을 직접 계산하기보다, 경우의 수의 규모(예: 다항식 차수, 조합적 폭발 여부)를 논할 때 근거로 인용하는 경우가 많으며, 정수해의 개수를 세는 문제(예: x1+x2+...+xn = r을 만족하는 음이 아닌 정수해의 수)와도 수학적으로 동일한 구조를 가진다는 점이 자주 언급됩니다.
주의할 점
중복조합은 순서를 따지지 않는다는 점에서 순열과 조합 중 조합에 가깝지만, 같은 원소를 여러 번 선택할 수 있다는 점이 일반 조합과 다릅니다. 순서까지 따지면서 중복을 허용하는 경우(중복순열)와 혼동하지 않도록 주의해야 합니다.