3-5. 亂序及禁位問題

Define Derangement

{ $1$, $2$, ..., $n$ }: 相異物作排列，使得每個物品皆不在它的自然位置(原本的位置)稱為亂序(derangement)， 其排列數 $D_n$ = $n!$[$1$ - $\dfrac{1}{1!}$ + $\dfrac{1}{2!}$ - $\dfrac{1}{3!}$ + ... + ($-1$)$^n \dfrac{1}{n!}$] = $n! (\displaystyle\sum_{i=0}^{n} \dfrac{(-1)^i}{i!})$

$\because e^x$ = $\displaystyle\sum_{i=0}^{\infty} \dfrac{x^i}{i!} \Rightarrow e^{-1}$ = $\displaystyle\sum_{i=0}^{\infty} \dfrac{(-1)^i}{i!} \therefore$ 當 $n \rightarrow \infty$ 時，$D_n \approx n! e^{-1}$

Define Rook Polynomial

$C$ 為一西洋棋棋盤，可分割為 $m$ 個彼此互斥的子棋盤 $C_1$, ..., $C_n$

• 定義 $r_k$($C$) 為在 $C$ 上放置 $k$ 個城堡使得任兩城堡皆不在同一行或同一列的方法數，$k \in Z^+$

• 定義 $C$ 的車多項式或城堡多項式(rook polynomial)為 $r$($C$, $x$) = $\displaystyle\sum_{k=0}^{\infty} r_k$($C$)$x^k$，其中 $r_0$($C$) = $1$

則 $r$($C$, $x$) = $r$($C_1$, $x$)$r$($C_2$, $x$)...$r$($C_m$, $x$)