중복순열이란?
중복순열(repetition이 허용되는 순열)은 서로 다른 n개의 원소로 이루어진 집합에서 r개를 골라 순서를 정해 나열하되, 같은 원소를 몇 번이든 다시 쓸 수 있을 때 가능한 경우의 수를 세는 것입니다. r개의 자리 각각을 n개 원소 중 어느 것으로든 자유롭게 채울 수 있으므로, 전체 경우의 수는 n을 r번 곱한 값, 즉 \({}_{\text{n}}\Pi_{r} = \text{n}^{\,r}\)이 됩니다. 이는 같은 원소를 다시 쓸 수 없는 보통의 순열 \({}_{\text{n}}P_{r} = \frac{n!}{(n-r)!}\) 과는 구별됩니다.
계산기 사용 방법
서로 다른 원소의 개수 \(n\)을 입력한 다음, \(r\)의 시작값과 끝값을 지정하세요. 이 도구는 해당 범위(양 끝값 포함)에 속하는 모든 정수 \(r\)에 대해 한 행씩 만들어 \(n^r\) 값을 출력합니다. 이 수치는 매우 빠르게 커지기 때문에, 계산기는 내부적으로 정확한 큰 정수 연산을 사용하며 화면에 표시할 유효숫자 자릿수를 직접 선택할 수 있습니다(기본값 18자리). 시작값을 끝값보다 크게 입력하면 두 값이 서로 바뀌어, 표는 항상 오름차순으로 표시됩니다.
공식 풀이
핵심 규칙은 다음과 같습니다.
$$ {}_{\text{n}}\Pi_{r} = \text{n}^{\,r}, \quad r = \text{r}_{\text{start}}, \dots, \text{r}_{\text{end}} $$
r개의 자리 각각이 n개 선택지 중에서 독립적으로 결정되므로, 곱의 법칙에 따라 경우의 수가 곱해집니다. 즉 \(n \times n \times \dots \times n\) (인수 r개)이 되는 것이죠. 특수한 경우도 여기서 바로 따라옵니다. \(r = 0\)일 때는 아무것도 나열하지 않는 단 하나의 경우(빈 나열)만 존재하므로 모든 n에 대해 \(n^0 = 1\)이며, 여기서는 \(0^0 = 1\)로 약속합니다. \(n = 0\)이고 \(r > 0\)인 경우에는 배치할 원소 자체가 없으므로 경우의 수는 0입니다.
풀이 예시
\(n = 17\), \(r\)을 0부터 20까지 변화시키면 표는 1, 17, 289, 4,913, 83,521, … 으로 시작해 \(r = 20\)에서 \(17^{20} = 4{,}064{,}231{,}406{,}647{,}572{,}522{,}401{,}601\), 즉 약 \(4.06 \times 10^{24}\)로 끝납니다. 간단히 확인해 볼 수 있는 예로, \(n = 2\)이고 \(r\)이 0부터 4까지라면 1, 2, 4, 8, 16이 나오는데, 이는 각 길이별 이진 문자열의 개수와 정확히 일치합니다.
자주 묻는 질문
왜 \(n^0 = 1\)인가요? 원소를 하나도 나열하지 않는 방법, 즉 아무것도 고르지 않는 경우가 단 한 가지 존재합니다. 이 빈 나열 덕분에 공식이 일관성을 유지합니다.
nPr과는 어떻게 다른가요? 보통의 순열 \({}_{\text{n}}P_{r}\)은 원소의 재사용을 허용하지 않아 \(\frac{n!}{(n-r)!}\) 이 됩니다. 반면 중복순열은 재사용이 가능하므로 모든 자리가 n개 선택지를 가지며, 답은 \(n^r\)이 됩니다.
왜 큰 수는 반올림되어 표시되나요? 내부 연산은 정확하지만, 매우 큰 결과값은 가독성을 위해 지정한 유효숫자 자릿수로 표시됩니다.
