네 자리 비밀번호는 몇 가지일까요? 0~9 열 개를 다시 써도 되니까 $10\times10\times10\times10=10{,}000$. 고1에서 배운 순열 $_{10}P_4=5{,}040$이 아니에요. 그리고 BANANA의 글자를 섞어 만들 수 있는 단어는 $6!=720$이 아니라 60개예요. 같은 A 세 개를 서로 바꿔도 같은 단어니까요. 순열에 "다시 뽑아도 되나"와 "같은 것이 있나" 두 조건이 붙으면 어떻게 달라지는지, 그게 이 단원이에요.
미적분으로 유명한 라이프니츠는 20세에 「조합의 기술(De Arte Combinatoria, 1666)」이라는 책을 썼어요. 글자와 개념을 조합해 모든 생각을 계산할 수 있다는 꿈이었죠. 그 꿈은 300년 뒤 컴퓨터로 실현됐어요. 컴퓨터가 다루는 모든 데이터는 0과 1의 중복순열이에요. $n$비트로 $2^n$가지 상태.
🔁 중복순열 — 자리마다 후보가 그대로
$n$가지 중에서 골라 $r$개의 자리를 채워요. 다시 골라도 되면 자리마다 후보가 $n$가지 그대로예요. 토글을 눌러 "다시 못 고르는" 보통 순열과 비교해 보세요. 자리 아래 숫자가 달라져요.
종류 $n$3
자리 $r$2
✅ 중복순열
서로 다른 $n$개에서 중복을 허락하여 $r$개를 택해 일렬로 나열하는 경우의 수 $_n\Pi_r=n^r$. $r$이 $n$보다 커도 된다(비밀번호 자리 수가 숫자 종류보다 많아도 되듯).
1, 2, 3, 4, 5 의 숫자를 반복해서 써서 만들 수 있는 세 자리 자연수의 개수는? 반복하지 않으면?
1반복 허용: 백·십·일의 자리 각각 5가지 → $_5\Pi_3=5^3$.
2반복 불가: $5\times4\times3={}_5P_3$.
$125$개 · 반복 없으면 $60$개
서로 다른 편지 4통을 우체통 3개에 넣는 방법의 수는? (빈 우체통이 있어도 된다)
1편지 한 통마다 "어느 우체통?" 3가지 선택. 편지가 자리, 우체통이 후보.
→ 헷갈리면 "무엇이 자리인가"를 먼저: 편지 4통이 4자리, 각 자리에 우체통 3가지.
2$3^4$. ($4^3$이 아님에 주의)
$81$가지
⚠️ $n^r$인가 $r^n$인가
"자리"가 되는 것은 하나씩 결정해야 하는 대상(편지·사람·숫자 칸)이고, 그 자리마다 고를 수 있는 후보의 수가 밑이에요. 편지 4통을 우체통 3개에: 편지마다 3가지 → $3^4$. 자리 수가 지수.
🔁 "적어도 하나"는 뒤집어서 센다 — 여사건
"적어도 하나"·"하나 이상"·"이하" 같은 조건은 그대로 세면 경우가 잘게 갈라진다. 반대쪽(하나도 없는 경우)을 세어 전체에서 빼는 것이 거의 언제나 짧다. 예 — 서로 다른 편지 3통을 우체통 4개에 넣을 때, 특정한 우체통 A 가 적어도 하나를 받는 방법은? ① 전체: 편지마다 4가지 → $4^3=64$ ② A 가 하나도 못 받는 경우: 편지마다 A 를 뺀 3가지 → $3^3=27$ ③ $64-27=37$ 확인 — A 가 받는 편지 수로 갈라 세면 $_3C_1\cdot3^2+{}_3C_2\cdot3+{}_3C_3=27+9+1=37$ ✓ 갈라 세기는 항이 셋인데 여사건은 뺄셈 한 번이다. ⚠️ 뒤집을 때 전체가 무엇인지 먼저 못 박는다. 여기서는 조건 없이 넣는 모든 방법 64 가지다.
0️⃣ 0 이 섞이면 맨 앞자리를 따로 센다
숫자로 자연수를 만들 때 맨 앞자리에는 0 이 올 수 없다. 맨 앞만 후보를 하나 줄이고, 뒤 자리는 그대로 둔다 — 뒤에는 0 을 써도 되기 때문이다. 예 — $0,1,2$ 에서 중복을 허락해 만드는 세 자리 자연수는? ① 백의 자리: 0 을 뺀 2가지 ② 십·일의 자리: 각각 3가지 ③ $2 imes3^2=18$ 확인 — 전부 세면 $3^3=27$ 이고 맨 앞이 0 인 것이 $3^2=9$ 라 $27-9=18$ ✓ (여사건으로도 같다) ⚠️ 뒤 자리까지 후보를 줄여 $2^3=8$ 로 세는 것이 흔한 실수다. 조건이 붙은 것은 맨 앞 한 자리뿐이다.
🔤 같은 것이 있는 순열 — 겹치는 만큼 나눈다
글자를 골라 보세요. 전부 다르다고 치면 $n!$가지인데, 같은 글자끼리 자리를 바꿔도 같은 배열이라 겹쳐요. 실제 서로 다른 배열이 몇 개인지, 그리고 왜 나눗셈인지 보세요.
전부 다르다면 $n!$
같은 것끼리 바꾸기
실제 배열 수
✅ 같은 것이 있는 순열
$n$개 중 같은 것이 각각 $p$개, $q$개, …일 때 일렬로 나열하는 경우의 수 $\dfrac{n!}{p!\,q!\cdots}$ ($p+q+\cdots\le n$). 이유: 같은 것을 서로 다르다고 보고 센 $n!$ 안에서, 같은 것들끼리의 자리 바꿈 $p!\,q!\cdots$가지가 한 배열로 겹치기 때문.
1, 1, 2, 2, 3 을 모두 써서 만든 다섯 자리 자연수 중 양 끝이 모두 1인 것의 개수는?
1양 끝을 1로 고정하면 가운데 세 자리에 2, 2, 3을 배열.
2$\dfrac{3!}{2!}=3$.
→ 조건이 있는 자리를 먼저 채우고 남은 것을 "같은 것이 있는 순열"로.
$3$개
⚠️ 옛 자료의 원순열(둥근 탁자에 앉히기, $(n-1)!$)은 2022 개정 교육과정에서 다루지 않아요. 보이면 범위 밖이라고 생각하고 넘겨도 돼요.
🔗 이웃 조건 — 묶거나, 나머지를 먼저 세우고 틈에 끼우거나
이웃해야 한다 → 묶어서 한 글자로 본다. 예 — $A,A,B,B,C$ 에서 두 $B$ 가 이웃하는 배열은? $[BB]$ 를 한 글자로 보면 $[BB],A,A,C$ 네 개를 늘어놓는 $\dfrac{4!}{2!}=12$ 가지. ⚠️ 묶은 것들이 서로 다를 때만 덩어리 안의 배열 $p!$ 를 곱한다. $B$ 둘은 같으므로 곱하지 않는다.
이웃하면 안 된다 → 두 길이 있다. ① 전체 − 이웃하는 것: $\dfrac{5!}{2!2!}-12=30-12=18$ ② 나머지를 먼저 세우고 틈에 끼우기: $B$ 가 아닌 $A,A,C$ 를 늘어놓으면 $\dfrac{3!}{2!}=3$ 가지이고, 그 사이와 양 끝 네 자리 중 두 자리를 골라 $B$ 를 넣으면 $_4C_2=6$ 가지 → $3 imes6=18$ ✓ 🔑 두 길의 답이 같은지 맞춰 보는 것이 가장 좋은 검산이다. $n$ 개를 늘어놓으면 틈은 $n+1$ 개(양 끝 포함)다.
🗺️ 최단 경로 — →와 ↑의 배열
격자 도로에서 왼쪽 아래 A에서 오른쪽 위 B로 가는 최단 경로. 오른쪽으로 $a$번, 위로 $b$번 가야 하고 그 순서만 다르니까, → $a$개와 ↑ $b$개를 나열하는 "같은 것이 있는 순열"이에요. 버튼을 눌러 무작위 경로를 그려 보세요.
가로 $a$4
세로 $b$3
✅ 최단 경로의 수
가로 $a$칸, 세로 $b$칸: $\dfrac{(a+b)!}{a!\,b!}={}_{a+b}C_a$. 특정 점 P를 지나는 경로는 (A→P) × (P→B). 지나지 않는 경로는 전체에서 지나는 경로를 뺀다.
가로 4칸, 세로 3칸 격자에서 A에서 B로 가는 최단 경로 중 점 P(2, 1)을 지나는 경로의 수는?
1A→P: → 2개, ↑ 1개 → $\dfrac{3!}{2!\,1!}=3$.
2P→B: → 2개, ↑ 2개 → $\dfrac{4!}{2!\,2!}=6$.
3연달아 하는 두 단계 → 곱: $3\times6$. (전체는 $\frac{7!}{4!3!}=35$)
$18$가지
⚠️ 길이 끊긴 격자
일부 도로가 막혀 있으면 "막힌 길을 지나는 경로"를 전체에서 빼거나, 갈림점마다 경로 수를 더해 가며 채워요(각 교차점의 경로 수 = 왼쪽 점 + 아래 점). 두 방법이 같은 답을 내는지 확인하는 것도 좋은 연습이에요.
🚧 막힌 '변'을 지나는 경로 — 앞 구간 × 뒤 구간
공사 중이라 지날 수 없는 변이 있으면, 앞 단원의 '점' 문제와 방법이 같다 — 그 변을 지나는 경로를 세어 전체에서 뺀다. 변을 지나려면 그 변의 양 끝점을 반드시 차례로 밟는다. 예 — 가로 3·세로 2 격자에서 $(1,1)$ 과 $(2,1)$ 을 잇는 가로 변이 막혔다면? ① 전체 $=\dfrac{5!}{3!2!}=10$ ② 그 변을 지나는 경로 $=$ (A$ o(1,1)$) $ imes$ ($(2,1) o$B) $=2 imes2=4$ ③ $10-4=6$ ⚠️ 앞뒤 구간은 곱한다. 앞 구간의 경로마다 뒤 구간의 경로가 각각 이어지기 때문이다. 더하면 안 된다. 🔑 다른 검산법 — 교차점마다 (왼쪽 + 아래)를 더해 채워 나가되, 막힌 변으로는 값을 넘기지 않는다. 마지막 점에 적힌 수가 답이다.
🌐 세상 속으로
📌 어른이 되어도 기억할 것
다시 골라도 되면 $n^r$. 자리 수가 지수. 비밀번호를 한 자리 늘리면 경우의 수가 열 배가 되는 이유.
같은 것이 있으면 나눈다. "구별되지 않는 것을 구별해서 센 뒤 겹치는 만큼 나누기"는 세기의 기본 기술이다.
최단 경로는 화살표의 배열. 복잡해 보이는 문제가 글자 나열로 바뀌는 것, 이것이 수학의 "번역".
💡 인사이트 — 정보는 중복순열이다
컴퓨터의 1바이트는 0과 1 여덟 자리, 즉 $_2\Pi_8=2^8=256$가지. 그래서 색상이 256단계, 확장 아스키 문자가 256개예요. DNA는 A·T·G·C 네 글자의 중복순열이고, 세 글자(코돈) 한 묶음이 $4^3=64$가지라서 20종 아미노산을 지정하고도 남아요. 정보를 담는 모든 것은 "몇 가지 기호를 몇 자리에"라는 중복순열이에요.
🏠 순열이 보이는 곳
🔐
비밀번호
4자리 숫자 = 10⁴, 영문 대소문자 8자리는 약 53조
🚗
번호판
숫자·한글 자리의 중복순열
🧬
DNA
A·T·G·C 4글자의 배열
🎨
색상 코드
#RRGGBB = 16⁶ ≈ 1,677만 색
🗺️
격자 도시
교차로에서 갈림 = 최단 경로 세기
🔤
글자 맞추기
같은 글자가 있으면 경우가 줄어든다
🏭 산업과 직업
🛡️
정보 보안 암호 키의 "키 공간"은 중복순열의 크기. 128비트 키 = $2^{128}$가지라 전부 시도하는 데 우주 나이보다 오래 걸린다. 🎓 컴퓨터공학 · 정보보호
🧪
생명공학 염기 서열의 조합 수, 단백질 접힘 경우의 수를 세는 것이 신약·유전자 분석의 첫걸음. 🎓 생명과학 · 생물정보학
🚚
물류·경로 최적화 배달 경로·창고 동선의 경우의 수는 폭발적으로 늘어나므로, 세는 법을 알아야 "다 볼 수 없다"는 것과 근사 알고리즘의 필요를 안다. 🎓 산업공학 · 컴퓨터공학
🔥 여러 가지 순열 퀴즈
문제 1 / 10점수 0 / 10
✅ 정리
항목
내용
중복순열
$_n\Pi_r=n^r$ · 자리(결정할 대상)의 수가 지수, 후보의 수가 밑
같은 것이 있는 순열
$\dfrac{n!}{p!\,q!\cdots}$ · 같은 것끼리의 자리 바꿈만큼 나눈다
최단 경로
$\dfrac{(a+b)!}{a!\,b!}$ · 경유점은 곱, 회피는 전체 − 경유
범위 밖
원순열 $(n-1)!$은 2022 개정에서 제외
🔑 한 줄 요약
다시 골라도 되면 곱하고($n^r$), 같은 것이 있으면 나눈다($\frac{n!}{p!q!}$).