密码学中的排列和排列

Question

我有一个问题，我有点麻烦;

，我们都给出了部分关键（失踪11个字母）的单字母替代密码，并要求计算因为没有明文字母可以映射到自身可能的密钥数量。

通常情况下，可能的键的数量将是缺失字母（！11）的排列次数，然而，缺少映射的明文字母中的5个已经作为部分键中的映射存在，因此在逻辑上它不重要这些明文字母的映射是什么，因为它们不能映射到自己。

所以不应该可能的键的数量是5！ *！6，即。 （5个已经映射的免费字母的排列数）*（其余6个的排列数）？

问题是5！ *！6 = 31800远低于！11 = 14684570

直觉上，这组紊乱应该是！11的一个较小子集，不应该吗？

我只是在我的算术错误？还是我完全错过了这些概念？任何帮助将不胜感激

谢谢格古斯

ps。我知道这不是严格的编程问题，但它是一个计算问题，与编程项目有关，所以我认为它可能是相关的。另外，我昨天张贴在math.stackexchange.com但还没有过任何答复尚未..

编辑：修正值11

Answer 1

我觉得你的问题可以表述为如下：

有多少个排列有元素a_0, a_1, ... a_n-1, b_0, b_1, ..., b_m-1的列表，其中没有a_k元素位于k？ （让我们表示与p_{n,m}这个数字 - 您的具体问题是p_{6,5}值）。

请注意，您的建议公式5 * 6是因为以下的不正确： 它只能算作案件，其中！在a_k s为前6位（没有任何人在自己的索引的位置是的），和b_k S于最后5 你不要指望像任何其他配置：a_3, b_4, b_1, a_0, a_5, b_0, a_2, b_2, b_3, a_1, a_4，这里的顺序是完全混合。

对于所有元素中的！11元素紊乱的子集，您的其他想法也是不正确的，因为任何b_k都可以在任何位置。

但是，根据a_0的位置，我们可以通过将p_{n,m}的递归公式分为两种情况轻松添加递归公式。

1. 如果a_0获取位置1, 2, ..., n-1之一。 （n-1不同的可能性。） 这意味着a_0都不在位置0，并且它还通过占据该位置防止另一个a_k位于位置k。因此，这个a_k成为'自由'，它可以去任何其他职位。如果a_0以这种方式得到修复，其他元素可以通过不同的方式以p_{n-2,m+1}进行排列。

2. 如果a_0进入n, n+1, ..., n+m-1的其中一个位置。 （m不同的可能性）。 这种方式没有其他a_k被阻止在对应于它的索引的位置。其他元素可以用p_{n-1,m}不同的方式排列。

将它们加在一起给出了递归：p_{n,m} = (n-1)*p_{n-2,m+1} + m*p_{n-1,m}。因为它意味着每个元素可以在任何位置，所以每个m停止条件为p_{0,m}=m!。

我也编码它的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) 

给22852200.

如果你有兴趣在一般情况下，你可以找到一些OEIS相关序列。 搜索词“差异因子数”可能很有趣，例如三角形：http://oeis.org/A047920。 还有一篇文章提到那里：http://www.pmfbl.org/janjic/enumfun.pdf，也许它可以帮助，如果你有兴趣在n和m通用封闭公式。突然之间，我没有任何想法想出来，但我认为这可能是一个很好的起点。