Rearrangement

1,2,...,n 으로 수들이 나열되었을 때 각 자리에 지금 나열된 수가 오지 않도록 재배열하는 방법의 수(\(D_n \))

1. 점화식

---

n을 선택해서 같은 수가 오지 않도록 재배열하는 상황을 생각한다.

다른 수 하나랑 뒤집히는 형태가 있고, 이 때 경우의 수는 \((n-1)D_{n-2} \)

다른 수 하나를 가져오되, 원래 자신의 수 n은 또 다른 한 자리에 부여할 경우 \((n-1)D_{n-1} \)

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

2. 일반식

---

\(A_i ^C \)를 i번째 자리에 i가 오지 않도록, 즉 약한 조건이 걸려서 재배열하는 경우의 수로 놓는다.

\[D_n = | A_1 ^C \cup A_2 ^C \cup \cdots \cup A_{n-1} ^C \cup A_n ^C | \]

\[ = |U| - \left \{((n-1)!n - (n-2)! \binom {n}{2} + (n-3)! \binom {n}{3} - \cdots + (-1)^{n+1} \binom {n}{n} \right \} \]

\[= n! - (n!- \frac{1}{2!} n! + \frac{1}{3!}n! - \cdots) = n! ( \frac {1}{2!} + \frac {1}{3!} + \frac{1}{4!} \cdots )\]

포함과 배제의 원리를 사용하면 위와 같다. \(D_n\)의 정의와 \(A^C \)의 의미를 안다면 이해할 수 있다.