중복순열

3. 중복 순열의 수

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

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

이는 $3^2\; =\; 9$로 계산할 수 있다.

3. 1. 증명

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

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

3. 1. 1. k-튜플 관점

• '''정리:''' 크기 $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개다.