중복순열 (permutations with repetition)
쉽게 풀면
일반적인 순열은 한 번 뽑은 대상을 다시 뽑을 수 없지만(예: 카드 뽑기), 중복순열은 이미 뽑은 대상을 몇 번이고 다시 뽑을 수 있는 경우를 다룹니다. 예를 들어 0부터 9까지 숫자 10개를 이용해 4자리 비밀번호를 만든다고 하면, 같은 숫자를 여러 번 써도 되므로(예: 1111도 가능) 이는 중복순열입니다. 서로 다른 n개 중에서 r개를 중복을 허락해 순서대로 나열하는 경우의 수는 n^r로 계산됩니다. 앞의 비밀번호 예시라면 10^4 = 10000가지가 됩니다. 각 자리마다 독립적으로 10가지 선택이 가능하기 때문에 단순히 곱하기만 하면 되는 것이 핵심입니다.
왜 중요한가
중복순열은 같은 값을 여러 번 사용할 수 있는 상황에서 전체 경우의 수를 셀 때 쓰이는 가장 기본적인 도구이기 때문에, 암호학의 키 공간 크기 추정, 정보이론의 코드워드 개수 계산, 유전 서열이나 문자열 조합을 다루는 생물정보학 등 다양한 분야에서 등장합니다. 특히 비밀번호나 코드처럼 자릿수마다 독립적으로 값을 고를 수 있는 구조를 분석할 때, 전체 가능한 경우의 수가 얼마나 되는지를 보이는 근거로 자주 활용됩니다. 이 값은 시스템의 안전성이나 정보 표현 능력을 정량적으로 논의하는 출발점이 됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 0과 1(2가지)을 L자리에 걸쳐 중복을 허용하며 배열하는 경우의 수를 계산할 때, 중복순열 공식(2^L)을 그대로 적용했다는 뜻입니다.
보안 연구에서는 비밀번호처럼 각 자리에서 같은 문자를 반복해 사용할 수 있는 경우, 중복순열 공식을 이용해 전체 경우의 수를 구하고 이를 공격 난이도 추정의 근거로 삼습니다.
생물정보학에서는 DNA 서열처럼 정해진 몇 가지 요소가 반복적으로 나타날 수 있는 구조를 분석할 때, 중복순열 공식을 이용해 가능한 서열의 총 개수를 계산합니다.
조금 더 깊게 보면
중복순열의 값(n^r)은 대상 수 n이나 자리 수 r이 조금만 커져도 매우 빠르게 커지는데, 이런 성질은 보안 분야에서 키 공간이 충분히 커야 무차별 대입 공격에 안전하다는 논리의 근거로 쓰입니다. 반대로 자리마다 선택 가능한 값의 종류가 제한되어 있으면(예: 염기서열의 4가지 문자) 전체 경우의 수가 상대적으로 작아, 정보량을 나타내는 지표인 엔트로피 계산과도 연결됩니다. 실제 논문에서는 이 값을 그대로 제시하기보다, 로그를 취해 비트 단위의 정보량으로 환산해 제시하는 경우도 흔합니다.
주의할 점
중복순열(n^r)과 중복조합을 혼동하기 쉽습니다. 중복순열은 뽑은 것들의 "순서"까지 구분하지만, 중복조합은 순서를 따지지 않고 몇 개씩 뽑았는지만 셉니다. 예를 들어 사탕 3개를 색깔별로 몇 개씩 사는지는 중복조합이지만, 그 사탕들을 일렬로 늘어놓는 방법의 수는 중복순열에 가깝습니다.