순열: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글편집 요약 없음 |
|||
9번째 줄:
[[조합론]]에선 이와 다른 순열의 여러 가지 정의가 사용된다. 가장 자주 쓰이는 하나는 임의의 집합에서 일정 개수의 원소를 골라 순서를 뒤섞는 연산이다. <math>n</math>개의 원소에서 <math>k</math>개의 원소를 골라 순서를 뒤섞는 연산을 '''<math>n</math>의 <math>k</math>-순열'''(-順列, {{llang|en|<math>k</math>-permutation of <math>n</math>}})이라고 하며, 그 개수는 [[하강 계승]] <math>n^{\underline k}</math>와 같다. 즉, <math>n</math> 이하의 정수들 가운데 가장 큰 <math>k</math>개를 곱한 값이다.
== 정의 ==
집합 <math>X</math>의 '''순열'''은 [[전단사 함수]] <math>X\to X</math>이다. 특히, 유한 집합 <math>\{1,2,\dots,n\}</math>의 순열 <math>\sigma</math>를 다음과 같이 표기한다.
:<math>\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix}</math>
모든 <math>X</math>의 순열이 [[함수의 합성]]에 따라 이루는 [[군 (수학)|군]] <math>\operatorname{Sym}(X)</math> 또는 <math>S_X</math>를 <math>X</math>의 '''[[대칭군]]'''이라고 한다. 이는 [[집합의 크기]]에 따라 완전히 분류되며, 특히 [[기수 (수학)|기수]] <math>\kappa</math>에 대응하는 대칭군 <math>\operatorname{Sym}(\kappa)</math> 또는 <math>S_\kappa</math>를 '''<math>\kappa</math>차 대칭군'''이라고 한다. 임의의 집합의 순열은 그 밖의 모든 원소를 고정점으로 여길 경우 자연스럽게 더 큰 집합의 순열이 된다. 즉, 임의의 <math>X\subseteq Y</math>에 대하여, 자연스러운 동형에 따라 <math>\operatorname{Sym}(X)\le\operatorname{Sym}(Y)</math>이다.
=== 순환 ===
줄 23 ⟶ 22:
:<math>x\mapsto x\qquad\forall x\in X\setminus\{\dots,x_{-1},x_0,x_1,\dots\}</math>
여기서 <math>x_i\in X</math>는 서로 다른 원소이다. 특히, '''호환'''(互換, {{llang|en|transposition}}) <math>\begin{pmatrix}x&y\end{pmatrix}</math>은 2-순환이다. 특히, 유한 집합 <math>\{1,2,\dots,n\}</math>의 '''인접 호환'''(隣接互換, {{llang|en|adjecent transposition}}) <math>\begin{pmatrix}x&x+1\end{pmatrix}</math>은 인접한 두 수에 대한 호환이다.
=== 반전 ===
줄 37 ⟶ 30:
:<math>\operatorname{inv\,vec}(\sigma)_y=|\{x\in\{1,2,\dots,n\}\colon\sigma^{-1}(x)<\sigma^{-1}(y),\;x>y\}|\qquad y=1,2,\dots,n-1</math>
또한, <math>\sigma</math>의 '''반전수'''(反轉數, {{llang|en|inversion number}}) <math>\operatorname{inv\,num}(\sigma)</math> 또는 <math>N(\sigma)</math>는 <math>\sigma</math>의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다.
=== 궤도 ===
순열 <math>\sigma\in\operatorname{Sym}(X)</math>의 [[순환군]] <math>\langle\sigma\rangle</math>은 <math>X</math>의 왼쪽에서 자연스럽게 [[군의 작용|작용]]한다. 즉, <math>\sigma</math>가 <math>x\in X</math>에 작용한 결과는 <math>\sigma(x)</math>이다. 이 작용의 각 궤도 <math>\langle\sigma\rangle(x)</math> (<math>x\in X</math>)를 <math>\sigma</math>의 '''궤도'''(軌道, {{llang|en|orbit}})라고 한다.
순열 <math>\sigma\in\operatorname{Sym}(n)</math>의 '''감소량'''(減少量, {{llang|en|decrement}}) <math>\operatorname{dec}(\sigma)</math>는 <math>n</math>에서 <math>\sigma</math>의 [[군 작용|궤도]]의 개수를 뺀 것이다. 즉, 이는 다음과 같다. (이는 <math>\sigma</math>를 몇 차 대칭군의 원소로 여기는지와 무관하다.)
:<math>\operatorname{dec}(\sigma)=n-|\{\langle\sigma\rangle(x)\colon x\in\{1,2,\dots,n\}\}|=
\sum_{\langle\sigma\rangle(x)\colon\sigma(x)\ne x}(|\langle\sigma\rangle(x)|-1)</math>
=== 부호 ===
53번째 줄:
* <math>\operatorname{dec}(\sigma)</math>는 짝수이다.
* <math>\sgn(\sigma)=1</math>
== 순열의 수 ==
유한 집합 <math>\{1,2,\dots,n\}</math>의 모든 순열의 수는 <math>n</math>의 [[계승]] <math>n!</math>이다. 이들 가운데 홀순열의 수는 다음과 같다.
:<math>\begin{cases}0&n=0,1\\n!/2&n\ge 2\end{cases}</math>
또한, 짝순열의 수는 다음과 같다.
:<math>\begin{cases}1&n=0,1\\n!/2&n\ge 2\end{cases}</math>
[[조합론]]에서는 조금 더 일반화된 순열의 개념이 사용되며, 이는 다음과 같다.
==== <math>k</math>-순열 ====
음이 아닌 정수 <math>k</math>가 주어졌을 때, 집합 <math>X</math> 위의 '''<math>k</math>-순열'''(-順列, {{llang|en|<math>k</math>-permutation}})은 [[단사 함수]] <math>\{1,2,\dots,k\}\to X</math>이다. 특히, 유한 집합 <math>X=\{1,2,\dots,n\}</math>의 경우 이를 '''<math>n</math>의 <math>k</math>-순열'''이라고 한다. 이 경우, 원래의 유한 순열은 <math>n</math>의 <math>n</math>-순열이다. 풀어 말해, <math>n</math>의 <math>k</math>-순열은 서로 다른 <math>n</math>개의 원소 가운데 중복 없이 <math>k</math>개를 골라서 순서 있게 나열한 것이다. <math>n</math>의 <math>k</math>-순열의 수는 <math>n^{\underline k},{}_nP_k,P_{n,k},P(n,k)</math>와 같이 표기하며, 다음과 같이 [[하강 계승]]으로 주어진다.
:<math>n^{\underline k}=n(n-1)(n-2)\cdots(n-k+1)</math>
예를 들어, 6곡의 노래 가운데 3곡을 골라 재생 목록을 만드는 방법의 수는 다음과 같다.
:<math>6^{\underline 3}=6\times 5\times 4=120</math>
<math>n</math>의 <math>k</math>-순열의 수와 <math>n</math>의 <math>k</math>-[[조합]]의 수([[이항 계수]])의 관계는 다음과 같다.
:<math>\binom nk=\frac{n^{\underline k}}{k!}</math>
==== 중복 순열 ====
음이 아닌 정수 <math>k</math>가 주어졌을 때, 집합 <math>X</math> 위의 <math>k</math>-'''중복 순열'''(重複順列, {{llang|en|<math>k</math>-permutation with repetition}})은 <math>X</math> 위의 <math>k</math>-[[튜플]]을 뜻한다. 특히, 유한 집합 <math>\{1,2,\dots,n\}</math> 위의 <math>k</math>-튜플을 생각할 수 있으며, 이는 풀어 말해 <math>n</math>개의 원소 가운데 중복이 가능한 <math>k</math>개를 골라서 순서 있게 나열한 것이다. 그 수는 <math>n^k</math>이다. 예를 들어, 26개의 알파벳으로 구성된 3글자 단어의 수는 <math>26^3=17576</math>이다.
==== 중복집합 순열 ====
[[파일:Permutations with repetition.svg|대체글=중복집합을 우선 집합으로 여겨 순열을 취한 뒤, 다시 중복집합으로 여겨 겹치는 순열들을 제외하는 방법으로 중복집합 순열의 수를 계산한 것|섬네일|집합의 순열과 달리, 중복집합 순열에서는 같은 색깔의 원소들을 구별이 불가능하다고 여기며, 이에 따라 순열의 수가 줄어들게 된다.]]
크기 <math>n</math>의 [[중복집합]] <math>n_1\{1\}+n_2\{2\}+\cdots+n_k\{k\}</math> 위의 '''중복집합 순열'''(重複集合順列, {{llang|en|multiset permutation}}) 또는 '''같은 것이 있는 순열'''(-順列)은 다음 조건을 만족시키는 [[함수]] <math>\sigma\colon\{1,2,\dots,n\}\to\{1,2,\dots,k\}</math>이다.
:<math>|\sigma^{-1}(x)|=m(x)\qquad x=1,2,\dots,k</math>
풀어 말해, 중복집합 순열은 중복집합의 각 원소를 그 중복도만큼씩 순서 있게 나열한 것이다. 다시 말해, 원래의 순열의 정의에서, 짝지어진 원소들을 같다고 여겨 얻는 개념이다. 그 수는 다음과 같이 [[다항 계수]]로 주어진다.
:<math>\binom n{n_1,n_2,\dots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}</math>
예를 들어, 영어 단어 "MISSISSIPPI"의 [[어구전철]]의 수는 다음과 같다.
:<math>\binom{11}{1,4,4,2}=\frac{11!}{1!\times 4!\times 4!\times 2!}=34650</math>
==== 원순열 ====
유한 집합 <math>\{1,2,\dots,n\}</math> 위의 '''원순열'''(圓順列, {{llang|en|circular permutation}})은 그 위의 <math>n</math>-순환을 뜻한다. 즉, 이는 다음과 같은 [[몫군]]의 원소와 일대일 대응한다.
:<math>\operatorname{Sym}(n)/\langle\begin{pmatrix}1&2&\cdots&n\end{pmatrix}\rangle</math>
풀어 말해, 이는 <math>n</math>개의 원소를 원형 탁자에 둘러앉힌 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 원순열의 수는 다음과 같다.
:<math>\begin{cases}1&n=0\\(n-1)!&n\ge 1\end{cases}</math>
이는 원래의 <math>n!</math>에서 겹치는 배수인 <math>n</math>을 나눈 것이다. 예를 들어, 회전 다트 판의 1~20을 다시 배열하는 방법의 수는 19!이다.
==== 염주 순열 ====
유한 집합 <math>\{1,2,\dots,n\}</math> 위의 '''염주 순열'''(念珠順列) 또는 '''목걸이 순열'''은 다음과 같은 몫군의 원소와 일대일 대응한다.
:<math>\operatorname{Sym}(n)/(\langle\begin{pmatrix}1&2&\cdots&n\end{pmatrix},n+1-\operatorname{id}_n\rangle)</math>
풀어 말해, 이는 <math>n</math>개의 원소를 염주에 꿴 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전 및 뒤집기만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 염주 순열의 수는 다음과 같다.
:<math>\begin{cases}1&n=0,1,2\\(n-1)!/2&n\ge 3\end{cases}</math>
이는 원래의 <math>n!</math>에서 겹치는 배수인 <math>2n</math>을 나눈 것이다. 처음 몇 염주 순열의 수는 다음과 같다. (<math>n=1,2,\dots</math>)
:1, 1, 1, 3, 12, 60, 360, 2520, ... {{OEIS|A001710}}
== 예 ==
순열의 합성의 한 가지 예는 다음과 같다.
:<math>
\begin{pmatrix}1&2&3&4&5\\3&2&1&5&4\end{pmatrix}
\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}=
\begin{pmatrix}2&5&4&3&1\\2&4&5&1&3\end{pmatrix}
\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}=
\begin{pmatrix}1&2&3&4&5\\2&4&5&1&3\end{pmatrix}</math>
순열의 역의 한 가지 예는 다음과 같다.
:<math>
\begin{pmatrix}1&2&3&4&5&6&7\\3&1&4&7&6&5&2\end{pmatrix}^{-1}=
\begin{pmatrix}2&7&1&3&6&5&4\\1&2&3&4&5&6&7\end{pmatrix}^{-1}=
\begin{pmatrix}1&2&3&4&5&6&7\\2&7&1&3&6&5&4\end{pmatrix}</math>
순열의 서로소 순환 분해의 한 가지 예는 다음과 같다.
:<math>
\begin{pmatrix}1&2&3&4&5\\4&1&5&2&3\end{pmatrix}=
\begin{pmatrix}1&4&2&3&5\\4&2&1&5&3\end{pmatrix}=
\begin{pmatrix}1&4&2\end{pmatrix}
\begin{pmatrix}3&5\end{pmatrix}</math>
순열의 홀짝성의 몇 가지 예는 다음과 같다.
* 항등 함수는 짝순열이다.
* 호환은 홀순열이다.
* 짝수 길이의 순환은 홀순열이다.
* 홀수 길이의 순환은 항상 짝순열이다.
크기 3의 대칭군 <math>\operatorname{Sym}(3)</math>의 [[켤레류]]는 다음과 같다.
:<math>
\begin{pmatrix}1&2&3\end{pmatrix}\sim
\begin{pmatrix}1&3&2\end{pmatrix}</math>
:<math>
\begin{pmatrix}1&2\end{pmatrix}
\begin{pmatrix}3\end{pmatrix}\sim
\begin{pmatrix}1&3\end{pmatrix}
\begin{pmatrix}2\end{pmatrix}\sim
\begin{pmatrix}2&3\end{pmatrix}
\begin{pmatrix}1\end{pmatrix}</math>
:<math>
\begin{pmatrix}1\end{pmatrix}
\begin{pmatrix}2\end{pmatrix}
\begin{pmatrix}3\end{pmatrix}</math>
이들에 대응하는 3의 [[자연수의 분할|분할]]은 각각 다음과 같다.
:<math>3=3</math>
:<math>3=1+2</math>
:<math>3=1+1+1</math>
순열의 반전수의 몇 가지 예는 다음과 같다.
:<math>\operatorname{inv\,num}(\operatorname{id}_n)=0</math>
:<math>\operatorname{inv\,num}(
\begin{pmatrix}x&y\end{pmatrix})=|\{(y,x+1),(y,x+2),\dots,(y,y-1),(x+1,x),(x+2,x),\dots,(y-1,x),(y,x)\}|=2|y-x|-1</math>
:<math>\operatorname{inv\,num}(
\begin{pmatrix}1&2&\cdots&n\\n&n-1&\cdots&1\end{pmatrix})=\binom n2=
\begin{cases}0&n=0,1\\n(n-1)/2&n\ge 2\end{cases}</math>
== 성질 ==
줄 157 ⟶ 250:
:<math>\operatorname{Alt}(n)=\ker\sgn\triangleleft\operatorname{Sym}(n)</math>
홀순열의 집합은 부분군이 아니다. 또한, <math>n=0,1</math>의 경우 홀순열이 존재하지 않는다. 그러나, <math>n\ge 2</math>의 경우 홀순열의 집합은 크기가 교대군과 같으며, 교대군의 (자기 자신을 제외하면 유일한) [[잉여류]]이다.
== 관련 개념 ==
| |||