godingMath

중복 순열의 계산은 어려운 것이 아니지만,  중복 순열을 사용해 경우의 수를 세다 보면 \(n\)과 \(r\)을 어떻게 정해야 하는지, \(a^b\)과 \(b^a\) 중 어떤 것이 올바른 것인지 종종 헷갈릴 때가 있습니다. 이 글에서는 중복 순열을 사용할 때 헷갈릴 수 있는 부분과 그 이유를 살펴보고 중복 순열을 바르게 사용하는 방법에 대해 이야기해 보겠습니다.

\(a^b\)인가? 아니면 \(b^a\)인가?

교과서에서 설명하고 있는 중복 순열의 정의는 다음과 같습니다.

서로 다른 \(n\)개에서 중복을 허락하여 \(r\)개를 택하는 순열. 기호로는 \(_n\Pi_{r}\) 로 나타내며, $$_n\Pi_{r} = n^r$$

하지만 중복 순열을 이용해 경우의 수를 세다 보면 가끔 \(n\)과 \(r\)을 정하는데 어려움을 겪거나  \(a^b\) 형태로 세어야 할 것을 \(b^a\)으로 세는 경우가 있습니다.  다음 2개의 문제를 통해 이러한 문제의 원인은 무엇인지, 그리고 그 문제를 어떻게 해결할 수 있는지를 살펴보겠습니다.

[문제1]

세 개의 숫자 \(1,2,3\)을 써서 만들수 있는 네 자리의 자연수의 개수는? (단, 같은 숫자를 여러번 사용하거나 사용하지 않은 숫자가 있어도 좋다.)

[풀이]

네 개의 모든 자리 마다 넣을 수 있는 서로 다른 숫자의 개수가 3개이므로 모든 네 자리 자연수의 개수는 $$3\times 3\times 3\times3=3^4=81$$

이 문제는 중복 순열의 기호를 사용하지 않는 것이 오히려 더 쉬운 문제입니다. 문제의 답은 \(3^4\) 이므로, 중복 순열에서 \(n\)과 \(r\)의 값은 \(n=3, r=4\) 이라고 할 수 있습니다. 네 자리 자연수의 개수는 서로 다른 \(3\)개에서 중복을 허용하여 \(4\)개를 택하는 순열의 수라고 할 수 있으므로 모든 경우의 수는 $$ _3\Pi_{4}=3^4=81$$이 됩니다.

여기서 \(3^4\)이라는 답에서 \(n\)과 \(r\)의 값을 추론할 수 있었습니다. 만약 답에 의존하지 않고 먼저 \(n\)과 \(r\)의 값을 정하려고 한다면 서로 다른 \(n\)개에서 \(r\)개를 택하는 것이라는 이라는 정의만으로는 무엇을 \(n\)과 \(r\)로 정해야 할지 쉽게 떠오르지 않을 때가 많습니다. 이러한 어려움 때문에 중복 순열 기호를 사용하는 것이 어렵다면 아예 중복 순열 기호를 사용하지 않고 [문제1]의 풀이처럼 공간에 물건을 집어 넣는 것을 세는 것으로만 문제를 푸는 것은 어떨까요? 불행하게도 어떤 경우에는 이러한 풀이법도 종종 바르지 못할 때가 있습니다.

다음 문제는 편지-우체통 문제로 알려진 문제입니다.  중복 순열 기호를 사용하지 않아도 \(a^b\)와 \(b^a\)의 형태 중 어떤 것이 맞는지 종종 헷갈리는 문제입니다.

[문제2]

서로 다른 3통의 편지를 서로 다른 4개의 우체통에 넣는 방법은 모두 몇가지인가? (단, 한 우체통에 여러 통의 편지를 넣을수 있고, 비어 있는 우체통이 있어도 괜찮다.)

[풀이]

3통의 서로 다른 편지마다 각각 서로 다른 4개의 우체통중 하나를 선택해서 넣을 수 있으므로 모든 경우의 수는 $$4^3=64$$, 또는 \(n=4, r=3\) 이므로 모든 경우의 수는 $$ _4\Pi_{3}=4^3=64$$

하지만 이 문제를 풀다보면 모든 경우의 수를  \(4^3\)이 아니라 \(3^4\)이라고 생각하거나  \(n=4, r=3\)로 두는 것이 직관적으로 받아들이기 쉽지 않을 때가 있습니다.

이렇게 밑과 지수가 헷갈리는 이유는 [문제1]과 [문제2]가 밑과 지수의 역할을 하는 것이 서로 뒤바뀌어져 있기 때문입니다. 왜 [문제1]에서는 숫자의 개수가 밑, 숫자를 넣을 수 있는 자리가 지수가 되었고, [문제2]에서는 편지의 수가 지수, 편지를 넣을 수 있는 우체통의 수가 밑이 되었을까요? 이런 차이는 어디에서 생기는 것일까요? 그리고 더 나아가 \(n\)과 \(r\)의 값을 어떻게 정하는 것이 좋을까요?

중복순열이 헷갈리는 이유

[문제1]과 [문제2]에서 살펴보았듯이, 중복 순열을 사용할 때 발생하는 어려움의 주된 원인은 순열이나 중복 순열을 “서로 다른 공간(또는 자리)에 서로 다른 물건을 집어 넣는 방법”의 수를 세는 것이라고만 생각하기 때문입니다. 예를 들어 [문제1]에서는 자릿수라는 공간에 숫자를 집어넣는 것으로 생각한다면 중복 순열의 수로 모든 경우의 수를 셀 수 있지만, [문제2]에서는 우체통이라는 공간에 편지를 집어넣는 것으로 생각하면 모든 경우의 수를 중복 순열의 수로 셀 수 없게 됩니다.

사실 중복 순열을 공간과 넣을 물건의 관계로 보는 것은 잘못된 것은 아닙니다. 하지만 중복순열에서 말하는 공간이란 반드시 무엇인가를 실제로 넣을 수 있는 ‘주머니’와 같은 것을 뜻하는 것은 아닙니다. 중복 순열에서는 실제 무엇인가를 집어 넣지 못하더라도 공간의 역할을 할 수 있습니다. 즉 중복 순열이 말하는 공간과 물건의 관계란 정말로 비어있는 공간과 그 공간에 집어 넣을 수 있는 어떤 물건을 뜻하는 것이 아니라, (무엇을 공간이라고 정하든지)

“공간”이라고 정한 모든 것에 “물건” 이라고 정한 것이  오직 하나씩 연결된 것,

그리고 이 때, “\(n\)=서로 다른 물건의 수, \(r\)=서로 다른 공간의 개수”

를 뜻합니다. 만약 연결된 물건이 하나도 없는 공간이 적어도 한 개 이상 존재하거나 2개 이상의 물건이 연결되어 있는 공간이 있다면 그것은 순열이 될 수 없습니다. (중복 순열도 마찬가지 입니다.) 예를 들어 다음과 같은 것들은 모두 순열입니다.

그리고 다음과 같은 것들은 순열이 아닙니다.

[문제1]로  돌아가서, 세 자리 자연수 1123 를 가지고 공간과 물건을 정해 둘 사이의 연결 관계를 살펴보겠습니다. 먼저 자리를 공간으로, 숫자를 물건으로 정해 둘 사이의 연결 관계가 순열인지 아닌지 판단해 보겠습니다.

이 연결 관계는 순열이 됩니다. 모든 공간에 물건 하나씩이 잘 연결되어 있기 때문입니다. 하지만 숫자를 공간으로, 자리 수를 물건으로 정하고 둘 사이의 연결 관계를 살펴보면 이것은 순열이 될 수 없습니다. 숫자 1에 천의 자리와 백의 자리, 모두 2개의 자리가 연결되어 있고, 숫자 3에는 일의 자리가 연결되어 있기 때문입니다. 따라서 순열로 만들기 위해서는 자리를 공간\(r\)으로 보고, 숫자를 물건\(n\)으로 정해주어야 합니다. 즉, \(n=3, r=4\)로 정하면 모든 자연수의 수는 $$_n\Pi_{r}=_3\Pi_{4}=3^4=81$$이 됩니다.

이번에는 [문제2]를 생각해보겠습니다.  먼저 서로 다른 네 우체통의 이름을 각각 A,B,C,D 라고 부르고, 서로 다른 편지의 이름을 1,2,3 이라고 정하겠습니다. [문제1]과 마찬가지로 하나의 예를 들어서 공간과 물건의 역할을 어떻게 할지 찾아보겠습니다. 우체통 A에는 편지 1이, 우체통 B에는 편지 2와 편지 3이 들어 있을 때, 공간을 우체통으로, 물건을 편지로 정하고 이 둘 사이의 연결 관계가 순열인지 살펴보겠습니다.

이 연결 관계를 순열이라고 할 수 있습니까? 그렇지 않습니다. 우체통B와 연결된 편지는 2개이고 심지어 우체통 C와 우체통 D와 연결된 편지는 아예 존재하지도 않기 때문입니다. 그렇다면 이번에는 공간과 물건의 역할을 바꾸어 이 둘 사이의 연결관계가 순열이 되는지 확인해 보겠습니다. 공간을 편지,  물건을 우체통으로 정하겠습니다.

이 번에는 이 연결관계가 중복 순열이 됩니다.. 비어 있는 공간도 없고 모든 공간에 1개의 물건이 모두 (B가 중복) 연결되어 있기 때문입니다. 서로 다른 3개의 공간(\(r=3\)에 서로 다른 4개의 물건(\(n=4\)의 연결 관계를 따지는 것이 되므로  중복 순열 기호를 사용하지 않고 \(4^3=64\)라고 곧바로 답을 하거나 중복 순열 기호를 사용하여 $$_n\Pi_{r}=_4\Pi_{3}=4^3=64$$라고 답할 수 있습니다.

순열과 함수

지금까지 순열에서 공간과 물건의 관계를 이야기 했습니다. 혹시 이 관계가 어디서 많이 본 것 같지 않습니까?  맞습니다. 순열에서 공간과 물건의 관계는 함수에서 정의역과 공역의 관계와 정확히 일치 합니다. 함수가 되려면 정의역의 모든 원소가 공역의 원소중 1개와 연결이 되어 있어야 합니다. 순열에서 공간과 물건의 관계는 함수의 정의역과 공역의 관계와 같습니다. 특정한 조건이 없는 이상 공역의 원소는 중복해서 쓰일 수 있기 때문에 중복 순열의 개수를 세는 것은 함수의 개수를 세는 것과 같습니다.

[문제1]과 [문제2]를 함수의 개수를 세는 것으로 본다면, [문제1]은 정의역이 {백의자리, 십의자리, 일의자리} 이고 공역이 {1,2,3}인 함수의 개수를 세는 문제와 같고 [문제2]는 정의역이 {편지1, 편지2, 편지3} 이고 공역이 {우체통A, 우체통B, 우체통C}인 함수의 개수를 세는 문제와 같습니다.

따라서 중복 순열에서,

\(n\)=공역의 원소의 개수, \(r\)=정의역의 원소의 개수

가 됩니다. 따라서 함수의 개수를 세는 것은 결국 중복 순열의 개수를 세는 것과 동일합니다.

지금까지 중복 순열을 사용할 때 발생할 수 있는 문제와 그 원인, 그리고 해결책을 살펴보았습니다. 중복 순열을 이용해서 경우의 수를 세고 싶을 때는 먼저 특정한 예를 만들어보고 이 예를 통해 공간(또는 함수의 정의역)과 물건(또는 함수의 공역)의 역할을 누가 맡을지 생각해 보아야 합니다. 그리고 선택할 수 있는 물건의 수를 \(n\)의 값으로, 공간의 수를 \(r\)이라 두고 중복 순열의 수를 세면 됩니다.