subfractorial

combinatorics

what

a.k.a. the derangement number

$!n$: How many ways to arrange the $n$ objects, excluding any permutation where an object is in its original position.

formula

as sum

$$\begin{array}{rl}!n& =n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}\\ & =\sum _{k=0}^n\frac{n!(-1{)}^{n-k}}{(n-k)!}\\ & =\sum _{k=0}^{n}k!(-1{)}^{n-k}(\genfrac{}{}{0ex}{}{n}{k})\end{array}\text{\hspace{1em}(1)(2)(3)}$$

where $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is the combination.

as recursion

$$\begin{array}{rl}!n& =n\cdot !(n-1)+(-1{)}^n\\ & \\ !n& =(n-1)(!(n-2)+!(n-1))\end{array}\text{\hspace{1em}(4)(5)}$$

transformation between formulas

$(4)\to (5)$

$$\begin{array}{rl}!n& =n\cdot !(n-1)+(-1{)}^n\\ & =n\cdot ((n-1)\cdot !(n-2)+(-1{)}^{n-1})+(-1{)}^n\\ & =n(n-1)\cdot !(n-2)+n(-1{)}^{n-1}+(-1{)}^{n-1}(-1)\\ & =n(n-1)\cdot !(n-2)+(n-1)(-1{)}^{n-1}\\ & =(n-1)(n\cdot !(n-2)+(-1{)}^{n-1})\\ & =(n-1)((n-1)\cdot !(n-2)+!(n-2)+(-1{)}^{n-1})\\ & =(n-1)(!(n-1)+!(n-2))\end{array}\text{\hspace{1em}(4)(5)}$$

$(4)\to (1)$

$$\begin{array}{rl}!n& =n\cdot !(n-1)+(-1{)}^n\\ & =n\cdot (n-1)!\cdot \sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}+(-1{)}^n\\ & =n!\cdot \sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}+(-1{)}^n\frac{n!}{n!}\\ & =n!\cdot (\sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}+\frac{(-1{)}^n}{n!})\\ & =n!\cdot \sum _{k=0}^n\frac{(-1{)}^k}{k!}\end{array}\text{\hspace{1em}(4)(1)}$$

$(5)\to (1)$

$$\begin{array}{rl}!n& =(n-1)(!(n-1)+!(n-2))\\ & =(n-1)((n-1)!\cdot \sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}+(n-2)!\cdot \sum _{k=0}^{n-2}\frac{(-1{)}^k}{k!})\\ & =(n-1)(n-1)!\cdot \sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}+(n-1)(n-2)!\cdot \sum _{k=0}^{n-2}\frac{(-1{)}^k}{k!}\\ & =n(n-1)!\cdot \sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}-(n-1)!\cdot \sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}+(n-1)!\cdot \sum _{k=0}^{n-2}\frac{(-1{)}^k}{k!}\\ & =n!\cdot \sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}-(n-1)!\cdot (\sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}-\sum _{k=0}^{n-2}\frac{(-1{)}^k}{k!})\\ & =n!\cdot \sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}-(n-1)!\cdot \frac{(-1{)}^{n-1}}{(n-1)!}\\ & =n!\cdot \sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}-n!\cdot \frac{(-1{)}^{n-1}}{n!}\\ & =n!\cdot (\sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}-\frac{(-1{)}^{n-1}}{n!})\\ & =n!\cdot (\sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}+\frac{(-1{)}^n}{n!})\\ & =n!\cdot \sum _{k=0}^n\frac{(-1{)}^k}{k!}\end{array}\text{\hspace{1em}(5)(1)}$$