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$의 의미를 안다면 이해할 수 있다.