4
$\begingroup$

Need help with this: $$D_n=(n-1)(D_{n-1}+D_{n-2})$$ $$n\ge2$$ $$D_1=0,D_2=1$$

This is actually recurrence relation of derangement numbers.

$\endgroup$
3
$\begingroup$

Given ${D}(0)=1$ and ${D}(1)=0$, and the recursion $$D_n=(n-1)\big(D_{n-1}+D_{n-2}\big) \tag1$$Subtracting $n{D}(n-1)$ from both sides of $(1)$ yields $$ {D}(n)-n{D}(n-1)=-({D}(n-1)-(n-1){D}(n-2))\tag{2} $$ Let$ A_n = D_n - n D_{n-1}$, and the recurrence relation becomes $A_n = - A_{n-1}$. With $A_0 = 1$, this recurrence is easy to solve, and we get $D_n - n D_{n-1} = A_n = (-1)^n$. Hence : $$ {D}(n)-n{D}(n-1)=(-1)^n\tag{3} $$ Dividing both sides of $(3)$ by $n!$ yields $$ \frac{{D}(n)}{n!}-\frac{{D}(n-1)}{(n-1)!}=\frac{(-1)^n}{n!}\tag{4} $$ Equation $(4)$ is very simple to solve for $\dfrac{{D}(n)}{n!}$: $$ \frac{{D}(n)}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}+C\tag{5} $$ Putting $n=0$ into equation $(5)$ yields that $C=0$. Therefore,

$$ {D}(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!} $$

$\endgroup$
3
$\begingroup$

By setting $D_n = n! E_n$ we get the following recurrence relation for $E_n$: $$ E_n = \left(1-\frac{1}{n}\right) E_{n-1} + \frac{1}{n} E_{n-2} \tag{1} $$ then by setting $\Delta_n=E_n-E_{n-1}$ we get $$ \Delta_n = -\frac{1}{n} \Delta_{n-1} \tag{2}$$ from which $\Delta_n = \frac{(-1)^n}{n!}$ and $$ D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}\tag{3} $$ You may notice that $\sum_{k=0}^{n}\frac{(-1)^k}{k!}$ converges pretty fast to $\frac{1}{e}$, hence $\frac{1}{e}$ is the asymptotic probability that a random element in $S_n$ (for a large $n$) is a derangement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.