[include(틀:다른 뜻1, other1=후한의 인물 순열, rd1=순열(후한))] [include(틀:이산수학·수리논리학)] [목차] == 개요 == ||서로 다른 [math(n)]개의 원소에서 [math(r)]개를 '''중복없이''' 골라 '''순서에 상관있게''' 나열하는 것을 [math(n)]개에서 [math(r)]개를 택하는 '''순열'''([[順]][[列]])이라고 한다. || 기호로는 [math({}_n{\rm P}_r)], [math({\rm P} (n, \ r ))], [math(n^{\underline{r}})][* 하강 계승(Falling Factorial)이라고도 한다.]등 여러가지가 있지만 한국 교육과정 상에서 자주 쓰이는 것은 [math({}_n{\rm P}_r)]이다. [math(\rm P)]는 영어 명칭 permutation[* 이 단어는 군론에서 [[치환#s-2.2|치환]]을 의미하며, 치환의 개수는 순열로 표현할 수 있다.]의 머리글자에서 유래했다. 뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념 중 하나다[* 초등학교 때 한번쯤은 "[math(\left<0, \ 1, \ 2, \ 3\right>)]중 [math(3)]개를 골라서 만들 수 있는 [math(3)]자리 수의 개수를 구하시오"같은 문제는 풀어봤을 것이다.]. 계산하는 방법도 초등학교에서 해왔던 방법 그대로이며, 단지 미지수가 추가된 것 뿐. 다음 그림과 같이 5장의 카드에서 3장 의 카드를 골라 순서대로 나열해 '세 자리로 된 문자'를 만드는 경우의 수는 몇 가지나 될까를 생각해보면 풀이법을 간단하게 연상할 수 있다. [[파일:4-12-14.png|width=300]] [[https://www.onlybook.co.kr/entry/algorithm-interview|<파이썬 알고리즘 인터뷰>]] p.349, 책만, 2020 수식으로 나타내면 [math({}_n{\rm P}_r = n \times ( n-1 ) \times ( n-2 ) \times \cdots\cdots \times ( n-r+1 ))].[* [math(n)]부터 시작해서 하나씩 작은 수를 [math(r)]개 곱한 것이다.] 이를 [[팩토리얼]]을 사용하여 좀더 간략화 하면 [math({}_n{\rm P}_r = \dfrac{n!}{(n-r)!})]이다.[* 이 식은 [math(r=0)]일 때도 정의가 되기 때문에 부분곱에 의한 정의를 확장하는 효과도 있다.] 자연수 범위에서 팩토리얼이 [[감마 함수]]와 동치[* 즉 감마 함수는 팩토리얼을 복소수 범위로 [[일반화]]시킨 것이다. 그러나 실수부가 [math(0)]보다 작거나 같은 정수를 제외한다는 점은 여전히 동일하다.]라는 것을 이용해서 [math({}_n{\rm P}_r = \dfrac{\Gamma ( n+1 )}{\Gamma ( n-r+1 )})]의 꼴로 바꿀 수 있으며, [[실수(수학)|실수]]/[[복소수]] 순열도 구할 수 있다.[* 가령 인수에 각각 [[원주율]]과 [[허수|허수단위]]를 넣은 [math({}_\pi{\rm P}_i)]의 [[https://www.wolframalpha.com/input/?i=gamma%28pi+%2B+1%29+%2F+gamma%28pi+-+i+%2B+1%29|값을 구해보면]] [math({}_\pi{\rm P}_i = 0.2977\cdots\cdots + i1.1049\cdots\cdots)]이 나온다. 그러나 이걸 직접 풀기는 '''매우 어려운데''' 링크에 나온 항등식 중 하나를 꼽아보면 [math(\displaystyle {}_\pi{\rm P}_i = \exp(\int_{0}^{1} \dfrac{i - ix + x^{1+\pi} - x^{(1-i)+\pi}}{(-1+x) \ln x}\,\mathrm{d}x))](단, [math(\exp(x) = e^x)]) 가 나오는데 이거만 해도 어마무시한 계산 [[노가다(수학)|노가다]]를 수반한다.] === 성질 === 순열은 다음과 같은 성질을 갖는다. [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})][* [math(n)]명 중 특정한 [math(1)]명을 제외하고 뽑아 나열하는 경우의 수[math(+)]특정한 [math(1)]명을 포함하여 뽑아 나열하는 경우의 수] 이 성질은 팩토리얼을 쓰지 않고 순열의 기본 정의([math(n)]개에서 [math(r)]개를 골라 일렬로 나열한 것)만으로 증명할 수 있다. [math(1 < r \leq n)]일 때, [math({}_n{\rm P}_r = (n-r+1) \cdot {}_n{\rm P}_{r-1})] [[감마 함수]]를 이용해서도 증명이 가능하며, 이 경우 정의역이 복소수 범위로 확장[* 물론 변수의 실수부는 [math(0)]보다 작거나 같은 정수를 제외한다.]된다는 데에 의의가 있다. [math({}_n{\rm P}_r = \dfrac{\Gamma \left( n+1 \right)}{\Gamma \left( n-r+1 \right)})]에서 감마 함수의 성질에 의해 [math(\left( n-r+1 \right) \Gamma \left( n-r+1 \right) = \Gamma \left( n-r+2 \right) \Leftrightarrow \dfrac 1{\Gamma \left( n-r+1 \right)} = \dfrac{\left( n-r+1 \right)}{\Gamma \left( n-r+2 \right)})]이므로 ||[math({}_n{\rm P}_r = \dfrac{\Gamma \left( n+1 \right)}{\Gamma \left( n-r+1 \right)} = \left( n-r+1 \right) \dfrac{\Gamma \left( n+1 \right)}{\Gamma \left( n-r+2 \right)} = \left( n-r+1 \right) \cdot {}_n{\rm P}_{r-1})] || == 중복 순열 == 중복 순열은 순열과 마찬가지로 [math(n)]개 중에 [math(r)]개를 순서에 상관있게 뽑는데, '''중복을 허락하여''' 뽑는 것을 말한다. 역시 거창한 설명이지만 초등학교 때부터 써온 수학적 개념. 계산하는 방법 역시 초등학교에서 해왔던 방법과 동일하다. 지수를 사용해 [[경우의 수]]를 나타내면 [math(n^r)]이 된다. 고등학교 확률과 통계 교과서에서는 [math({}_n\Pi_r)]이라는 표현을 쓰는데, 순열과 조합에서 쓰이는 비슷한 기호들과는 달리 출처 불명의 기호로[* 일본에서도 쓰이는 걸 보면 일본에서 유래된 듯하다.], 세계적으로는 그냥 [math(n^r)]라 나타낸다. 2015 개정 교육과정 기준 교과서와 참고서에서는 두 표현이 같다고 병기하여 표시되어있지만 해당 표현은 아직 완전히 사라지지 않았다. [[0의 0제곱]] 문서에서도 다루지만, [math({}_0\Pi_0 = 0^0 = 1)]이다. == 동자 순열 / 부분중복순열 / 같은 것이 있는 순열 == [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 \left( {\rm P}_k ! \right)} = \dfrac{({\rm P}_1 +{\rm P}_2 +\cdots\cdots +{\rm P}_n)!}{{\rm P}_1! \times {\rm P}_2! \times \cdots\cdots \times {\rm P}_n!})] || == 원순열 == [math(n)]개를 나열하는데, 원형으로 나열하는 경우의 수를 말한다. 예를들어 [math(a)], [math(b)], [math(c)], [math(d)]를 원형으로 나열하는 가짓 수를 찾는다 하자. 얼핏 생각하면 [math(4! = 24)]이라 말하기 쉽지만 처음 놓는 문자의 위치는 돌려보면 어디든지 다 '''똑같다'''. 원을 돌려버리면 그만이기 때문. 하지만 두번째 이후로 놓는 문자부터는 위치에 관계 있으며, 결국 구하고자 하는 답은 [math((4-1)! = 6)]이 된다. 이를 일반적으로 나타내면 아래와 같다. ||[math(n)]개의 물체를 원형으로 나열하는 수 [math(= (n-1)! = \Gamma \left( n \right))] || === 같은 것이 있는 원순열 === [[https://m.blog.naver.com/PostView.nhn?blogId=jwonk96&logNo=220440241716&proxyReferer=https:%2F%2Fwww.google.com%2F|링크]]를 참고하자. == 염주 순열 / 목걸이 순열 == [[염주순열]] 참고 == 완전 순열 / 교란 순열 == [[완전순열]] 참고. == 예시 == '''순열''' [math(10)]명중 [math(3)]명을 뽑아 일렬로 세우는 경우의 수는? [math({}_{10}{\rm P}_3 = \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)] '''원순열''' 서로 다른 [math(5)]개의 구슬을 원형으로 나열하는 가짓수는? [math((5-1)! = 4! = 24)] '''염주 순열 / 목걸이 순열''' 서로 다른 [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} \left( -1 \right)^k = {}_5{\rm P}_3 - {}_5{\rm P}_2 + {}_5{\rm P}_1 - {}_5{\rm P}_0 = 44)] == 관련 문서 == * [[경우의 수]] * [[조합]] * [[치환]] [[분류:이산수학]]