이 계산기가 하는 일
이 도구는 중복조합(다중집합 계수라고도 함)을 표로 만들어 줍니다. 서로 다른 n가지 항목이 있을 때, 각 항목을 몇 번이든 중복해서 고를 수 있다고 가정하고 크기가 r인 순서 없는 선택이 몇 가지인지 계산합니다. 시작값부터 끝값까지의 모든 정수 r에 대해 결과를 보여 줍니다. 이 함수는 \(H(n, r)\)로 표기하며, 이항계수 \(C(n + r - 1, r)\)과 같습니다.
사용 방법
서로 다른 항목의 개수 n(1 이상)을 입력한 다음, r의 시작값과 끝값을 입력하세요. 계산기는 각 r마다 한 줄씩, 정확한 값 \(H(n, r)\)을 표로 출력합니다. 이 수치는 매우 빠르게 커지기 때문에, 계산 엔진은 큰 정수를 정확히 다루는 빅인티저(big-integer) 연산을 사용합니다. 따라서 표가 커져도 오차 없이 정확합니다.
공식 풀이
고전적인 "별과 막대(stars and bars)" 논증에 따르면, n가지 종류에서 중복을 허용해 r개를 고르는 것은, 똑같이 생긴 별 r개를 막대 n − 1개로 나뉜 n개의 칸에 배치하는 것과 같습니다. 이 n + r − 1개 기호의 배열 수가 바로 \(C(n + r - 1, r)\)입니다.
$$\overline{C}(n, r) = \binom{\text{Items }(n) + r - 1}{r} = \frac{\left(\text{Items} + r - 1\right)!}{r!\,\left(\text{Items} - 1\right)!}$$기억해 둘 두 가지 특수한 경우가 있습니다. \(H(n, 0) = 1\)(아무것도 고르지 않는 경우)이고, \(H(1, r) = 1\)(하나뿐인 항목을 r번 고른 다중집합은 단 한 가지)입니다.
예제 풀이
\(n = 5\), r을 0부터 4까지로 두어 봅시다. \(H(5,0) = C(4,0) = 1\), \(H(5,1) = C(5,1) = 5\), \(H(5,2) = C(6,2) = 15\), \(H(5,3) = C(7,3) = 35\), \(H(5,4) = C(8,4) = 70\)이 됩니다. 따라서 표는 1, 5, 15, 35, 70으로 나옵니다. 한 번 더 확인해 보면,
$$H(30,4) = C(33,4) = \frac{33 \cdot 32 \cdot 31 \cdot 30}{24} = 40920$$입니다.
자주 묻는 질문
일반 조합과는 어떻게 다른가요? 일반 조합 \(C(n, r)\)은 같은 항목을 두 번 고를 수 없습니다. 반면 여기서는 각 항목을 여러 번 고를 수 있기 때문에 지수가 \(n + r - 1\)로 바뀝니다.
순서가 중요한가요? 아니요. {A, A, B}와 {B, A, A}는 같은 선택입니다. 순서가 중요하다면 중복순열(\(n^r\))을 사용해야 합니다.
왜 값이 이렇게 커지나요? 다중집합 계수는 r에 대해 대략 \(n - 1\)차 다항식처럼 증가합니다. 그래서 n이나 r이 커지면 천문학적으로 큰 정수가 나오는데, 이 계산기는 정확한 연산으로 이를 처리합니다.
