최근 수정 시각 : 2022-06-16 10:35:05

순열


파일:나무위키+유도.png  
은(는) 여기로 연결됩니다.
후한의 인물 순열에 대한 내용은 순열(후한) 문서
번 문단을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
참고하십시오.
이산수학
Discrete Mathematics
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
{{{#!wiki style="letter-spacing: -1px"
이론
기본 대상 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프 수형도 · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타
이산수학·수리논리학 둘러보기 · 이론 컴퓨터 과학 둘러보기 · P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 시행착오 ( 예상과 확인)
관련 문서
논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 }}}}}}}}}}}}


1. 개요
1.1. 성질
2. 중복 순열3. 동자 순열 / 부분중복순열 / 같은 것을 포함한 순열4. 원순열
4.1. 같은 것이 있는 원순열
5. 염주 순열 / 목걸이 순열6. 완전 순열 / 교란 순열7. 예시8. 관련 문서

1. 개요

/ falling factorial

서로 다른 [math(n)]개의 원소에서 [math(r)]개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다.

서로 다른 [math(n)]개의 원소에서 [math(r)]개를 선택하는 순열의 가능한 개수를 기호로는 [math({}_n{\rm P}_r)], [math({\rm P} (n,\,r))], [math(n^{\underline{r}})], [math((n)_r)][1]등 여러가지가 있지만 한국 교육과정 상에서 자주 쓰이는 것은 [math({}_n{\rm P}_r)]이다. [math(\rm P)]는 영어 명칭 permutation[2]의 머리글자에서 유래했다.

뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념 중 하나다[3]. 계산하는 방법도 초등학교에서 해왔던 방법 그대로이며, 단지 미지수가 추가된 것 뿐. 다음 그림과 같이 5장의 카드에서 3장 의 카드를 골라 순서대로 나열해 '세 자리로 된 문자'를 만드는 경우의 수는 몇 가지나 될까를 생각해보면 풀이법을 간단하게 연상할 수 있다.

파일:4-12-14.png

수식으로 나타내면 [math({}_n{\rm P}_r = n \times ( n-1 ) \times ( n-2 ) \times \cdots\cdots \times ( n-r+1 ))].[4] 이를 팩토리얼을 사용하여 좀더 간략화 하면 [math({}_n{\rm P}_r = \dfrac{n!}{(n-r)!})]이다.[5] 자연수 범위에서 팩토리얼이 감마 함수와 동치[6]라는 것을 이용해서 [math({}_n{\rm P}_r = \dfrac{\Gamma ( n+1 )}{\Gamma ( n-r+1 )})]의 꼴로 바꿀 수 있으며, 실수/ 복소수 순열도 구할 수 있다.[7]

1.1. 성질

순열은 다음과 같은 성질을 갖는다.
[math({}_n{\rm P}_r = n \cdot {}_{n-1}{\rm P}_{r-1} = {}_{n-1}{\rm P}_r + r \cdot {}_{n-1}{\rm P}_{r-1})][8]

이 성질은 팩토리얼을 쓰지 않고 순열의 기본 정의([math(n)]개에서 [math(r)]개를 골라 일렬로 나열한 것)만으로 증명할 수 있다.
[math(1 < r \le n)]일 때, [math({}_n{\rm P}_r = (n-r+1) \cdot {}_n{\rm P}_{r-1})]

감마 함수를 이용해서도 증명이 가능하며, 이 경우 정의역이 복소수 범위로 확장[9]된다는 데에 의의가 있다. [math({}_n{\rm P}_r = \dfrac{\Gamma \left( n+1 \right)}{\Gamma \left( n-r+1 \right)})]에서 감마 함수의 성질에 의해 [math((n-r+1) \Gamma(n-r+1) = \Gamma(n-r+2) \Leftrightarrow \dfrac 1{\Gamma(n-r+1)} = \dfrac{(n-r+1)}{\Gamma(n-r+2)})]이므로
[math({}_n{\rm P}_r = \dfrac{\Gamma(n+1)}{\Gamma(n-r+1)} = (n-r+1) \dfrac{\Gamma(n+1)}{\Gamma(n-r+2)} = (n-r+1) \cdot {}_n{\rm P}_{r-1})]

중복조합과는 다음과 같은 성질이 성립한다. 이는 상승 계승에서 유도되는 성질이다.
[math({}_n{\rm P}_r = r! (-1)^r {}_{-n}{\rm H}_r)]

2. 중복 순열

product ·

중복 순열은 순열과 마찬가지로 [math(n)]개 중에 [math(r)]개를 순서에 상관 있게 뽑는데, 중복을 허락하여 뽑는 것을 말한다. 역시 거창한 설명이지만 초등학교 때부터 써온 수학적 개념. 계산하는 방법 역시 초등학교에서 해왔던 방법과 동일하다. 지수를 사용해 경우의 수를 나타내면 [math(n^r)]이 된다. 고등학교 확률과 통계 교과서에서는 [math({}_n\Pi_r)]이라는 표현을 쓰는데, 순열과 조합에서 쓰이는 비슷한 기호들과는 달리 출처 불명의 기호로[10], 세계적으로는 그냥 [math(n^r)]으로 나타낸다. 2015 개정 교육 과정 기준 교과서와 참고서에서는 두 표현이 같다고 병기하여 표시되어 있지만 해당 표현은 아직 완전히 사라지지 않았다.

0의 0제곱 문서에서도 다루지만, [math({}_0\Pi_0 = 0^0 = 1)]이다.

3. 동자 순열 / 부분중복순열 / 같은 것을 포함한 순열[11]

[math(n)]개 중에 [math(r)]개를 중복없이 순서에 맞게 뽑는데, [math(n)]개 중에 똑같은 것이 몇개 섞여있을 경우를 말한다. 예를들어 세 개의 문자 [math(a)], [math(a)], [math(b)]를 일렬로 늘어놓는 순열의 수를 찾아보자. 직접 찾아보면 [math(aab)], [math(aba)], [math(baa)]의 [math(3)]가지 경우 밖에 없다. 여기서 좀 더 관찰해 보면 [math(3)]개를 일렬로 늘어놓는 순열의 수는 [math({}_3{\rm P}_3 = 3! = 6)], 중복되는 문자는 [math(2)]개이고, [math(3 = \dfrac 62)]이다. 곧, 같은 것이 있을 때는 전체 순열의 수에서 무언가를 나눠주면 된다는 것을 확인할 수가 있다. 그리고 그 무언가는 중복되는 문자를 나열하는 방법의 수, 즉 이 예시에서는 [math(2!)]이 된다.

중복되는 것이 다른 종류로 여러가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다.
[math(\left( \overbrace{a_1,\,a_1,\, \cdots\cdots,\, a_1}^{\rm P_1},\, \overbrace{a_2,\,a_2,\, \cdots\cdots,\, a_2}^{\rm P_2},\, \cdots\cdots,\, \overbrace{a_n,\, a_n,\, \cdots\cdots,\, a_n}^{{\rm P}_n} \right))]일 때, 즉 [math(a_1)]이 [math(\rm P_1)]개, [math(a_2)]가 [math(\rm P_2)]개, [math(\cdots\cdots)], [math(a_n)]이 [math({\rm P}_n)]개일 때의 순열의 수
[math(~= \frac{\displaystyle \left( \sum_{k=1}^n {\rm P}_k \right)!}{\displaystyle \prod_{k=1}^n ({\rm P}_k!)} = \dfrac{({\rm P}_1 +{\rm P}_2 +\cdots +{\rm P}_n)!}{{\rm P}_1! \times {\rm P}_2! \times \cdots\times {\rm P}_n!})]

4. 원순열

norm of cyclic group ·

[math(n)]개를 나열하는데, 원형으로 나열하는 경우의 수를 말한다. 예를들어 [math(a)], [math(b)], [math(c)], [math(d)]를 원형으로 나열하는 가짓 수를 찾는다 하자. 얼핏 생각하면 [math(4! = 24)]이라 말하기 쉽지만 처음 놓는 문자의 위치는 돌려보면 어디든지 다 똑같다. 원을 돌려버리면 그만이기 때문.[12]하지만 두번째 이후로 놓는 문자부터는 위치에 관계 있으며, 결국 구하고자 하는 답은 [math((4-1)! = 6)]이 된다. 이를 일반적으로 나타내면 아래와 같다.[13]
[math(n)]개의 물체를 원형으로 나열하는 수 [math(~=(n-1)! = \Gamma(n))]

4.1. 같은 것이 있는 원순열

링크를 참고하자.

5. 염주 순열 / 목걸이 순열

염주순열 참고

6. 완전 순열 / 교란 순열

완전순열 참고.

7. 예시

순열
[math(10)]명중 [math(3)]명을 뽑아 일렬로 세우는 경우의 수는?
[math(\rm{}_{10}P_3 = 10 \times 9 \times 8 = \dfrac{10!}{(10-3)!} = \dfrac{10!}{7!} = 720)]

중복 순열
중복을 허락하여 네 개의 숫자 [math(1, \ 2, \ 3, \ 4)]를 써서 세 자리 자연수를 만드는 가짓수는?
[math(4^3=64)]

동자 순열(1)
wiki라는 네 글자를 일렬로 나열할 때의 가짓수는?
[math(\dfrac{4!}{2!} = 12)]

동자 순열(2)
namuwiki라는 여덟 글자를 일렬로 나열할 때의 가짓수는?
[math(\dfrac{8!}{2!} = 20160)]

원순열(1)
서로 다른 [math(5)]개의 구슬을 원형으로 나열하는 가짓수는?
[math((5-1)! = 4! = 24)]

원순열(2)
남학생 3명과 여학생 2명을 원탁에 앉힐 때, 여학생끼리 이웃하지 않게 앉히는 가짓수는?
우선 남학생 1명을 아무 자리에나 앉힌다. (1)
그러면 4자리가 남고, 경우의 수는 24가지가 되는데, 여학생끼리 이웃하는 경우의 수는 12가지이므로 정답은 12가지이다. 여학생 1명을 아무 자리에나 앉히고 시작하더라도 결과는 똑같다.[14]

염주 순열 / 목걸이 순열
서로 다른 [math(5)]개의 구슬로 목걸이를 만드는 방법의 가짓수는?
[math(\left\lceil \dfrac{(5-1)!}2 \right\rceil =12)]

완전 순열 / 교란 순열
[math(5)]명의 사람이 시험을 보고 시험지를 채점하는데 자신의 시험지는 자신이 채점할 수 없다. 채점하게 하는 방법의 가짓수는?
[math(\displaystyle D_5 = \sum_{k=2}^5 {}_5{\rm P}_{5-k} (-1)^k = \rm{}_5P_3 - {}_5P_2 + {}_5P_1 - {}_5P_0 = 44)]

8. 관련 문서


[1] [math(n^{\underline{r}})], [math((n)_r)]은 하강 계승()이라는 이름으로 주로 불린다. [2] 이 단어는 군론에서 치환을 의미하며, 치환의 개수는 순열로 표현할 수 있다. [3] 초등학교 때 한번쯤은 "[math(\left<0,\,1,\,2,\,3\right>)]중 [math(3)]개를 골라서 만들 수 있는 [math(3)]자리 수의 개수를 구하시오"같은 문제는 풀어봤을 것이다. [4] [math(n)]부터 시작해서 하나씩 작은 수를 [math(r)]개 곱한 것이다. [5] 이 식은 [math(r=0)]일 때도 정의가 되기 때문에 부분곱에 의한 정의를 확장하는 효과도 있다. [6] 즉 감마 함수는 팩토리얼을 복소수 범위로 일반화시킨 것이다. 그러나 실수부가 [math(0)]보다 작거나 같은 정수를 제외한다는 점은 여전히 동일하다. [7] 가령 인수에 각각 원주율 허수단위를 넣은 [math({}_\pi{\rm P}_i)]의 값을 구해보면 [math({}_\pi{\rm P}_i = 0.2977\cdots\cdots + i1.1049\cdots\cdots)]이 나온다. 그러나 이걸 직접 풀기는 매우 어려운데 링크에 나온 항등식 중 하나를 꼽아보면 [math(\displaystyle {}_\pi{\rm P}_i = \exp\left(\int_0^1 \dfrac{i - ix + x^{1+\pi} - x^{(1-i)+\pi}}{(-1+x) \ln x}\,{\rm d}x\right))](단, [math(\exp(x) = e^x)]) 가 나오는데 이거만 해도 어마무시한 계산 노가다를 수반한다. [8] [math(n)]명 중 특정한 [math(1)]명을 제외하고 뽑아 나열하는 경우의 수[math(+)]특정한 [math(1)]명을 포함하여 뽑아 나열하는 경우의 수 [9] 물론 변수의 실수부는 [math(0)]보다 작거나 같은 정수를 제외한다. [10] 일본에서도 쓰이는 걸 보면 일본에서 유래된 듯하다. 지수 꼴로 간략하게 표현할 수 있으니 세계적으로는 굳이 기호를 만들 필요성을 못 느낀 것. [11] 고등학교 확률과 통계(확통)에서는 이 용어로 학습한다. [12] 이 때문에 원형 하노이 탑은 순서를 생각하지 않아도 된다. 일직선 하노이 탑은 순서를 생각할 수 있어서 경우의 수가 더 많다. [13] 직관적으로 설명하자면 일단 아무 자리에나 한 명을 앉히고 시작하면 된다. [14] 고등학교 확률과 통계에서 자주 나오는 유형이다.