# UVa 10497

## Summary

This is a derangement problem. Standard combinatorics problem - hard part is finding the recurrence.

## Explanation

Given n arrangements, we can look at it in the following way:

`1 2 3 4 5 ... n`

all in their original permutation. So how many ways are there to solve it?

There are two cases, looking at any one particular element:

1. Swap this element with another element ${\displaystyle n-1}$ ways to do that, and take care of two elements.
2. Put another element in this location. There are ${\displaystyle n-1}$ elements for that.

In the first scenario, and since there are ${\displaystyle n-1}$ ways, and it takes care of two elements, ${\displaystyle f(n)=(n-1)f(n-2)}$. In the second scenario, only that element is taken care of, so ${\displaystyle f(n)=(n-1)f(n-1)}$. Now sum the two scenarios, and you have ${\displaystyle f(n)=(n-1)(f(n-1)+f(n-2))}$.

## Gotchas

• Use BigNum. For ${\displaystyle N=800}$ the answer is huge.

```2
3
4
5
20
-1
```

## Output

```1
2
9
44
895014631192902121
```