직관 — 이름표를 떼면 같은 줄이 된다
같은 모양의 두 카드에 잠시 서로 다른 이름표를 붙인다. 이름표를 보고 줄을 세우면 두 카드의 자리를 바꾼 줄도 따로 센다. 이름표를 떼었을 때 같아지는 줄들을 한 묶음으로 모으면 원래 세려던 배열만 남는다.
이름표를 붙이는 것은 대상을 임시로 구별하는 일이다. 이름표를 지운 뒤 같은 결과가 되는 횟수를 정확히 세면 순열의 수에서 중복을 제거할 수 있다. 이 글의 문자 카드와 격자 길은 설명을 위해 만든 가상 예다. 문자 배열, 최단 경로, 순서가 정해진 줄 세우기를 셀 때 이 방법을 쓴다.
같은 것이 있는 순열은 정해진 개수를 모두 배열한다
같은 것이 있는 순열은 주어진 대상들을 모두 일렬로 놓되, 같은 종류끼리 바꾼 배열은 같은 것으로 보는 순열이다. '같은 것을 포함한 순열'이라고도 부른다. 종류별 개수는 이미 정해져 있다. A 두 개와 B 한 개가 주어졌다면 AAB, ABA, BAA는 가능하지만 AAA는 불가능하다.
총 개 중 같은 종류가 각각 개이고 일 때, 서로 다른 배열의 수 은 다음과 같다. 여기서 각 종류의 개수는 양의 정수다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 전체 개수 | total number | 빠짐없이 일렬로 놓을 대상의 수 | |
| 종류별 개수 | multiplicities | 같은 것으로 취급하는 각 종류의 개수 | |
| 계승 | factorial | 서로 다른 개를 전부 배열하는 수 | |
| 배열의 수 | number of arrangements | 같은 종류의 자리 바꿈을 구별하지 않은 결과 수 |
같은 것이 있는 순열에서 모두 같거나 모두 다르면 어떻게 되나요?
같은 것이 있는 순열에서 주어진 개가 모두 같으면 한 종류이므로 가지이고, 모두 다르면 각 종류의 개수가 1이므로 가지다. 예를 들어 AAA는 배열 하나지만 A, B, C를 모두 배열하면 가지다.
같은 것이 있는 순열은 왜 계승으로 나눌까?
최종 배열 하나마다 지워 버릴 이름표의 배치 수가 똑같기 때문이다. A 두 개를 로 구별하면 세 카드의 배열은 가지다. 이름표를 지우면 AAB 하나를 만드는 배열은 , 의 가지이고, ABA와 BAA도 각각 두 번씩 나타난다.
figures/erase_labels.py그림 1의 핵심은 단지 '중복이 있다'가 아니라 각 결과가 같은 횟수로 중복된다는 점이다. 일반적으로 이름표가 없는 배열 하나를 고정하자. 그 배열에서 첫 종류가 차지한 자리에 서로 다른 이름표를 붙이는 방법은 가지다. 다음 종류는 가지이며 다른 종류의 이름표 배치와 독립적으로 선택할 수 있다.
따라서 고정한 배열 하나에서 개의 구별된 배열이 나온다. 반대로 이름표가 붙은 어떤 배열도 이름표를 지우면 원래 배열 하나로 돌아간다. 전체 개가 이 크기의 묶음들로 빠짐없이 나뉘므로 식 (1)이 성립한다. 이 설명은 AAB의 수치만 확인한 것이 아니라 임의의 종류별 개수에 적용되는 이유다.
같은 것이 있는 순열은 정해진 개를 모두 일렬로 배열하고, 같은 종류의 자리 바꿈을 구별하지 않는다. 종류별 개수가 로 합이 이면, 각 최종 배열이 정확히 번씩 중복되어 배열 수는 이다.
같은 것이 있는 순열에서 같은 색 공도 번호가 있으면 같은 것인가요?
배열 결과를 구별하는 기준에 번호가 포함되면 같은 색 공이라도 서로 다른 대상이다. A 카드 두 장에 붙인 번호를 결과에서도 유지한다면 그림 1의 여섯 배열을 그대로 세고, 번호를 무시할 때만 세 배열로 묶는다.
같은 것이 있는 순열과 중복순열은 개수가 정해졌는지로 갈린다
중복순열은 자리마다 같은 종류를 다시 골라, 종류별 개수가 기록마다 달라질 수 있다. 같은 것이 있는 순열은 종류별 개수가 처음부터 정해져 있어 그 재고를 모두 쓴다. A, B로 세 자리를 채우는 중복순열 가지 가운데 A 두 개와 B 한 개를 모두 쓴 기록은 3가지뿐이다.
figures/repeat_vs_multiset.py그림 2의 네 묶음 크기 1, 3, 3, 1은 각각 같은 것이 있는 순열의 수다. 예를 들어 A 한 개와 B 두 개는 가지다. 네 묶음을 더하면 중복순열의 수 8이 된다. 이 1, 3, 3, 1은 이항정리에서 을 전개한 계수로 다시 나온다.
'같은 것이 나온다'는 말보다 개수가 정해져 있는지가 두 문제를 가르는 기준이다. AAB에 대해 을 쓰면 AAA나 ABB처럼 재고와 개수가 다른 기록까지 센다.
같은 것이 있는 순열에서 주어진 것 중 일부만 쓰면 되나요?
같은 것이 있는 순열의 전체 배열 공식은 주어진 대상을 모두 쓰는 조건에서 적용한다. A, A, B 중 두 개를 써서 만들 수 있는 기록은 AA, AB, BA의 3가지다. 먼저 각 종류를 몇 개씩 쓰는지 나눈 뒤, 겹치지 않는 경우의 수를 합의 법칙으로 더할 수 있다.
같은 것이 있는 순열은 조합으로 자리를 골라도 같은 답이다
LEVEL의 다섯 글자를 모두 배열하자. L 두 개, E 두 개, V 한 개이므로 식 (1)에 넣으면 다음과 같다.
뜻이 있는 영단어인지 여부는 세지 않고, 문자 순서만 구별한다. 같은 답을 조합으로도 얻는다. 다섯 자리 중 L이 들어갈 두 자리를 고르고, 남은 세 자리 중 E가 들어갈 두 자리를 고른다. 마지막 한 자리는 자동으로 V다.
figures/slot_choice.py그림 3에서 같은 문자끼리는 자리만 고르고 순서는 고르지 않는다. 그래서 순열 대신 조합을 쓴다. 식 (3)과 식 (4)는 같은 배열을 '나누어 지우기'와 '자리 고르기'의 두 방법으로 센 것이다.
같은 것이 있는 순열은 조합과 같은 건가요?
같은 것이 있는 순열은 종류가 두 가지일 때 조합의 수와 같다. R 네 개와 U 두 개의 배열은 여섯 자리 중 U의 두 자리를 고르는 것과 같아 가지다. 종류가 셋 이상이면 식 (4)처럼 조합을 여러 번 곱한다.
격자의 최단 경로는 같은 것이 있는 순열로 센다
격자에서 오른쪽으로 네 번, 위로 두 번 움직여 도착점에 가는 경로를 생각해 보자. 매번 한 칸만 움직이며, 왼쪽이나 아래쪽으로는 가지 않는다. 오른쪽 이동을 R, 위 이동을 U로 쓰면 경로 하나는 R 네 개와 U 두 개의 배열 하나다.
figures/lattice_routes.py그림 4의 경로를 문자로 읽을 수 있고, 문자 배열을 따라가면 경로가 하나로 정해진다. 그러므로 식 (5)는 배열뿐 아니라 경로도 중복 없이 센다. A에서 B로 가는 최단 경로는 오른쪽 네 번과 위 두 번만 쓰는 길이 6의 경로이므로, 이 15개가 최단 경로 전체다.
반드시 지나야 할 점이 있으면 최단 경로를 두 구간으로 나눈다
점 P를 반드시 지나는 최단 경로는 A에서 P까지의 경로와 P에서 B까지의 경로를 이어 붙인 것이다. 앞 구간을 어떻게 골랐든 뒤 구간의 선택 수는 같으므로 두 수를 곱한다. A에서 오른쪽 두 칸, 위로 한 칸 떨어진 P를 지나게 하자.
figures/lattice_through_point.py그림 5에서 P에서 B까지도 오른쪽 두 칸, 위로 한 칸이라 3가지이므로 식 (6)의 9가지가 된다. P를 지나지 않는 최단 경로는 전체에서 빼서 가지다. 점선 RRRRUU처럼 처음 세 칸을 모두 오른쪽으로 가서 P의 아래를 지나는 경로가 3가지, UURRRR처럼 오른쪽으로 두 칸을 가기 전에 맨 윗줄까지 올라 P의 왼쪽 위를 지나는 경로가 3가지다.
같은 것이 있는 순열에 위치 조건이 붙으면 무엇을 고정할까?
LEVEL의 두 끝이 모두 L이어야 한다면 L 두 개는 이미 자리를 차지했다. 가운데 세 자리에 E, E, V를 놓는 방법만 세므로 가지다. 전체 배열의 수 30에 추가로 를 나누는 문제가 아니다.
두 L이 반드시 이웃해야 한다면 LL을 한 덩어리로 묶는다. LL, E, E, V의 네 대상을 배열하므로 가지다. 덩어리 안의 두 L은 같은 문자라 안쪽 순서는 한 가지뿐이다.
숫자 카드 0, 1, 1, 2를 모두 써서 네 자리 자연수를 만들 때는 첫 자리의 0을 뺀다. 0으로 시작하는 배열은 나머지 1, 1, 2를 배열한 것과 같다.
1012, 1021, 1102, 1120, 1201, 1210, 2011, 2101, 2110을 나열하면 식 (7)의 9개와 맞는다.
순서가 정해진 대상은 같은 것으로 보고 센다
A, B, C, D, E를 한 줄로 세우되 A, B, C가 왼쪽부터 이 순서로 놓여야 한다고 하자. A, B, C를 모두 같은 문자 X로 바꾸어 X, X, X, D, E를 배열한 뒤, X 자리에 왼쪽부터 A, B, C를 적으면 된다.
X의 배열 하나는 조건을 지키는 줄 하나로만 바뀌고, 조건을 지키는 줄도 X로 바꾸면 배열 하나로 돌아간다. 다른 눈으로 보면, A, B, C가 차지한 세 자리에 세 문자를 놓는 가지 순서 중 조건을 지키는 순서는 하나다. 그래서 전체 120을 6으로 나눈다. 이름표 A, B, C를 지웠다가 정해진 순서대로 다시 붙이는 셈이다.
같은 것이 있는 순열의 흔한 오해
- 같은 것이 둘씩 있으면 전체 계승을 종류마다 2를 더한 수로 나눈다 — LEVEL처럼 두 종류가 둘씩이면 우연히 지만, AABBCC처럼 세 종류가 둘씩이면 분모는 이고 이 아니다. 각 종류의 이름표 배치를 함께 고르므로 더하지 않고 곱한다.
- 같은 문자를 묶을 때도 묶음 안의 순서를 곱한다 — LEVEL에서 LL 덩어리의 12가지에 를 곱한 24는 같은 줄을 두 번씩 센 값이다. 두 L을 맞바꾸어도 줄이 달라지지 않으므로 묶음 안 순서는 서로 다른 대상을 묶을 때만 곱한다.
직접 해보기
- BANANA의 여섯 문자를 모두 배열하는 방법은 몇 가지인가? 실제 단어인지 여부는 구별하지 않는다.
- A, A, B, B를 모두 배열하되 양 끝의 문자가 달라야 한다. 몇 가지인가?
- 숫자 카드 0, 0, 1, 2, 2를 모두 써서 만드는 다섯 자리 자연수는 몇 개인가?
- A, B, C, D, E, F를 한 줄로 세우되 A는 B보다 왼쪽, C는 D보다 왼쪽에 있어야 한다. 몇 가지인가?
- 오른쪽으로 세 칸, 위로 세 칸 떨어진 점까지 R, U 이동만으로 가는 최단 경로 중, 출발점에서 오른쪽 한 칸·위로 한 칸 떨어진 점을 지나지 않는 경로는 몇 가지인가?
답과 풀이
- A 세 개, N 두 개, B 한 개다. 가지다.
- 끝이 A, B인 경우와 B, A인 경우를 나눈다. 각 경우 가운데 남은 A, B의 순서가 2가지이므로 가지다. 전체 가지에서 양 끝이 같은 ABBA, BAAB를 빼도 4가지다.
- 전체 배열은 가지다. 0으로 시작하는 배열은 나머지 0, 1, 2, 2를 배열한 가지다. 따라서 개다.
- A와 B를 같은 문자 X로, C와 D를 같은 문자 Y로 바꾸어 X, X, Y, Y, E, F를 배열한다. 가지다.
- 전체는 가지다. 그 점까지는 가지, 그 점에서 도착점까지는 오른쪽 두 칸·위로 두 칸이라 가지다. 지나는 경로는 가지이므로 지나지 않는 경로는 가지다.
더 읽기
- 지학사 2022 개정 고등 확률과 통계 교과서 — 「중복순열과 같은 것이 있는 순열」 14–15쪽. 구별 표지를 붙였다 지우는 이유와 격자 경로의 대응을 확인했다.
- College Algebra 2e — Counting Principles — OpenStax. 「Finding the Number of Permutations of n Non-Distinct Objects」에서 종류별 계승으로 나누는 조건을 확인했다.
영상 노트
- 00:00 A 두 장의 이름표를 붙였다 떼며 배열의 구별 기준을 정한다.
- 00:30 그림 1의 여섯 배열을 세 묶음으로 모아 식 (2)를 계산한다.
- 01:05 각 최종 배열의 이름표 수가 일정함을 설명하고 식 (1)로 일반화한다.
- 01:40 그림 2로 중복순열 8개를 A의 개수별로 나누어 재고가 정해진 묶음을 고른다.
- 02:15 식 (3)의 LEVEL을 그림 3처럼 자리 고르기로 다시 세어 식 (4)와 맞춘다.
- 02:50 그림 4의 경로를 문자로 읽어 식 (5)를 얻고, 그림 5에서 P를 지나는 9와 피하는 6을 센다.
- 03:35 끝자리 고정, LL 묶음, 0이 있는 숫자 카드의 식 (7)을 차례로 센다.
- 04:10 A, B, C를 X로 바꾸는 식 (8)을 보이고 새 연습을 푼다.
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 중복순열과의 비교 절, 조합으로 자리 고르기와 두 종류일 때의 조합 질문, 반드시 지나는 점이 있는 최단 경로, 0이 있는 숫자 카드, 순서가 정해진 배열 절 추가, 중복되던 오해를 같은 문자 묶음의 순서 곱하기로 교체하고 계승 덧셈 오해의 반례를 둘씩인 세 종류로 바꿈, P를 피하는 경로의 두 갈래를 바로잡음, 연습을 숫자 카드·순서 조건·지나지 않는 경로 유형으로 바꿈, 별칭 추가 (에이전트 수정, 그림 2→5)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림