순열

최근 수정 시각: (5년 전)
분류
목차
1. 개요
1.1. 성질
2. 중복 순열3. 동자 순열 / 부분중복순열 / 같은 것이 있는 순열4. 원순열
4.1. 같은 것이 있는 원순열
5. 염주 순열 / 목걸이 순열6. 완전 순열 / 교란 순열7. 예시8. 관련 문서

1. 개요 [편집]

서로 다른 nn개의 원소에서 rr개를 중복없이 골라 순서에 상관있게 나열하는 것을 nn개에서 rr개를 택하는 순열(順列)이라고 한다.
기호로는 nPr{}_n{\rm P}_r, P(n, r){\rm P} (n, \ r ), nr‾n^{\underline{r}}[1]등 여러가지가 있지만 한국 교육과정 상에서 자주 쓰이는 것은 nPr{}_n{\rm P}_r이다. P\rm P는 영어 명칭 permutation[2]의 머리글자에서 유래했다.

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

파일:4-12-14.png
<파이썬 알고리즘 인터뷰> p.349, 책만, 2020

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

1.1. 성질 [편집]

순열은 다음과 같은 성질을 갖는다.
nPr=n⋅n−1Pr−1=n−1Pr+r⋅n−1Pr−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]

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

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

2. 중복 순열 [편집]

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

0의 0제곱 문서에서도 다루지만, 0Π0=00=1{}_0\Pi_0 = 0^0 = 1이다.

3. 동자 순열 / 부분중복순열 / 같은 것이 있는 순열 [편집]

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

중복되는 것이 다른 종류로 여러가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다.
(a1, a1,⋯⋯ , a1⏞P1, a2, a2,⋯⋯ , a2⏞P2,⋯⋯ , an, an,⋯⋯ , an⏞Pn)\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)일 때, 즉 a1a_1이 P1\rm P_1개, a2a_2가 P2\rm P_2개, ⋯⋯\cdots\cdots, ana_n이 Pn{\rm P}_n개일 때의 순열의 수
=(∑k=1nPk)!∏k=1n(Pk!)=(P1+P2+⋯⋯+Pn)!P1!×P2!×⋯⋯×Pn!= \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!}

4. 원순열 [편집]

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

4.1. 같은 것이 있는 원순열 [편집]

링크를 참고하자.

5. 염주 순열 / 목걸이 순열 [편집]

염주순열 참고

6. 완전 순열 / 교란 순열 [편집]

완전순열 참고.

7. 예시 [편집]

순열
1010명중 33명을 뽑아 일렬로 세우는 경우의 수는?
10P3=10!(10−3)!=10!7!=720{}_{10}{\rm P}_3 = \dfrac{10!}{(10-3)!} = \dfrac{10!}{7!} = 720

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

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

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

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

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

완전 순열 / 교란 순열
55명의 사람이 시험을 보고 시험지를 채점하는데 자신의 시험지는 자신이 채점할 수 없다. 채점하게 하는 방법의 가짓수는?
D5=∑k=255P5−k(−1)k=5P3−5P2+5P1−5P0=44\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] 초등학교 때 한번쯤은 "<0, 1, 2, 3>\left<0, \ 1, \ 2, \ 3\right>중 33개를 골라서 만들 수 있는 33자리 수의 개수를 구하시오"같은 문제는 풀어봤을 것이다.[4] nn부터 시작해서 하나씩 작은 수를 rr개 곱한 것이다.[5] 이 식은 r=0r=0일 때도 정의가 되기 때문에 부분곱에 의한 정의를 확장하는 효과도 있다.[6] 즉 감마 함수는 팩토리얼을 복소수 범위로 일반화시킨 것이다. 그러나 실수부가 00보다 작거나 같은 정수를 제외한다는 점은 여전히 동일하다.[7] 가령 인수에 각각 원주율과 허수단위를 넣은 πPi{}_\pi{\rm P}_i의 값을 구해보면 πPi=0.2977⋯⋯+i1.1049⋯⋯{}_\pi{\rm P}_i = 0.2977\cdots\cdots + i1.1049\cdots\cdots이 나온다. 그러나 이걸 직접 풀기는 매우 어려운데 링크에 나온 항등식 중 하나를 꼽아보면 πPi=exp⁡(∫01i−ix+x1+π−x(1−i)+π(−1+x)ln⁡x dx)\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)=ex\exp(x) = e^x) 가 나오는데 이거만 해도 어마무시한 계산 노가다를 수반한다.[8] nn명 중 특정한 11명을 제외하고 뽑아 나열하는 경우의 수++특정한 11명을 포함하여 뽑아 나열하는 경우의 수[9] 물론 변수의 실수부는 00보다 작거나 같은 정수를 제외한다.[10] 일본에서도 쓰이는 걸 보면 일본에서 유래된 듯하다.

라이선스를 별도로 명시하지 않은 문서는 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다.
기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.

문서의 기여자는 역사 탭에서 확인할 수 있습니다.
접두어의 N: - 나무위키 사용자, R: - 리그베다 위키의 사용자를 뜻합니다.
자세한 사항은 나무위키에서 동일한 문서의 역사를 참고하시기 바랍니다.