중복순열

원문 보기: https://dawoum.duckdns.org/wiki/중복순열

Main article: Permutation § Permutations_with_repetition

순열에서는 서로 다른 \(n\)개를 일부 또는 전부를 일렬로 줄 세우는 경우의 수입니다. 이것은 같은 것을 중복해서 사용하지는 않는 경우입니다. 반면에 같은 것을 여러 번 중복해서 사용해야 되는 경우도 있습니다.

예를 들어, 1부터 9까지의 자연수를 중복을 허락해서 세 자리 자연수를 만들 때, 만들 수 있는 자연수는 몇 개일까요?

세 자리 숫자를 만들 때에는 백 자리, 십 자리, 일 자리로 세 개로 구성됩니다. 또한, 각 자리에는 중복을 허락하므로 이전에 사용했던 숫자도 여전히 사용할 수 있습니다. 따라서 곱의 법칙에 의해 다음과 같은 결과를 얻습니다.

\(\quad\)\( 9 \times 9 \times 9 = 9^3\)

만약 중복을 허용하지 않았다면, 다음과 같이 쓸 수 있습니다.

\(\quad\)\( P(9,3)=9 \times 8 \times 7\)

이와 같이 중복을 허락하여 택할 수 있는 순열을 중복순열이라고 합니다.

서로 다른 \(n\)개에서 중복을 허락하여 \(r\)개를 택하는 중복순열은 \(_n\Pi_r=n^r\)입니다.

여기서 숫자가 2개 나오기 때문에 간혹 혼동이 올 수 있습니다. 중복을 허락하는 것이 ''지수''에 오지만, 실제 계산에서는 곱의 법칙을 이용하는 것이 혼동이 없습니다.

• 빵 1개와 우유 1개를 서로 다른 세 사람에게 나누어 주는 경우: 3×3
• 서로 다른 세 사람에게 서로 다른 네 권의 책을 나누어 주는 경우: 3×3×3×3
• 5명의 전입생을 서로 다른 세 반에 배정하는 방법의 수: 3×3×3×3×3
• 서로 다른 4명의 여행자가 서로 다른 세 곳의 호텔에 투숙하는 방법의 수: 3×3×3×3
• 서로 다른 편지 3통을 서로 다른 네 곳의 우체통에 넣는 방법의 수: 4×4×4

어느 것이 중복해서 선택할 수 있는지 여부를 확인하는 것도 혼동을 줄일 수 있는 방법입니다.

한편, 중복 순열도 약간 다른 경우도 있습니다.

예를 들어, 0, 1, 2, 3, 4를 중복을 허락하여 세 자리 자연수를 만들 때, 세 자리의 자연수의 개수는?

\(\quad\)백자리에는 0이 올 수 없으므로, 4×5×5
200 이상인 자연수의 개수는?
\(\quad\)백자리에는 2이상의 숫자가 와야 하므로, 3×5×5

함수의 개수

함수의 개수를 구할 때, 정의역의 원소가 \(r\)개, 공역의 원소가 \(n\)개 일 때, 함수의 개수는?

\(\quad\)중복순열입니다. \(n^r\)

정의역의 원소가 4개, 공역의 원소가 3개일 때, 치역과 공역이 같아지는 함수의 개수는?
\(\quad\)전체 함수의 개수 – 치역이 2개인 함수 – 치역이 1개인 함수
\(\quad\)3×3×3×3 – 3×(2×2×2×2–2) – 3 = 36
이때 치역이 2개인 함수는

• 먼저 공역 3개 중에 치역 2개를 선택하는 경우의 수: 3
• 치역은 반드시 2개 여야 하기 때문에 공역 2개로 만들 수 있는 함수에서 치역이 1개인 경우를 제외해야 합니다.

응용예제

응용예제1

집합 \(\{1,2,3,4,5,6\}\)의 서로소인 두 부분집합 A, B의 순서쌍 (A, B)의 개수를 구하여라.

응용예제2

전체집합 \(U=\{1,2,3,4,5,6,7,8,9\}\)의 두 부분집합 \(A,B\) 다음 조건을 만족시킬 때, 순서쌍 \((A,B)\)의 개수는?

\(\quad\)(가) \(A-B=\{2,3,6,8\}\)

\(\quad\)(나) \(B\cap \{1,5,7\}=C\)라 할 때, \(n(C)=1\)이다.