교란순열 (편집) (6)

(편집 필터 규칙)

==== 포함-배제 원리를 이용한 방법 ====
순열 [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]])

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

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