확률과 통계 · 1주차
여러 가지 순열
원순열 · 중복순열
같은 것이 있는 순열
근거: 미래엔 『확률과 통계』 Ⅰ. 경우의 수 – 1. 순열과 조합 (pp.10–16)
오늘의 학습 흐름
1
원순열
원형으로 배열,
회전하여 같은 배열은 1가지
비유: 상석이 없는 아서왕의 원탁
2
중복순열
같은 것을 여러 번
뽑을 수 있는 배열
비유: 숫자를 다시 써도 되는 자물쇠
3
같은 것이 있는 순열
구별되지 않는 것이
섞여 있는 배열
비유: 점과 선만 반복하는 모스 부호
원순열
회전하면 같은 배열비유: 아서왕의 원탁
상석이 없어 어느 자리든 동등한 배치
- 일렬 배열에서는 서로 다른 4가지, 원형 배열에서는 모두 같은 1가지
- 기준이 되는 “첫 자리”가 없는 것이 원형 배열의 특징
예제: 이웃하여 앉는 경우
묶어서 하나로 취급
회장, 부회장 포함 5명의 원탁 회의
- 5명이 앉는 경우 (5−1)! = 24
- 회장·부회장 묶음과 3명의 원순열 (4−1)! = 6
- 묶음 안 자리 바꿈 2! = 2
- 이웃하는 경우 6 × 2 = 12
중복순열
같은 것을 다시 뽑을 수 있는 배열비유: 여행가방 번호 자물쇠
자리마다 0~9 중 아무 숫자나 다시 사용 가능
- 세 자리 비밀번호 10 × 10 × 10 = 10³ = 1000가지
- 8비트 신호 2⁸ = 256가지: 컴퓨터 1바이트가 나타내는 값의 개수
중복순열의 수
서로 다른 n개에서 중복을 허용하여 r개를 택하는 중복순열의 수
ₙΠᵣ = n × n × ⋯ × n = nʳ
ΠProduct(곱)의 P에 해당하는 그리스 문자n각 자리에 올 수 있는 후보의 개수r자리의 개수 (n보다 커도 가능)
첫 번째
↑
n가지두 번째
↑
n가지세 번째
↑
n가지⋯
r 번째
↑
n가지곱의 법칙: n을 r번 곱하기
- ₅Π₂ = 5² = 25, ₃Π₄ = 3⁴ = 81
- 순열 ₙPᵣ과 달리 r > n도 가능한 점
예제: 맨 앞자리 조건이 있는 경우
천의 자리
1, 2, 3
(0 제외)
3가지(0 제외)
백의 자리
0, 1,
2, 3
4가지2, 3
십의 자리
0, 1,
2, 3
4가지2, 3
일의 자리
0, 1,
2, 3
4가지2, 3
₄Π₃ = 4³ = 64
숫자 0, 1, 2, 3으로 만드는 네 자리 자연수
- 천의 자리: 0 제외, 3가지
- 나머지 세 자리: ₄Π₃ = 64
- 전체 3 × 64 = 192개
같은 것이 있는 순열
구별되지 않는 것이 섞인 배열비유: 모스 전신기
점(·)과 선(−) 두 기호만 반복해 문자를 표현
- 모두 다르다고 보고 세면 같은 배열이 여러 번 중복
- 같은 것끼리의 자리 바꿈 수 3! × 2!로 나누어 중복 제거
같은 것이 있는 순열의 수
같은 것이 각각 p개, q개, …, r개 있는 n개를 일렬로 나열하는 순열의 수
n! ÷ (p! × q! × ⋯ × r!)
n!모두 다르다고 볼 때의 배열 수p!, q!같은 것끼리 자리 바꿈으로 생기는 중복조건p + q + ⋯ + r = n
- a 3개, b 2개의 순열
5! ÷ (3! × 2!) = 10
모스 부호: 점 1개, 선 2개를 전부 나열
1번째
2번째
3번째
모스 부호의 수 3! ÷ 2! = 3가지
생각해 보기: 점 2개, 선 2개를 전부 나열하면 몇 가지?
예제: 격자에서의 최단 경로
같은 것이 있는 순열의 활용
비유: 바르셀로나 격자 도시
동쪽·북쪽으로만 가는 최단 이동
회로 배선·로봇 경로와 같은 구조
- 오른쪽 한 칸 a, 위쪽 한 칸 b → 최단 경로 = a 4개, b 2개의 나열
- 경로의 수 6! ÷ (4! × 2!) = 15
요약
일단 모두 다르게 세고, 겹친 만큼 나누기원순열
(n − 1)!
회전하여 같은 n가지를
1가지로 묶는 계산
중복순열
ₙΠᵣ = nʳ
자리마다 n가지,
r번 곱하는 계산
같은 것이 있는 순열
n! ÷ (p! q! ⋯ r!)
같은 것끼리의 자리 바꿈
중복을 나누는 계산
연습문제
더 풀어 보기: 상단 메뉴의 퀴즈1
서버 6대를 원형 링 네트워크로
연결하는 배치의 수
(회전하여 같은 것은 같은 배치)
2
4가지 색을 낼 수 있는 LED 3개로
표시 가능한 신호의 수
(같은 색 중복 가능)
3
101101
1 네 개, 0 두 개로 만드는
6비트 신호의 수
연습문제 정답
- 1번 6개의 원순열 (6 − 1)! = 5! = 120
- 2번 4가지 색에서 3개를 택하는 중복순열 ₄Π₃ = 4³ = 64
- 3번 같은 것이 있는 순열 6! ÷ (4! × 2!) = 15 (격자 최단 경로와 같은 구조)
