중복순열과 같은 것이 있는 순열

숫자 1, 2, 3만 쓰는 네 자리 비밀번호에서는 같은 숫자를 여러 번 써도 됩니다. 반대로 BANANA의 글자를 늘어놓을 때는 같은 글자끼리 자리를 바꾸어도 새 배열이 생기지 않습니다. 이 절에서는 순열의 두 가지 변형인 중복순열과 같은 것이 있는 순열을 다룹니다. 두 경우의 수가 왜 각각 곱셈과 나눗셈으로 구해지는지 따져 보고, 바둑판 모양 길의 최단 경로를 세는 데 써 봅니다.

먼저 알면 좋은 것 곱의 법칙순열 \({}_{n}\mathrm{P}_{r}\)와 \(n!\)조합 \({}_{n}\mathrm{C}_{r}\)

본문

중복순열과 같은 것이 있는 순열

본문

숫자 0~9로 네 자리 비밀번호를 만들면 같은 숫자를 여러 번 써도 되니 순열 \({}_{10}\mathrm{P}_4\)와는 다르다. 또 BANANA의 여섯 글자를 늘어놓을 때 두 N이나 세 A끼리 자리를 바꾸어도 같은 단어이다. 이런 경우의 수는 어떻게 셀까?

가로 \(m\) = 세로 \(n\) = 길 고르기

그림 1. 가장 짧은 길은 '→' \(m\)개와 '↑' \(n\)개를 늘어놓은 것이므로, 같은 것이 있는 순열의 수 \(\dfrac{(m + n)!}{m!\,n!}\)만큼 있다.

먼저 알아야 할 것곱의 법칙, 순열 \({}_n\mathrm{P}_r\)와 \(n!\), 조합 \({}_n\mathrm{C}_r\)(공통수학1).

1.1.1중복순열

네 자리 비밀번호의 첫째 자리에 올 수 있는 숫자는 10가지이다. 같은 숫자를 다시 써도 되므로 둘째, 셋째, 넷째 자리도 각각 10가지이다. 곱의 법칙에 따라 \(10 \times 10 \times 10 \times 10 = 10^4\)가지이다. 순열에서는 자리마다 고를 것이 하나씩 줄었지만, 여기서는 줄지 않는다.

정의 1.1.1 중복순열

서로 다른 \(n\)개에서 중복을 허락하여 \(r\)개를 택해 일렬로 나열하는 순열을 중복순열이라 하고, 그 수를 \({}_n\Pi_r\)로 나타낸다. \[{}_n\Pi_r = n^r\]

중복을 허락하므로 \(r\)이 \(n\)보다 커도 된다. 가령 0과 1 두 숫자로 8자리를 만드는 방법은 \({}_2\Pi_8 = 2^8 = 256\)가지이고, 이것이 1바이트로 나타낼 수 있는 수의 개수이다.

1.1.2같은 것이 있는 순열

BANANA의 글자를 모두 다른 것으로 보면, 곧 \(\text{A}_1\text{A}_2\text{A}_3\), \(\text{N}_1\text{N}_2\)로 구별하면 배열은 \(6! = 720\)가지이다. 그런데 실제로는 세 A끼리 자리를 바꾼 \(3! = 6\)가지와 두 N끼리 바꾼 \(2! = 2\)가지가 모두 같은 단어이다. 따라서 720을 \(3! \times 2!\)로 나누어 \(\dfrac{720}{12} = 60\)가지이다.

정리 1.1.2 같은 것이 있는 순열

\(n\)개 가운데 같은 것이 각각 \(p\)개, \(q\)개, …, \(r\)개씩 있을 때, 이들을 모두 일렬로 나열하는 방법의 수는 \[\frac{n!}{p!\,q!\,\cdots\,r!}\ (p + q + \cdots + r = n)\]

그림 1의 바둑판 길도 같은 순열이다. 왼쪽 아래에서 오른쪽 위로 가장 짧게 가려면 오른쪽으로 \(m\)칸, 위로 \(n\)칸 가야 하고, 길 하나는 '→'와 '↑'를 늘어놓은 순서 하나와 같다. 슬라이더로 길을 바꾸어 보면 화살표의 순서가 바뀐다.¹

그림 2. 같은 것을 구별해 센 순열을, 같은 것끼리 자리를 바꾸는 경우의 수로 나누면 같은 것이 있는 순열이 된다.

1.1.3예제 풀이

예제 1.1.3

그림 1에서 \(m = 4\), \(n = 3\)인 바둑판 길에서 가장 짧은 길의 수를 구하여라. 또 이 가운데 가운데 점 \((2, 1)\)을 반드시 지나는 길의 수를 구하여라.

길은 → 4개와 ↑ 3개를 늘어놓은 것이므로 \(\dfrac{7!}{4!\,3!} = 35\)가지이다.

점 \((2, 1)\)을 지나는 길은 두 부분으로 나뉜다. 출발점에서 \((2, 1)\)까지는 → 2개, ↑ 1개이므로 \(\dfrac{3!}{2!\,1!} = 3\)가지이다. \((2, 1)\)에서 도착점까지는 → 2개, ↑ 2개이므로 \(\dfrac{4!}{2!\,2!} = 6\)가지이다.

앞부분을 어떻게 가든 뒷부분은 6가지이므로 곱의 법칙에 따라 \(3 \times 6 = 18\)가지이다. 전체 35가지 가운데 18가지가 그 점을 지나는 셈이다. 아래 탐구 카드에서 같은 것이 있는 순열과 바둑판 길을 직접 세어 보자.

→ \(m\)개와 ↑ \(n\)개의 순서는 \(m + n\)개의 자리 가운데 →가 올 \(m\)자리를 고르는 것과 같으므로 \({}_{m+n}\mathrm{C}_m\)으로도 셀 수 있다. 두 식의 값은 같다.

마무리

중복을 허락하면 자리마다 고르는 수가 줄지 않으므로 중복순열의 수는 \(n^r\)이다. 같은 것이 섞여 있으면, 모두 구별한 순열의 수를 같은 것끼리 자리를 바꾸는 경우의 수로 나눈다. 그래서 처음 질문의 비밀번호는 \(10^4\)가지, BANANA의 배열은 \(\tfrac{6!}{3!\,2!} = 60\)가지이다.

탐구 1

같은 것을 여러 번 골라도 되면 경우의 수는 어떻게 될까?

중복순열 · 자리마다 갈래 세기

쓸 수 있는 숫자 \(n\) = 3가지

자리 수 \(r\) = 4

\({}_{n}\Pi_{r}\): —
\({}_{n}\mathrm{P}_{r}\) (중복 없이): —
지금 배열의 순서: —

맨 위 칸을 누르면 그 자리의 숫자가 바뀐다. 왼쪽 수는 그 단계까지 갈라진 길의 수이고, 길이 81개를 넘는 단계는 점을 그리지 않고 개수만 적는다.

질문숫자 1, 2, 3만 써서 네 자리 비밀번호를 만든다. 같은 숫자를 다시 써도 된다면 비밀번호는 몇 가지일까?
복원서로 다른 \(n\)개에서 \(r\)개를 골라 한 줄로 세우는 순열의 수는 \({}_{n}\mathrm{P}_{r} = n(n - 1)(n - 2)\cdots(n - r + 1)\)이다. 한 번 쓴 것은 다시 쓸 수 없어서 자리마다 고를 수 있는 것이 하나씩 줄기 때문이다. 그리고 각 단계의 가짓수를 곱하는 것은 곱의 법칙이다.
설명그런데 같은 것을 다시 써도 되면 자리마다 고를 수 있는 것이 줄지 않는다. 첫째 자리 \(n\)가지, 둘째 자리도 \(n\)가지, …, \(r\)째 자리도 \(n\)가지이므로 곱의 법칙에 따라 \(n \times n \times \cdots \times n = n^r\)가지이다. 이렇게 서로 다른 \(n\)개에서 중복을 허락하여 \(r\)개를 택해 일렬로 나열하는 순열을 중복순열이라 하고, 그 수를 \({}_{n}\Pi_{r}\)로 나타내며 \({}_{n}\Pi_{r} = n^r\)이다. 같은 것을 거듭 쓸 수 있으므로 순열과 달리 \(r\)가 \(n\)보다 커도 된다.
연결'다음 배열'을 누르면 맨 끝 자리부터 바뀌고, \(n\)가지를 다 돌면 앞자리가 하나 올라간다. 자동차 주행 거리계와 같은 방식이어서, 중복순열은 \(n\)진법으로 쓴 \(r\)자리 수와 하나씩 짝지어진다. 그래서 0부터 9까지 쓰는 네 자리 자물쇠는 \(10^4 = 10000\)가지이고, 0과 1만 쓰는 \(r\)비트 신호는 \(2^r\)가지이다. 원소가 \(r\)개인 집합에서 원소가 \(n\)개인 집합으로 가는 함수의 개수도 \(n^r\)인데, 정의역의 원소마다 함숫값을 하나씩 고르기 때문이다.
적용\(n = 3\), \(r = 4\)로 두고 '다음 배열'을 여러 번 눌러 숫자가 바뀌는 순서를 보고, 수형도 맨 아랫줄의 개수와 \({}_{3}\Pi_{4}\)를 비교해 보자. 칸을 눌러 3333을 만들면 몇 번째 배열인지 세어 보고, \(r\)를 \(n\)보다 크게 했을 때 \({}_{n}\mathrm{P}_{r}\)와 \({}_{n}\Pi_{r}\)가 각각 어떻게 되는지도 확인해 보자.
판단"3명이 방 4개 가운데 하나씩 골라 들어가는 방법"에서 \(n\)과 \(r\)를 바꾸어 쓰기 쉽다. 사람마다 방을 하나씩 고르므로 정하는 일이 3번\((r = 3)\), 매번 고를 수 있는 것이 방 4개\((n = 4)\)이고, 답은 \(4^3 = 64\)이다. \(3^4\)으로 쓰면 방이 사람을 하나씩 고르는 셈이 되어, 한 사람이 두 방에 들어가는 경우까지 센다. 그래서 먼저 '한 번씩 정해 주어야 하는 대상'과 '그때마다 고르는 선택지'를 구별해야 한다.

확인조건이 달라지면

학생 5명이 두 동아리 A, B 가운데 한 곳에 각각 가입하는 방법의 수는? (아무도 가입하지 않은 동아리가 있어도 된다.)

탐구 2

같은 글자끼리 자리를 바꾸면 새 배열일까?

같은 것이 있는 순열 · 나누어 세기

직접 입력 (8글자까지)

글자를 모두 다르게 볼 때 \(n!\): —
한 칸에 겹친 배열 수: —
서로 다른 배열 수: —

칸을 누르면 그 칸이 강조된다. 글자가 5개 이상이면 칸이 너무 많아 그림 대신 곱셈 관계만 보여 준다.

질문BANANA의 여섯 글자를 한 줄로 늘어놓는 방법은 \(6! = 720\)가지일까? 두 N의 자리를 바꾼 배열은 눈으로 보면 똑같다.
복원서로 다른 \(n\)개를 모두 한 줄로 세우는 방법은 \(n!\)가지이다. 또 같은 결과를 몇 번씩 겹쳐 세었는지 알면, 전체를 그 수로 나누어 겹침을 없앨 수 있다.
설명같은 글자에 잠시 번호를 붙여 \(A_1, A_2\)처럼 모두 다르게 만들면 배열은 \(n!\)가지이다. 이제 번호를 지우면, 같은 글자끼리 자리만 바꾼 배열들이 하나로 합쳐진다. A가 \(p\)개이면 그 A들의 자리를 바꾸는 방법이 \(p!\)가지이므로, 한 배열에 \(p!\)개씩 겹쳐 있던 것이다. 다른 글자도 같은 글자가 \(q\)개, \(r\)개 있으면 \(q!, r!\)배씩 더 겹친다. 그래서 \(n\)개 가운데 같은 것이 각각 \(p\)개, \(q\)개, …, \(r\)개씩 있을 때\((p + q + \cdots + r = n)\), 이들을 모두 일렬로 나열하는 같은 것이 있는 순열의 수는 \(\frac{n!}{p!q!\cdots r!}\)이다.
연결글자가 두 종류뿐이면 이 수는 조합과 같다. AABB는 \(\frac{4!}{2!2!} = 6\)이고, 네 자리 가운데 A가 들어갈 두 자리를 고르는 \({}_{4}\mathrm{C}_{2} = 6\)과 같다. 바둑판 모양 길에서 최단 경로를 셀 때, 그리고 \((a + b)^n\)을 전개할 때 이 생각이 다시 나온다.
적용AABB를 고르고 '같은 글자에 번호 붙이기'를 눌러 칸이 몇 개이고 한 칸에 번호 붙은 배열이 몇 개씩 들어 있는지 보자. AAAB, AABC로 바꾸어 한 칸의 개수가 어떤 계승의 곱인지 찾고, 마지막으로 BANANA를 직접 입력해 서로 다른 배열 수를 확인해 보자.
판단나누는 수는 같은 글자 묶음마다 따로 구한 계승의 곱이다. BANANA는 A 3개, N 2개이므로 \(3!\cdot2! = 12\)로 나누어 \(\frac{720}{12} = 60\)이고, \((3 + 2)! = 120\)으로 나누면 틀린다. A와 N은 서로 다른 글자라서 A와 N이 자리를 바꾸면 다른 배열이 되기 때문이다. 또 이 공식은 주어진 것을 모두 늘어놓을 때만 쓴다. 일부만 골라 늘어놓을 때는 어떤 글자를 몇 개 골랐는지 경우를 나누어 세어야 한다.

확인조건이 달라지면

숫자 1, 1, 2, 2, 2, 3을 모두 한 번씩 써서 만들 수 있는 여섯 자리 자연수의 개수는?

탐구 3

바둑판 길에서 가장 짧은 길은 몇 가지일까?

같은 것이 있는 순열 · 최단 경로

가로 \(m\) = 4칸

세로 \(n\) = 3칸

전체 최단 경로: —
P를 지나는 경로: —

—

'P를 꼭 지나기'를 켜면 점 P를 끌어서 다른 교차점으로 옮길 수 있다.

질문가로 4칸, 세로 3칸인 바둑판 모양 길에서 A에서 B까지 가장 짧게 가는 방법은 몇 가지일까? 하나하나 그려서 세면 빠뜨리기 쉽다.
복원같은 것이 \(p\)개, \(q\)개 있는 \(n\)개를 모두 늘어놓는 방법은 \(\frac{n!}{p!q!}\)가지이다. 또 동시에 일어나지 않는 경우들은 더하고(합의 법칙), 잇달아 일어나는 단계는 곱한다(곱의 법칙).
설명최단 경로는 왼쪽이나 아래로 돌아가지 않으므로 반드시 오른쪽으로 \(m\)번, 위로 \(n\)번 움직인다. 그래서 경로 하나는 → \(m\)개와 ↑ \(n\)개를 한 줄로 늘어놓은 배열 하나와 짝지어지고, 거꾸로 그런 배열 하나는 경로 하나를 정한다. 따라서 최단 경로의 수는 같은 것이 있는 순열의 수 \(\frac{(m + n)!}{m!n!}\)이고, 가로 4칸, 세로 3칸이면 \(\frac{7!}{4!3!} = 35\)가지이다. 또 P를 꼭 지나야 하면 \(A\to P\)와 \(P\to B\)를 잇달아 가는 것이므로 두 구간의 경로 수를 곱한다.
연결'점마다 경로 수 적기'를 켜면 각 교차점에 그 점까지 가는 최단 경로 수가 적힌다. 어느 점에 들어가는 길은 왼쪽 점에서 오는 길과 아래 점에서 오는 길뿐이므로, 두 수를 더하면 된다. 이 덧셈 규칙은 파스칼의 삼각형을 만드는 규칙과 같아서, 바둑판을 45° 돌려 보면 그 수들이 파스칼의 삼각형으로 늘어서 있다.
적용→와 ↑ 버튼으로 경로 하나를 끝까지 그리고 아래에 적힌 기호 배열을 본 뒤, 다른 경로를 그려 배열의 무엇이 바뀌는지 보자. 'P를 꼭 지나기'를 켜고 P를 옮겨 지나는 경로가 가장 많아지는 위치를 찾고, 점마다 경로 수를 켜서 B에 적힌 수가 위의 '전체' 또는 'P를 지나는' 값과 같은지도 확인해 보자.
판단P를 지나는 경로를 셀 때 \(A\to P\)와 \(P\to B\)의 경로 수를 더하는 실수가 흔하지만, 두 구간은 차례로 이어지는 단계이므로 곱해야 한다. 또 이 공식은 모든 길이 이어져 있는 바둑판에서만 그대로 쓴다. 공사 중인 길이나 대각선 길이 있으면 덧셈 규칙으로 점마다 수를 적어 나가거나 경우를 나누어야 한다.

확인조건이 달라지면

가로 4칸, 세로 3칸인 바둑판 모양 길에서 A(왼쪽 아래)에서 B(오른쪽 위)까지 가는 최단 경로 가운데, A에서 오른쪽으로 2칸, 위로 1칸 간 점 P를 지나지 않는 경로의 수는?

AI 출제 문항연습문제 풀어보기12문항 수능·모의평가·학력평가기출문제 풀어보기136문항