I think your problem can be rephrased as the following:
How many permutation has a list with elements a_0, a_1, ... a_n-1, b_0, b_1, ..., b_m-1
, in which no a_k
element is at position k
? (Let us denote this number with p_{n,m}
- your specific question is the value of p_{6,5}
.)
Please note that your suggested formula 5!*!6 is not correct because of the following:
it only counts the cases, where the a_k
s are in the first 6 positions (without any of them being in the position of its own index), and the b_k
s on the last 5.
You do not count any other configurations like: a_3, b_4, b_1, a_0, a_5, b_0, a_2, b_2, b_3, a_1, a_4
, where the order is totally mixed.
Your other idea about the result being a subset of the !11-element derangement on all the elements is also not correct, as any of the b_k
s can be at any position.
However, we can easily add a recursive formula for p_{n,m}
by separating it into two cases based on the position of a_0
.
If
a_0
gets in one of the positions1, 2, ..., n-1
. (n-1
different possibilities.) This means that neithera_0
is at position0
, and it also prevents anothera_k
from being at positionk
by occupying that position. Thus thisa_k
becomes 'free', it can go to any other positions. Ifa_0
gets fixed this way, the other elements can be permutated inp_{n-2,m+1}
different ways.If
a_0
gets in one of the positionsn, n+1, ..., n+m-1
. (m
different possibilities.) This way no othera_k
gets prevented to be at the position corresponding to it's index. The other elements can be permutated inp_{n-1,m}
different ways.
Adding this together gives the recursion: p_{n,m} = (n-1)*p_{n-2,m+1} + m*p_{n-1,m}
. The halting conditions are p_{0,m}=m!
for every m
, as it means, that each element can be at any location.
I also coded it in python:
import math
def derange(n,m):
if n<0:
return 0
elif n==0:
return math.factorial(m)
else:
return (n-1)*derange(n-2, m+1) + m*derange(n-1, m)
print derange(6,5)
gives 22852200.
If you are interested in the general case, you can find some related sequences on OEIS.
The search term 'differences of factorial numbers' can be interesting, e.g. in triangular form: http://oeis.org/A047920.
There is also an article mentioned there: http://www.pmfbl.org/janjic/enumfun.pdf, maybe it can help if you are interested in a generic closed formula for n
and m
.
Suddenly I didn't have any good idea to come up with, but I think this can be a good starting point.