More on calculating derangements

Hello coldfire Quote:

Originally Posted by

**coldfire** Thanks for the reply.

Is there a way to do these by the Principle of Inclusion-Exclusion?

You can certainly calculate $\displaystyle d_n$ using the Inclusion-Exclusion Principle, which results in an explicit formula for $\displaystyle d_n$:

$\displaystyle d_n = n!\Big(1 -\sum_{p=1}^n\frac{(-1)^{p-1}}{p!}\Big) $

This will enable you to calculate any value of $\displaystyle d_n$ directly. For example, for $\displaystyle n = 6$ this gives:

$\displaystyle d_6=6!\Big(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}\Big)$

$\displaystyle = 720 - 720 + 360 - 120 +30-6+1=265$

However, if (like me) you're using a spreadsheet to do the calculations, it's probably easier to use the recursive formula $\displaystyle d_n = (n-1)(d_{n-1}+d_{n-2})$, given that $\displaystyle d_1 = 0,\, d_2 =1$. This formula can be set up in a matter of seconds in a spreadsheet - which is what I did to get the numbers in my first posting.

Pay your money and take your choice, as the saying goes!

Grandad