10497 - Sweet Child Makes Trouble
This is a derangement problem. Standard combinatorics problem - hard part is finding the recurrence.
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:
- Swap this element with another element ways to do that, and take care of two elements.
- Put another element in this location. There are elements for that.
In the first scenario, and since there are ways, and it takes care of two elements, . In the second scenario, only that element is taken care of, so . Now sum the two scenarios, and you have .
- Use BigNum. For the answer is huge.
2 3 4 5 20 -1
1 2 9 44 895014631192902121