중복순열

1. 개요

중복순열은 크기가 n인 유한 집합 E의 원소로 구성된 k-튜플 또는 집합 {1, 2, …, k}에서 E로의 사상으로 정의된다. 중복을 허용하여 서로 다른 n개의 원소에서 r개를 뽑아 나열하는 경우의 수는 n^r개이며, 크기가 n인 유한 집합 E와 자연수 k에 대해 E의 원소로 이루어진 k-중복 순열의 개수는 n^k개이다. 이러한 개념은 다양한 경우에 적용될 수 있으며, 예를 들어, 여러 종류의 음료를 주문하는 경우의 수, 특정 조건을 만족하는 자연수의 개수, 또는 모스 부호의 단어 개수를 계산하는 데 활용된다.

2. 정의

중복 순열을 정의하는 방법은 다음과 같다.

* 정의 1: 크기가 $n$인 유한 집합 $E$와 음이 아닌 정수 $k$가 주어졌을 때, $E$의 원소로 이루어진 $k$-중복 순열 (또는 $n$개의 원소에서 중복을 허용하여 $k$개 선택하여 만들어지는 $k$-항 순열)은 $E$의 원소를 요소로 하는 $k$-순서쌍 ($k$-항의 유한 수열)을 말한다.

2.1. k-튜플 (순서쌍)

크기가 인 유한 집합 와 음이 아닌 정수 가 주어졌을 때, 의 원소로 이루어진 -중복 순열 (또는 개의 원소에서 중복을 허용하여 개 선택하여 만들어지는 -항 순열)은 의 원소를 요소로 하는 -순서쌍 (-항의 유한 수열)을 말한다.

2.2. 사상

중복 순열을 정의하는 방법에는 여러 가지가 있다.

* 정의 2: 크기 $n$ ($n \in \mathbb{N}^*$)인 유한 집합 $E$와 음이 아닌 정수 $k$가 주어졌을 때, $E$의 원소로 이루어진 $k$-중복 순열은 집합 $\{1, 2, \dots, k\}$에서 $E$로의 사상을 말한다.

3. 중복 순열의 수

서로 다른 $n$개의 원소에서 $r$개를 중복을 허락하여 뽑아 한 줄로 나열하는 경우의 수를 중복순열의 수라고 한다. 이때, 각 자리마다 $n$가지의 원소를 선택할 수 있으므로, 중복 순열의 수는 $n^r$이 된다.

예를 들어, 1, 2, 3 세 개의 숫자 중 중복을 허용하여 두 개를 뽑아 나열하는 경우의 수는 다음과 같이 9가지이다.

3.1. 증명

서로 다른 $n$개의 원소에서 $r$개를 중복을 허락해 뽑아 한 줄로 나열할 때, 첫 번째에서 $n$개를 선택할 수 있고 그 뒤로 두 번째, 세 번째, …, $r$번째에서 계속 $n$개를 선택할 수 있기 때문에 이 순열의 개수는 $n^r$임을 알 수 있다.

* 크기 $n$의 유한 집합 $E$와 자연수 $k$에 대해, $E$의 원소로 이루어진 $k$-중복 순열 전체가 이루는 집합은 유한하며, 그 크기는 $n^k$로 주어진다는 정리가 있다.

* 이 정리는 $k$-튜플과 사상, 두 가지 관점으로 증명할 수 있다.

3.1.1. k-튜플 관점

서로 다른 $n$개의 원소에서 $r$개를 중복을 허락해 뽑아 한 줄로 늘어놓을 때, 첫 번째에서 $n$개를 선택할 수 있고 그 뒤로 두 번째, 세 번째, … , $r$번째에서 계속 $n$개를 선택할 수 있기 때문에 이 순열의 개수는 $n^r$임을 알 수 있다.

* 정리: 크기 $n$의 유한 집합 $E$와 자연수 $k$에 대해, $E$의 원소로 이루어진 $k$-중복 순열 전체가 이루는 집합은 유한하며, 그 크기는 $n^k$로 주어진다.

* 증명
* $k$-튜플로 보면, $E$의 원소로 이루어진 $k$-중복 순열 전체가 이루는 집합은 $E^k\; =\; E\; \times \; E\; \times \; \dots \; \times \; E$와 다름없다. 따라서 그 크기에 관해 $\backslash left|\; E^k\; \backslash right|\; =\; \backslash left|\; E\; \backslash right|^k\; =\; n^k$임은 자명하다.
* $\backslash \{1,\; 2,\; \dots ,\; k\backslash \}$에서 $E$로의 사상으로 보면, $1$의 도착지가 $n$가지, $2$의 도착지가 $n$가지, ……, $k$의 도착지가 $n$가지이므로, 서로 다른 사상은 $n\; \times \; n\; \times \; \dots \; \times \; n\; =\; n^k$가지이다.

3.1.2. 사상 관점

서로 다른 개의 원소에서 개를 중복을 허락해 뽑아 한 줄로 늘어놓을 때, 첫 번째에서 개를 선택할 수 있고 그 뒤로 두 번째, 세 번째, …, 번째에서 계속 개를 선택할 수 있기 때문에 이 순열의 개수는 임을 알 수 있다.

* 에서 로의 사상으로 보면, 의 도착지가 가지, 의 도착지가 가지, ……, 의 도착지가 가지이므로, 서로 다른 사상은 가지이다.

4. 예시

* 여섯 명의 학생이 네 종류의 차(오미자차, 감잎차, 둥굴레차, 국화차)를 주문하는 경우의 수는 4⁶=4096가지다.
* 다섯 개의 숫자 1, 2, 3, 4, 5를 중복해서 사용할 때 만들 수 있는 네 자리 자연수 중 3000 이하인 홀수의 개수는 2×3×5²=150개다.
모스 부호는 두 종류의 기호 "─", "●"를 자모로 하는 단어(문자열)이다. k를 음이 아닌 정수라고 하면, k 문자의 단어는 집합 {─, ●}에 관한 k-중복 순열이며, 길이가 정확히 k인 단어는 2^k 종류이다.