순열
1. 개요
기호로는 $${}_n{\rm P}_r$$, $${\rm P} (n, \ r )$$, $$n^{\underline{r}}$$[1]등 여러가지가 있지만 한국 교육과정 상에서 자주 쓰이는 것은 $${}_n{\rm P}_r$$이다. $$\rm P$$는 영어 명칭 permutation[2]의 머리글자에서 유래했다.
뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념 중 하나다[3]. 계산하는 방법도 초등학교에서 해왔던 방법 그대로이며, 단지 미지수가 추가된 것 뿐. 다음 그림과 같이 5장의 카드에서 3장 의 카드를 골라 순서대로 나열해 '세 자리로 된 문자'를 만드는 경우의 수는 몇 가지나 될까를 생각해보면 풀이법을 간단하게 연상할 수 있다.
[image]
<파이썬 알고리즘 인터뷰> p.349, 책만, 2020
수식으로 나타내면 $${}_n{\rm P}_r = n \times ( n-1 ) \times ( n-2 ) \times \cdots\cdots \times ( n-r+1 )$$.[4] 이를 팩토리얼을 사용하여 좀더 간략화 하면 $${}_n{\rm P}_r = \dfrac{n!}{(n-r)!}$$이다.[5] 자연수 범위에서 팩토리얼이 감마 함수와 동치[6]라는 것을 이용해서 $${}_n{\rm P}_r = \dfrac{\Gamma ( n+1 )}{\Gamma ( n-r+1 )}$$의 꼴로 바꿀 수 있으며, 실수/복소수 순열도 구할 수 있다.[7]
1.1. 성질
순열은 다음과 같은 성질을 갖는다.
$${}_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]
이 성질은 팩토리얼을 쓰지 않고 순열의 기본 정의($$n$$개에서 $$r$$개를 골라 일렬로 나열한 것)만으로 증명할 수 있다.
$$1 < r \leq n$$일 때, $${}_n{\rm P}_r = (n-r+1) \cdot {}_n{\rm P}_{r-1}$$
감마 함수를 이용해서도 증명이 가능하며, 이 경우 정의역이 복소수 범위로 확장[9]된다는 데에 의의가 있다. $${}_n{\rm P}_r = \dfrac{\Gamma \left( n+1 \right)}{\Gamma \left( n-r+1 \right)}$$에서 감마 함수의 성질에 의해 $$\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)}$$이므로
2. 중복 순열
중복 순열은 순열과 마찬가지로 $$n$$개 중에 $$r$$개를 순서에 상관있게 뽑는데, '''중복을 허락하여''' 뽑는 것을 말한다. 역시 거창한 설명이지만 초등학교 때부터 써온 수학적 개념. 계산하는 방법 역시 초등학교에서 해왔던 방법과 동일하다. 지수를 사용해 경우의 수를 나타내면 $$n^r$$이 된다. 고등학교 확률과 통계 교과서에서는 $${}_n\Pi_r$$이라는 표현을 쓰는데, 순열과 조합에서 쓰이는 비슷한 기호들과는 달리 출처 불명의 기호로[10], 세계적으로는 그냥 $$n^r$$라 나타낸다. 2015 개정 교육과정 기준 교과서와 참고서에서는 두 표현이 같다고 병기하여 표시되어있지만 해당 표현은 아직 완전히 사라지지 않았다.
0의 0제곱 문서에서도 다루지만, $${}_0\Pi_0 = 0^0 = 1$$이다.
3. 동자 순열 / 부분중복순열 / 같은 것이 있는 순열
$$n$$개 중에 $$r$$개를 중복없이 순서에 맞게 뽑는데, $$n$$개 중에 똑같은 것이 몇개 섞여있을 경우를 말한다. 예를들어 세 개의 문자 $$a$$, $$a$$, $$b$$를 일렬로 늘어놓는 순열의 수를 찾아보자. 직접 찾아보면 $$aab$$, $$aba$$, $$baa$$의 $$3$$가지 경우 밖에 없다. 여기서 좀 더 관찰해 보면 $$3$$개를 일렬로 늘어놓는 순열의 수는 $${}_3{\rm P}_3 = 3! = 6$$, 중복되는 문자는 $$2$$개이고, $$3 = \dfrac 62$$이다. 곧, 같은 것이 있을 때는 전체 순열의 수에서 무언가를 나눠주면 된다는 것을 확인할 수가 있다. 그리고 그 무언가는 중복되는 문자를 나열하는 방법의 수, 즉 이 예시에서는 $$2!$$이 된다.
중복되는 것이 다른 종류로 여러가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다.
4. 원순열
$$n$$개를 나열하는데, 원형으로 나열하는 경우의 수를 말한다. 예를들어 $$a$$, $$b$$, $$c$$, $$d$$를 원형으로 나열하는 가짓 수를 찾는다 하자. 얼핏 생각하면 $$4! = 24$$이라 말하기 쉽지만 처음 놓는 문자의 위치는 돌려보면 어디든지 다 '''똑같다'''. 원을 돌려버리면 그만이기 때문. 하지만 두번째 이후로 놓는 문자부터는 위치에 관계 있으며, 결국 구하고자 하는 답은 $$(4-1)! = 6$$이 된다. 이를 일반적으로 나타내면 아래와 같다.
4.1. 같은 것이 있는 원순열
링크를 참고하자.
5. 염주 순열 / 목걸이 순열
염주순열 참고
6. 완전 순열 / 교란 순열
완전순열 참고.
7. 예시
'''순열'''
$$10$$명중 $$3$$명을 뽑아 일렬로 세우는 경우의 수는?
$${}_{10}{\rm P}_3 = \dfrac{10!}{(10-3)!} = \dfrac{10!}{7!} = 720$$
'''중복 순열'''중복을 허락하여 네 개의 숫자 $$1, \ 2, \ 3, \ 4$$를 써서 세 자리 자연수를 만드는 가짓수는?
$$4^3=64$$
'''동자 순열(1)'''wiki라는 네 글자를 일렬로 나열할 때의 가짓수는?
$$\dfrac{4!}{2!} = 12$$
'''동자 순열(2)'''namuwiki라는 여덟 글자를 일렬로 나열할 때의 가짓수는?
$$\dfrac{8!}{2!} = 20160$$
'''원순열'''서로 다른 $$5$$개의 구슬을 원형으로 나열하는 가짓수는?
$$(5-1)! = 4! = 24$$
'''염주 순열 / 목걸이 순열'''서로 다른 $$5$$개의 구슬로 목걸이를 만드는 방법의 가짓수는?
$$\left\lceil \dfrac{(5-1)!}2 \right\rceil =12$$
'''완전 순열 / 교란 순열'''$$5$$명의 사람이 시험을 보고 시험지를 채점하는데 자신의 시험지는 자신이 채점할 수 없다. 채점하게 하는 방법의 가짓수는?
$$\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$$
8. 관련 문서
[1] 하강 계승(Falling Factorial)이라고도 한다.[2] 이 단어는 군론에서 치환을 의미하며, 치환의 개수는 순열로 표현할 수 있다.[3] 초등학교 때 한번쯤은 "$$\left<0, \ 1, \ 2, \ 3\right>$$중 $$3$$개를 골라서 만들 수 있는 $$3$$자리 수의 개수를 구하시오"같은 문제는 풀어봤을 것이다.[4] $$n$$부터 시작해서 하나씩 작은 수를 $$r$$개 곱한 것이다.[5] 이 식은 $$r=0$$일 때도 정의가 되기 때문에 부분곱에 의한 정의를 확장하는 효과도 있다.[6] 즉 감마 함수는 팩토리얼을 복소수 범위로 일반화시킨 것이다. 그러나 실수부가 [math(0)]보다 작거나 같은 정수를 제외한다는 점은 여전히 동일하다.[7] 가령 인수에 각각 원주율과 허수단위를 넣은 $${}_\pi{\rm P}_i$$의 값을 구해보면 $${}_\pi{\rm P}_i = 0.2977\cdots\cdots + i1.1049\cdots\cdots$$이 나온다. 그러나 이걸 직접 풀기는 '''매우 어려운데''' 링크에 나온 항등식 중 하나를 꼽아보면 $$\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)$$(단, $$\exp(x) = e^x$$) 가 나오는데 이거만 해도 어마무시한 계산 노가다를 수반한다.[8] $$n$$명 중 특정한 $$1$$명을 제외하고 뽑아 나열하는 경우의 수$$+$$특정한 $$1$$명을 포함하여 뽑아 나열하는 경우의 수[9] 물론 변수의 실수부는 [math(0)]보다 작거나 같은 정수를 제외한다.[10] 일본에서도 쓰이는 걸 보면 일본에서 유래된 듯하다.