중복순열

중복순열은 보통의 순열과 비슷하지만, 바탕이 되는 집합 M의 원소가 되풀이될 수 있다.

정의와 공식

전형적인 예로 시작하자. 영어 알파벳(abc … xyz, 모두 26자)으로 길이가 6인 낱말을 몇 개 만들 수 있을까? 여섯 글자는 많지 않지만 낱말은 꽤 많을 것이다. 낱말의 뜻은 따지지 않으므로 “weqrww”도 길이가 6인 올바른 낱말로 본다.

계산하는 데는 곱의 법칙만 알면 된다. 쓸 수 있는 서로 다른 글자는 모두 26개이다. 첫째 자리에는 26개 글자 가운데 하나를 넣을 수 있다. 둘째 자리에도 26개 글자 가운데 하나를 넣을 수 있다. 글자가 되풀이되면 안 된다는 조건을 두지 않았기 때문이다. 그래서 자리마다 26개 글자 가운데 하나를 고르게 되고, 곱의 법칙에 따라 중복순열의 수는 모두 26⁶ = 308,915,776이다. 글자 26개만 썼는데도 꽤 많다.

크기가 n인 집합 M에서 k개를 고르는 중복순열은 집합 M의 원소로 이루어진 k개의 순서 있는 나열 가운데, 각 원소가 k번까지 나올 수 있는 것을 모두 말한다. 예를 들어 집합 M = {1, 2, 3}이 있으면 (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3)은 모두 네 개를 고르는 올바른 중복순열이다. 이런 중복순열의 수를 {}_nΠ_k로 나타내면 다음과 같다.

$${}_n{\mathrm{\Pi }}_k=n^k.$$

풀이가 있는 예제

1. 숫자를 되풀이해서 써도 될 때, 숫자 {2, 4, 6, 8}로 여섯 자리 수를 몇 개 만들 수 있을까? 공식에 대입하기만 하면 된다. 집합의 크기는 4이고 여섯 개를 고른다.

   $${}_4{\mathrm{\Pi }}_6=4^6=4096.$$

2. 컴퓨터에서는 보통 이진법, 즉 숫자 0과 1만 쓰는 진법을 쓴다. 여기서 새로운 단위를 쓴다. 예를 들어 비트는 0이나 1 가운데 하나를 저장하는 칸이다. 더 큰 단위인 바이트(byte)는 8비트로 이루어진다. 그래서 1은 1비트이고 01110001은 1바이트이다. 1바이트를 8비트로 채우는 방법은 몇 가지일까?

   집합 {0, 1}, 즉 원소 두 개에서 고른다. 크기가 k = 8인 나열을 고르므로 경우의 수는 모두 다음과 같다.

   $${}_2{\mathrm{\Pi }}_8=2^8=256.$$

3. 앞의 예제에서 1바이트로 서로 다른 값을 256가지까지 구별할 수 있다는 것을 알았다. 4바이트를 채우는 방법은 몇 가지일까?

   4바이트는 4 · 8 = 32비트이고, 이번에도 크기가 2인 집합에서 고른다. 따라서 결과는 다음과 같다.

   $${}_2{\mathrm{\Pi }}_{32}=2^{32}=\mathrm{4,294,967,296.}$$

   고작 4바이트로 40억 가지가 넘는 값을 구별할 수 있다. 참고로 오늘날 컴퓨터의 디스크는 수백 기가바이트에서 테라바이트에 이른다. 1테라바이트는 1,000,000,000,000바이트, 즉 8,000,000,000,000비트이다. 그래서 1테라바이트 디스크에는 서로 다른 값을 2^{8,000,000,000,000}가지까지 저장할 수 있다.

   참고: 요즘 킬로바이트(메가바이트 등)라는 말은 조금 혼란스럽다. 기술적인 이유로 1킬로바이트는 다른 단위의 관례(1킬로그램은 1000그램)처럼 1000바이트가 아니라 2¹⁰바이트, 즉 1024바이트였다. 1메가바이트는 2²⁰바이트, 즉 2¹⁰킬로바이트였다.

   그래서 지금은 두 가지 표기를 구별한다. 1 kB(킬로바이트)는 1000바이트이고 1 KiB(키비바이트)는 2¹⁰ = 1024바이트이다.

4. 또 다른 예는 비밀번호의 안전성을 다룬 별도의 글에 있다.