mir.pe (일반/어두운 화면)
최근 수정 시각 : 2024-03-25 10:19:04

순열


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


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

1. 개요

permutation / 順 列

서로 다른 [math(n)]개의 원소에서 [math(r)] (단, [math(0<r\le n)])개를 중복없이 순서를 고려하여 선택하거나 나열하거나 하는 것을 순열(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]의 머리글자다.

특히, [math(n = r)]인 경우, 순열의 수는 [math({}_n{\rm P}_n)]이며, 이럴 경우 순열은 1부터 [math(n)]까지의 자연수를 차례로 곱한 n의 계승 [math(n!)]과 같다.

뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념 중 하나다[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 = \dfrac62)]이다. 곧, 같은 것이 있을 때는 전체 순열의 수에서 무언가를 나눠주면 된다는 것을 확인할 수가 있다. 그리고 그 무언가는 중복되는 문자를 나열하는 방법의 수는 이 예시에서는 [math(2!)]이 된다.

중복되는 것이 다른 종류로 여러 가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다.
[math(( \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} ))]일 때, 즉 [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. 초순열

superpermutation

[math(n)]종류의 서로 다른 원소를 1개씩 뽑아내어 순서대로 나열한 순열의 수는 [math(n!)]이다. 그런데, 이렇게 만들어진 [math(n!)]개의 모든 순열을 전부 내포한 순열을, 그리고 그중에서도 길이가 최소인 순열을 생각할 수 있다. 이를 초순열이라고 한다.

예를 들어서 3종류의 원소 [math(a,b,c)]를 이용한 순열은 [math(abc, acb, bac, bca, cab, cba)]의 6개가 된다. 이 여섯개의 순열을 전부 내포한 최소 순열은 [math(abcabacba)]이고 그 길이는 9이다.

[math(n)]이 1부터 5까지일 때의 초순열의 최소길이는 각각 다음과 같다. 초순열의 수열은 현재 [math(n=5)]까지만 밝혀져 있다. 6부터는 현재까지 발견된 초순열이 진짜로 최소 길이인지가 불명이다.
[math(n)] [math(S_n)]
1 1
2 3
3 9
4 33
5 153

이 순열은 [math(\displaystyle \sum_{k=1}^{n}k!)]와 일치하기 때문에 당연히 그 이후로도 동일할 것이라 여겨졌으나, [math(n=6)]에서 반례가 발견되었다. [math(n=6)]에서 [math(\displaystyle \sum_{n=1}^{6}n!=873)]이지만, 2014년에 살짝 짧은 크기 872짜리 초순열이 발견되었기 때문.

이후 상한과 하한을 찾는 문제로 변화하게 된다. 상한은 [math(S_n\leq n!+(n-1)!+(n-2)!+(n-3)!+n-3)]이라는 것이 2018년 발견되었다. 하한은 그보다 매우 빠른 2011년 9월 17일에 이미 [math(S_n\geq n!+(n-1)!+(n-2)!+n-3)]라는게 증명이 되어 있긴 한데, 출처가 일반적인 수학 저널이 아니라 후술한 대로 4ch였기 때문에 묻혔다.

하한을 증명하게 된 계기가 상당히 특이하다. 스즈미야 하루히의 우울 TVA(1기) 방영 당시 화수가 이리저리 뒤섞여 있었고, 바로 이 1기의 14화를 상상할 수 있는 순서대로 나열한 모든 방법으로 전부 볼 수 있는 최소의 열람수를 알고 싶어하는 질문이 4ch의 sci에 올라온 것에서 시작된 것이었다. 그래서 별명은 하루히 문제(Haruhi problem). 현재 하루히 문제의 원형에 해당하는 답(=[math(S_{14})])은 알려져 있지 않으나, 위에서 증명된 상한과 하한을 고려하면 938.8억회 이상 939.25억회 이하라는 것은 확실하다.

증명 과정에는 치환과 그래프 이론이 사용되었다. 초순열을 조금 변형하면 가중치를 부여한 그래프 형태로 환원이 가능하기 때문에 그래프 이론을 사용할 수 있었던 것.

8. 예시

9. 관련 문서


[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] i가 두 번 들어간다. [15] e가 두 번, s가 두 번 들어간다. [16] l이 두 번, t가 두 번 들어간다. [17] i가 세 번, l이 두 번, n이 두 번 들어간다. [18] 고등학교 확률과 통계에서 자주 나오는 유형이다. [19] 여학생을 하나의 묶음으로 생각하고([math(3!)]), 묶인 여학생들의 자리가 바뀌는 경우의 수 [math(2)]를 곱해준다.

분류