교란순열 (편집) - 시드위키

(불러오기) (편집 필터 규칙)

[[분류:가져온 문서/오메가]]
{{{#!folding 수치표
||<-4> 수치표 ||
|| [math(n)] || [math(\vert D_n\vert)] || [math(n!)] || [math(\vert D_n\vert/n!)] ||
|| 1 || 0 || 1 || 0.0000000000 ||
|| 2 || 1 || 2 || 0.5000000000 ||
|| 3 || 2 || 6 || 0.3333333333 ||
|| 4 || 9 || 24 || 0.3750000000 ||
|| 5 || 44 || 120 || 0.3666666667 ||
|| 6 || 265 || 720 || 0.3680555556 ||
|| 7 || 1854 || 5040 || 0.3678571429 ||
|| 8 || 14833 || 40320 || 0.3678819444 ||
|| 9 || 133496 || 362880 || 0.3678791887 ||
|| 10 || 1334961 || 3628800 || 0.3678794643 ||
|| 11 || 14684570 || 39916800 || 0.3678794392 ||
|| 12 || 176214841 || 479001600 || 0.3678794413 ||
|| 13 || 2290792932 || 6227020800 || 0.3678794412 ||
|| 14 || 32071101049 || 87178291200 || 0.3678794412 ||
|| 15 || 481066515734 || 1307674368000 || 0.3678794412 ||
}}}
'''교란순열'''(Derangement), '''교란''', 또는 '''완전순열'''(Complete permutation)은 집합의 어떤 원소도 원래 자리에 있지 아니한 순열이다.

== 정의 ==
집합 [math(S=\{a_1,a_2,\cdots,a_n\})] 위의 순열 [math(\sigma:S\to S)]에 대해 [math(\sigma(a_1)\ne a_1, \sigma(a_2)\ne a_2,\cdots, \sigma(a_n)\ne a_n)]이면 [math(\sigma)]를 [math(a_1,a_2,\dots, a_n)]의 교란순열이라고 한다.

== 예시 ==
집합 [math(S=\{1,2,3,4\})]에 대해 [math(\sigma(1)= a_1, \sigma(2)=a_2, \sigma(3)=a_3, \sigma(4)=a_4)]인 순열 [math(\sigma:S \to S)]를 [math(a_1a_2a_3a_4)]로 표기하자. 이때 순열 중에서 교란순열인 것은

[math(2143)], [math(2341)], [math(2413)]
[math(3142)], [math(3412)], [math(3421)]
[math(4123)], [math(4312)], [math(4321)]

로 총 아홉 개이다.

집합 [math(S=\{a_1,a_2,\cdots,a_n\})]에 대해 모든 교란의 집합을 [math(D_n)]이라 하자. [math(1\le n \le 4)]일 때 [math(S_n)]과 [math(D_n)]을 나타낸 표는 다음과 같다.

||<tablealign=center> [math(n)] || [math(S_n)] || [math(D_n)] ||
|| 1 || [math(\{1\})] || [math(\emptyset)] ||
|| 2 || [math(\{1,2\})] || [math(\{21\})] ||
|| 3 || [math(\{1,2,3\})] || [math(\{231, 312\})] ||
|| 4 || [math(\{1,2,3,4\})] || [math(\{2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321\})] ||

== 교란의 계산 ==
=== 점화식 ===
사람 [math(1,2,\dots,n)]이 [math(1,2,\dots,n)]으로 지정된 비행기 좌석에 앉는 상황을 가정하자. 이때 누구도 자신에게 할당된 수와 같지 않은 자리에 앉는 경우의 수를 구하고자 한다. 누구도 자신에게 할당된 수와 같지 않은 자리에 앉는 경우의 집합을 [math(D_n)]이라 하면, [math(|D_n|)]을 구하면 된다. 사람 [math(1)]이 좌석 [math(k)]에 앉는다고 하자. 그러면 사람 [math(1)]은 좌석 [math(1)]에 앉지 않으므로, 사람 [math(1)]이 좌석에 앉는 경우의 수는 [math(n-1)]이다. 그러면 다음 두 가지의 가능성이 존재한다.

1. 사람 [math(k)]가 좌석 [math(1)]에 앉지 않는다고 하자. 그러면 이 경우는 금지된 선택이 단 하나(사람 [math(k)]가 좌석 [math(1)]을 고르지 않는다)이므로, [math(n-1)]명이 [math(n-1)]개의 좌석에 앉는 문제와 동일하다.
2. 사람 [math(k)]가 좌석 [math(1)]에 앉는다고 하자. 그러면 나머지 [math(n-2)]명은 [math(n-2)]개 좌석에 앉는다.

따라서 다음 식이 성립한다.

[math(|D_n|=(n-1)(|D_{n-1}|+|D_{n-2}|))]

한편, [math(|D_n|=(n-1)(|D_{n-1}|+|D_{n-2}|))]의 양변에 [math(-n|D_{n-1}|)]을 더하면 [math(|D_n|-n|D_{n-1}|=-(|D_{n-1}|-(n-1)|D_{n-2}|))]이다. 따라서 다음 식이 성립한다.

[math(|D_n|=n|D_{n-1}|+(-1)^n)]

=== 일반항 표현 ===
==== 포함-배제 원리를 이용한 방법 ====
순열 [math(f)]에 대해 [math(f(i)=i)]인 순열 전체의 집합을 [math(A_i)]라 하자. 그러면 [math(D_n)]의 원소는 순열 중 [math(f(i)=i)]인 [math(i)]가 존재하는 순열들을 모두 제외한 것과 같으므로

[math(\displaystyle |D_n|=n!-|A_1 \cup A_2\cup \cdots \cup A_n|)]

이다. 포함-배제 원리에 의해

[math(\displaystyle |D_n|=n!-\left(\sum_{\alpha}|A_\alpha|-\sum_{\alpha<\beta}|A_\alpha\cap A_\beta|+\sum_{\alpha<\beta<\gamma}|A_{\alpha}\cap A_{\beta} \cap A_{\gamma}|-\cdots+(-1)^{n+1}|A_1 \cap A_2 \cap \cdots \cap A_n |\right))]

이다. 이때,

[math(|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}|=(n-k)!)]

이고 [math(n)]개의 서로 다른 집합 중 [math(k)]개를 고르는 경우의 수는 [math(\dbinom{n}{k})]이므로,

[math(\displaystyle |D_n|=n!-\sum_{k=1}^n (-1)^{k+1}(n-k)!\binom{n}{k}=n!-\sum_{k=1}^n \frac{n!(-1)^{k+1}}{k!})]

이다. 따라서 다음 식을 얻는다.

[math(\displaystyle |D_n|=n!\sum_{k=0}^n \dfrac{(-1)^k}{k!})]

[math(n=0)]부터 시작하는 수열 [math(\{|D_n|\})]은 다음과 같다.

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... (OEIS의 수열 [[https://oeis.org/A000166|A166]])

==== 생성함수를 이용한 방법 ====
수열 [math(\{|D_n|\})]의 지수 생성함수를 [math(G(x))]라고 하자. 이때 점화식 [math(|D_n|=n|D_{n-1}|+(-1)^{n})]의 양변에 [math(\dfrac{x^n}{n!})]을 곱하고 [math(\sum)]을 취하면, [math(|D_0|=1)]이므로

[math(\displaystyle\sum_{n=0}^{\infty}|D_n|\dfrac{x^n}{n!}=\sum_{n=1}^{\infty}|D_{n-1}|\dfrac{x^n}{(n-1)!}+\sum_{n=0}^{\infty}(-1)^{n}\dfrac{x^n}{n!})]

이다. 이 식을 정리하면

[math(G (x)=xG (x)+e^{-x})]

이므로

[math(G(x)=\dfrac {e^{-x}}{1-x})]

이다. 그러면

[math(\displaystyle G(x)=\left(\sum_{n=0}^{\infty}\frac{(-1)^nx^n}{n!}\right)\left(\sum_{n=0}^{\infty}x^n\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^n \frac{(-1)^k}{k!} \right)x^n)]

이므로

[math(\displaystyle |D_n|=n!\sum_{k=0}^n \frac{(-1)^k}{k!})]

을 얻는다.

==== 기타 공식 ====
[math(\displaystyle \left\vert |D_n|-\frac{n!}{e} \right\vert <\frac{1}{n+1})]

이므로, [math(n\ge 1)]이면 다음 공식을 얻는다. 이때 [math(\lfloor x \rfloor)]는 최대정수함수이다.

[math(\displaystyle |D_n|=\left\lfloor \frac{n!}{e}+\frac{1}{2}\right\rfloor,\quad n\ge 1)]

다음 식이 알려져 있다.[* P. Mark Kayll. [[https://www.maa.org/sites/default/files/pdf/upload_library/22/Allendoerfer/Kayll-2012.pdf|"Integrals Don’t Have Anything to Do with Discrete Math, Do They?"]]. Mathematics Magazine 01/2011; 84(2):108-119. DOI: 10.4169/math.mag.84.2.108 ]

[math(\displaystyle |D_n|=\int_{0}^{\infty}(t-1)^ne^{-t}dt)]

== 교란순열과 순열의 비율 ==
[[대칭군]] [math(S_n)]의 원소를 하나 선택했을 때 그것이 교란순열일 확률을 [math(p_n)]이라 하자. 그러면

[math(\displaystyle p_n=\frac{|D_n|}{n!}=\sum_{k=0}^n \frac{(-1)^k}{k!})]

이다. [math(n)]이 충분히 크면, 순열의 수에 대한 교란순열의 수의 비율은 [math(1/e)]에 수렴한다. 즉, 다음 식이 성립한다.

[math(\displaystyle \lim_{n\to \infty}\frac{|D_n|}{n!}=\lim_{n\to \infty}\sum_{k=0}^n \dfrac{(-1)^k}{k!}=\frac{1}{e}\approx 0.3678794)]

== 일반화 ==
* [math(n)]개의 원소를 일렬로 나열할 때 고정점이 [math(k)]개인 경우: 부분교란으로 경우의 수는 [math(\dbinom {n}{k}|D_{n-k}|)]이다.
* 서로 다른 [math(n)]종류의 물건이 각각 [math(n_1,n_2,\cdots,n_k)]개 있을 때, 재배치해서 모두가 다른 자리에 있게 되는 경우의 수는

[math(\displaystyle P_{n_1,\cdots,n_k}=(-1)^{n_1+\cdots+n_k}\int_0^{\infty}L_{n_1}(x)L_{n_2}(x)\cdots L_{n_k}(x)e^{-x}dx)]

로 나타낼 수 있다. 이때 [math(L_{n_i}(x))]는 라게르 다항식이다.[* Even, S.; J. Gillis (1976). [[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2128316|"Derangements and Laguerre polynomials"]]. Mathematical Proceedings of the Cambridge Philosophical Society 79 (01): 135–143. doi:10.1017/S0305004100052154.]

== 외부  ==
*  Weisstein, Eric W. [[http://mathworld.wolfram.com/Derangement.html|"Derangement."]] From MathWorld--A Wolfram Web Resource.

== 참고 문헌 ==
* 박승안(2012). 『이산수학』 (제3판). 경문사. ISBN 9788961055345

== 영상 ==
[youtube(BNLZtJFRBGA)]

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)