순열 (수학) 편집하기

순열(Permutation)은 주어진 원소들 중 일부 또는 전체를 선택하여 '''순서를 고려하여 배치'''하는 경우의 수를 의미한다. 순열은 조합(Combination)과 달리 선택된 원소들의 '''순서를 중요하게 다룬다'''.
==개요==
순열은 '''순서를 고려하는 경우'''의 수를 구할 때 사용된다.  예를 들어, "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 - 선택되지 않은 원소들을 제거하는 역할.
==순열 예제==
예를 들어, 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과 같이 계산됨.
==순열의 성질==
*P(n, 0) = 1 (n개의 원소 중 아무것도 선택하지 않는 경우는 단 하나뿐: "아무것도 선택하지 않음").
*P(n, 1) = n (n개의 원소 중 하나를 선택하는 경우는 n가지 방법).
*P(n, n) = n! (n개의 원소를 모두 선택하여 나열하는 경우, 모든 원소를 한 번씩 사용하므로 전체 순열이 됨).
==원소의 중복이 있는 순열==
중복된 원소가 포함된 집합에서의 순열을 계산할 때는, 중복된 원소들로 인해 중복 계산되는 경우를 나눠줘야 한다.
*'''중복된 원소가 포함된 순열 공식'''
**동일한 원소가 각각 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
==원순열(Circular Permutation)==
원형으로 배치하는 순열을 '''원순열(Circular Permutation)'''이라 한다.  일반 순열은 선형(직선)으로 배열하지만, 원순열은 원형으로 배치하기 때문에 한 개의 원소를 기준으로 고정할 수 있다.
*'''원순열 공식'''
**(n-1)!
예제: 4명을 원탁에 앉히는 경우:
*(4-1)! = 3! = 6 가지 방법이 존재.
*첫 번째 사람을 고정하고 나머지 3명을 나열하면 같은 배치가 중복되지 않음.
==순열과 조합의 관계==
순열과 조합은 다음과 같은 관계를 가진다.
*P(n, r) = C(n, r) × r!
즉, 먼저 r개를 조합으로 선택한 후, 선택한 r개를 순서대로 배열하는 방법이 r! 가지 존재하므로 조합을 기반으로 순열을 계산할 수 있다.

예제: 5개 중 3개를 선택하는 조합(C(5,3) = 10)에 대해, 각 조합을 3! = 6가지 방법으로 배열하면 총 10 × 6 = 60개의 순열이 나옴.
==순열의 응용==
순열은 다양한 분야에서 활용된다.
*'''확률과 통계''' - 순서를 고려한 경우의 수 계산 (예: 좌석 배치, 경주 결과).
*'''암호학''' - 비밀번호 생성 및 키 배열 (순서가 중요한 경우).
*'''순열 정렬''' - 정렬 알고리즘의 이론적 분석 (숫자 혹은 문자열을 정렬하는 다양한 방식).
*'''그래프 이론''' - 그래프에서 경로 및 순회 문제 (예: 최단 경로, 외판원 문제).
==같이 보기==
*[[조합 (수학)]]
*[[이항 정리]]
*[[파스칼의 삼각형]]
*[[조합론]]