순열 (수학)
순열(Permutation)은 주어진 원소들 중 일부 또는 전체를 선택하여 순서를 고려하여 배치하는 경우의 수를 의미한다. 순열은 조합(Combination)과 달리 선택된 원소들의 순서를 중요하게 다룬다.
1 개요[편집 | 원본 편집]
순열은 순서를 고려하는 경우의 수를 구할 때 사용된다. 예를 들어, "ABC"와 "BAC"는 같은 원소로 구성되었지만 순서가 다르므로 서로 다른 순열로 취급된다.
순열의 개수는 다음과 같은 공식으로 계산된다.
- 순열 공식
- n개의 원소 중 r개를 선택하여 나열하는 경우의 수:
- P(n, r) = nPr = n! / (n - r)!
여기서,
- n! = n × (n-1) × ... × 1 (계승, Factorial) - 전체 원소를 순서대로 나열하는 경우의 수.
- (n - r)! = (n - r) × (n - r - 1) × ... × 1 - 선택되지 않은 원소들을 제거하는 역할.
2 순열 예제[편집 | 원본 편집]
예를 들어, 5개의 원소 {A, B, C, D, E} 중 3개를 선택하여 순서를 고려하여 나열하는 경우:
P(5, 3) = 5! / (5-3)! = (5 × 4 × 3 × 2! ) / (2!) = 5 × 4 × 3 = 60
가능한 순열의 일부 예시:
- ABC, ACB, BAC, BCA, CAB, CBA
- ABD, ADB, BAD, BDA, DAB, DBA
- ...
즉, 처음에 5개의 선택지가 있으며, 첫 번째 원소를 선택한 후에는 4개가 남고, 그다음에는 3개가 남기 때문에 5 × 4 × 3과 같이 계산됨.
3 순열의 성질[편집 | 원본 편집]
- P(n, 0) = 1 (n개의 원소 중 아무것도 선택하지 않는 경우는 단 하나뿐: "아무것도 선택하지 않음").
- P(n, 1) = n (n개의 원소 중 하나를 선택하는 경우는 n가지 방법).
- P(n, n) = n! (n개의 원소를 모두 선택하여 나열하는 경우, 모든 원소를 한 번씩 사용하므로 전체 순열이 됨).
4 원소의 중복이 있는 순열[편집 | 원본 편집]
중복된 원소가 포함된 집합에서의 순열을 계산할 때는, 중복된 원소들로 인해 중복 계산되는 경우를 나눠줘야 한다.
- 중복된 원소가 포함된 순열 공식
- 동일한 원소가 각각 k₁, k₂, ..., kₘ개 존재하는 경우:
- P(n; k₁, k₂, ..., kₘ) = n! / (k₁! × k₂! × ... × kₘ!)
예제: "AAB"의 모든 순열을 구하는 경우,
- 총 3개의 문자가 있으며, A가 2개, B가 1개이므로:
- P(3; 2,1) = 3! / (2! × 1!) = 6 / 2 = 3
- 가능한 순열: AAB, ABA, BAA
5 원순열(Circular Permutation)[편집 | 원본 편집]
원형으로 배치하는 순열을 원순열(Circular Permutation)이라 한다. 일반 순열은 선형(직선)으로 배열하지만, 원순열은 원형으로 배치하기 때문에 한 개의 원소를 기준으로 고정할 수 있다.
- 원순열 공식
- (n-1)!
예제: 4명을 원탁에 앉히는 경우:
- (4-1)! = 3! = 6 가지 방법이 존재.
- 첫 번째 사람을 고정하고 나머지 3명을 나열하면 같은 배치가 중복되지 않음.
6 순열과 조합의 관계[편집 | 원본 편집]
순열과 조합은 다음과 같은 관계를 가진다.
- P(n, r) = C(n, r) × r!
즉, 먼저 r개를 조합으로 선택한 후, 선택한 r개를 순서대로 배열하는 방법이 r! 가지 존재하므로 조합을 기반으로 순열을 계산할 수 있다.
예제: 5개 중 3개를 선택하는 조합(C(5,3) = 10)에 대해, 각 조합을 3! = 6가지 방법으로 배열하면 총 10 × 6 = 60개의 순열이 나옴.
7 순열의 응용[편집 | 원본 편집]
순열은 다양한 분야에서 활용된다.
- 확률과 통계 - 순서를 고려한 경우의 수 계산 (예: 좌석 배치, 경주 결과).
- 암호학 - 비밀번호 생성 및 키 배열 (순서가 중요한 경우).
- 순열 정렬 - 정렬 알고리즘의 이론적 분석 (숫자 혹은 문자열을 정렬하는 다양한 방식).
- 그래프 이론 - 그래프에서 경로 및 순회 문제 (예: 최단 경로, 외판원 문제).
