derangements and permutations in cryptography

Question

i have a problem that i am having a bit of trouble with;

we are given a partial key (missing 11 letters) for a mono-alphabetic substitution cipher and asked to calculate the number of possible keys given that no plaintext letter can be mapped to itself.

ordinarily, the number of possible keys would be the number of derangements of the missing letters (!11), however 5 of the plaintext letters that are missing mappings already exist as mappings in the partial key, so logically it shouldnt matter what the mapping of those plaintext letters is, because they can never map to themselves.

so shouldnt the number of possible keys be 5! * !6, ie. (the number of permutations of the 5 already mapped free letters) * (the number of derangements of the remaining 6)?

the problem is that 5! * !6 = 31800 which is much less than !11 = 14684570

intuitively the set of derangements should be a smaller subset of !11, shouldnt it?

am i just getting something wrong in my arithmetic? or am i completely missing the concepts? any help would be greatly appreciated

thanks gus

ps. i know this isn't strictly a programming question, but it is a computing question and related to a programming project, so i thought it might be pertinent. also, i posted it on math.stackexchange.com yesterday but havent had any responses yet..

EDIT: corrected the value of !11

Answer 1

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_ks are in the first 6 positions (without any of them being in the position of its own index), and the b_ks 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_ks 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.

1. If a_0 gets in one of the positions 1, 2, ..., n-1. (n-1 different possibilities.) This means that neither a_0 is at position 0, and it also prevents another a_k from being at position k by occupying that position. Thus this a_k becomes 'free', it can go to any other positions. If a_0 gets fixed this way, the other elements can be permutated in p_{n-2,m+1} different ways.

2. If a_0 gets in one of the positions n, n+1, ..., n+m-1. (m different possibilities.) This way no other a_k gets prevented to be at the position corresponding to it's index. The other elements can be permutated in p_{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.