密碼學中的排列和排列

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通用封閉公式。突然之間，我沒有任何想法想出來，但我認爲這可能是一個很好的起點。