math - 密码学中的困惑和排列

Question

我有一个问题，我遇到了一些麻烦；

我们得到了一个单字母替换密码的部分 key (缺少 11 个字母)，并要求我们计算可能的 key 数量，因为没有明文字母可以映射到其自身。

通常，可能的键的数量将是丢失字母的困惑数量(!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 位于前 6 个位置的情况(没有任何一个位于其自己索引的位置)，以及 b_k 位于最后 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 都可以位于任何位置。

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

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 的通用封闭公式感兴趣，也许它会有所帮助。 突然我想不出什么好主意，但我认为这可以是一个很好的起点。