순열

덤프버전 :

파일:다른 뜻 아이콘.svg
은(는) 여기로 연결됩니다.
후한의 인물 순열에 대한 내용은 순열(후한) 문서
순열(후한)번 문단을
순열(후한)# 부분을
, {{{#!html }}}에 대한 내용은 문서
#s-번 문단을
#s-번 문단을
# 부분을
# 부분을
, {{{#!html }}}에 대한 내용은 문서
#s-번 문단을
#s-번 문단을
# 부분을
# 부분을
, {{{#!html }}}에 대한 내용은 문서
#s-번 문단을
#s-번 문단을
# 부분을
# 부분을
, {{{#!html }}}에 대한 내용은 문서
#s-번 문단을
#s-번 문단을
# 부분을
# 부분을
, {{{#!html }}}에 대한 내용은 문서
#s-번 문단을
#s-번 문단을
# 부분을
# 부분을
, {{{#!html }}}에 대한 내용은 문서
#s-번 문단을
#s-번 문단을
# 부분을
# 부분을
, {{{#!html }}}에 대한 내용은 문서
#s-번 문단을
#s-번 문단을
# 부분을
# 부분을
, {{{#!html }}}에 대한 내용은 문서
#s-번 문단을
#s-번 문단을
# 부분을
# 부분을
, {{{#!html }}}에 대한 내용은 문서
#s-번 문단을
#s-번 문단을
# 부분을
# 부분을
참고하십시오.








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



1. 개요[편집]


/ falling factorial

서로 다른 [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)][2]등 여러가지가 있지만 한국 교육과정 상에서 자주 쓰이는 것은 [math({}_n{\rm P}_r)]이다. [math(\rm P)]는 영어 명칭 permutation[3]의 머리글자다.

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

뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념 중 하나다[4]. 계산하는 방법도 초등학교에서 해왔던 방법 그대로이며, 단지 미지수가 추가된 것 뿐. 다음 그림과 같이 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 ))].[5] 이를 팩토리얼을 사용하여 좀더 간략화 하면 [math({}_n{\rm P}_r = \dfrac{n!}{(n-r)!})]이다.[6] 자연수 범위에서 팩토리얼이 감마 함수와 동치[7]라는 것을 이용해서 [math({}_n{\rm P}_r = \dfrac{\Gamma ( n+1 )}{\Gamma ( n-r+1 )})]의 꼴로 바꿀 수 있으며, 실수/복소수 순열도 구할 수 있다.[8]

중국에서는 순열과 조합을 이과만 배운다.

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})][9]

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

감마 함수를 이용해서도 증명이 가능하며, 이 경우 정의역이 복소수 범위로 확장[10]된다는 데에 의의가 있다. [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)]이라는 표현을 쓰는데, 순열과 조합에서 쓰이는 비슷한 기호들과는 달리 출처 불명의 기호로[11], 세계적으로는 그냥 [math(n^r)]으로 나타낸다. 2015 개정 교육 과정 기준 교과서와 참고서에서는 두 표현이 같다고 병기하여 표시되어 있지만 해당 표현은 아직 완전히 사라지지 않았다.

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


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


[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)]이라 말하기 쉽지만 처음 놓는 문자의 위치는 돌려보면 어디든지 다 똑같다. 원을 돌려버리면 그만이기 때문.[13]하지만 두번째 이후로 놓는 문자부터는 위치에 관계 있으며, 결국 구하고자 하는 답은 [math((4-1)! = 6)]이 된다. 이를 일반적으로 나타내면 아래와 같다.[14]
[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까지일 때의 초순열의 최소길이는 각각 다음과 같다.[15]

[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)]에서 반례가 발견되었기에[16] 이후 상한과 하한을 찾는 문제로 변화하게 된다. 상한은 [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). 현재 하루히 문제의 원형에 해당하는 답은 알려져 있지 않으나, 위에서 증명된 상한과 하한을 고려하면 938.8억회 이상 939.25억회 이하라는 것은 확실하다.

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

8. 예시[편집]


  • 순열
[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[17]라는 4글자를 일렬로 나열할 때의 경우의 수는?
[math(\dfrac{4!}{2!} = 12)]

  • 동자 순열(2)
genesis[18]라는 7글자를 일렬로 나열할 때의 경우의 수는?
[math(\dfrac{7!}{2!×2!} = 1260)]

  • 동자 순열(3)
hillstate[19]라는 9글자를 일렬로 나열할 때의 경우의 수는?
[math(\dfrac{9!}{2!×2!} = 90720)]

  • 동자 순열(4)
illumination[20]이라는 12글자를 일렬로 나열할 때의 경우의 수는?
[math(\dfrac{12!}{3!×2!×2!} = 19958400)]

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

  • 원순열(2)
프로미스나인 [math(8)]명이 원탁에 앉는 경우의 수는?
[math((8-1)! = 7! = 5040)]

  • 원순열(3)
남학생 [math(3)]명과 여학생 [math(2)]명을 원탁에 앉힐 때, 여학생끼리 이웃하지 않게 앉히는 경우의 수는?[21]
  • 풀이 1
우선 남학생 [math(1)]명을 아무 자리에나 앉힌다. 그러면 [math(4)]자리가 남고, 이 남은 자리에 나머지 학생들을 앉히는 모든 경우의 수는 [math(4!=24)]가지다. 문제에선 여학생들끼리 이웃하지 말라고 했지만 역으로 이용해서, 여학생끼리 이웃하는 경우의 수는 [math(3!×2=12)]가지[22]이다. 고로 정답은 [math(24-12=12)]가지이다.
  • 풀이 2
우선 여학생 [math(1)]명을 아무 자리에나 앉힌다. 이때 다른 여학생이 앉을 수 있는 자리는 그 여학생이 앉은 자리의 양 옆이 아닌 두 자리뿐인데, 이 여학생이 앉는 경우의 수는 [math(2)]가지다. 그러면 남학생 [math(3)]명이 앉을 자리 세 자리가 남고, 나머지 남학생을 모두 앉히는 경우의 수는 [math(3!=6)]가지이므로 정답은 [math(2×6=12)]가지이다.

  • 염주 순열 / 목걸이 순열
서로 다른 [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)]


9. 관련 문서[편집]



파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-12-04 12:13:03에 나무위키 순열 문서에서 가져왔습니다.

[1] 고등학교 확률과 통계(확통)에서는 이 용어로 학습한다.[2] [math(n^{\underline{r}})], [math((n)_r)]은 하강 계승()이라는 이름으로 주로 불린다.[3] 이 단어는 군론에서 치환을 의미하며, 치환의 개수는 순열로 표현할 수 있다.[4] 초등학교 때 한번쯤은 "[math(\left<0,\,1,\,2,\,3\right>)]중 [math(3)]개를 골라서 만들 수 있는 [math(3)]자리 수의 개수를 구하시오"같은 문제는 풀어봤을 것이다.[5] [math(n)]부터 시작해서 하나씩 작은 수를 [math(r)]개 곱한 것이다.[6] 이 식은 [math(r=0)]일 때도 정의가 되기 때문에 부분곱에 의한 정의를 확장하는 효과도 있다.[7] 즉, 감마 함수는 팩토리얼을 복소수 범위로 일반화시킨 것이다. 그러나 실수부가 [math(0)]보다 작거나 같은 정수를 제외한다는 점은 여전히 동일하다.[8] 가령 인수에 각각 원주율허수단위를 넣은 [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)]) 가 나오는데 이거만 해도 어마무시한 계산 노가다를 수반한다.[9] [math(n)]명 중 특정한 [math(1)]명을 제외하고 뽑아 나열하는 경우의 수[math(+)]특정한 [math(1)]명을 포함하여 뽑아 나열하는 경우의 수[10] 물론 변수의 실수부는 [math(0)]보다 작거나 같은 정수를 제외한다.[11] 일본에서도 쓰이는 걸 보면 일본에서 유래된 듯하다. 지수 꼴로 간략하게 표현할 수 있으니 세계적으로는 굳이 기호를 만들 필요성을 못 느낀 것.[12] 고등학교 확률과 통계(확통)에서는 이 용어로 학습한다.[13] 이 때문에 원형 하노이 탑은 순서를 생각하지 않아도 된다. 일직선 하노이 탑은 순서를 생각할 수 있어서 경우의 수가 더 많다. [14] 직관적으로 설명하자면 일단 아무 자리에나 한 명을 앉히고 시작하면 된다. [15] 초순열의 수열은 현재 [math(n=5)]까지만이 밝혀져 있다. 6부터는 아직 발견된 초순열이 진짜로 최소 길이인지도 불명.[16] [math(n=6)]에서 [math(\displaystyle \sum_{n=1}^{6}n!=873)]이지만, 2014년에 크기 872짜리 초순열이 발견되었다.[17] i가 두 번 들어간다.[18] e가 두 번, s가 두 번 들어간다.[19] l이 두 번, t가 두 번 들어간다.[20] i가 세 번, l이 두 번, n이 두 번 들어간다.[21] 고등학교 확률과 통계에서 자주 나오는 유형이다.[22] 여학생을 하나의 묶음으로 생각하고([math(3!)]), 묶인 여학생들의 자리가 바뀌는 경우의 수 [math(2)]를 곱해준다.