密碼學中的混亂和排列
給定單字母替換密碼的部分密鑰（缺少 11 個字母），計算數字 $ N $ 可能的鍵，因為沒有明文字母可以映射到自身。
通常，可能的鍵數將是失去字母的混亂數 $ !11 $ . 但是，缺少映射的明文字母中有 5 個已經作為映射存在於部分鍵中，因此從邏輯上講，這些明文字母的映射是什麼並不重要，因為它們永遠無法映射到自己。
所以，我想知道可能的鍵數是否為 $ N = 5! * !6 $ . 那是：
(no. permutations of 5 already mapped free letters) * (no. derangements of the remaining 6)問題是5！* !6 = 31800 遠小於 !11 = 14684570 直覺地說，紊亂集應該是較小的子集，所以肯定 $ N>!11 $ .
我的算術有什麼問題還是我完全錯過了這些概念？
這純粹是一個計數問題。我們要號碼 $ N(n,m) $ 的可能排列 $ n $ 事物，只有這樣的約束 $ m $ 在這些東西中可以映射到它們自己（ $ 0\le m\le n $ ）。問題中的值是 $ n=11 $ , $ m=5 $ .
它認為 $ N(n,n)=n! $ （這是排列的數量 $ n $ 元素）。
它認為 $ N(n,0)=\text{}!n=\begin{cases} 1 &\text{if }n=0\ \lfloor{{n!+1}\over e}\rfloor&\text{if }n>0\ \end{cases} $
（這是錯亂的數量 $ n $ 元素）。
計算由 $ N(11,5) $ 作為 $ 5!\cdot\text{}!(11-5)=31,800 $ 如前所述，在問題中是錯誤的：這小於 $ !11=14,684,570 $ ，當它應該高於（但仍低於 $ 11!=39,916,800 $ ）。犯了兩個錯誤：
- 這 $ m=5 $ 可以不受限制地分配的東西 $ n=11 $ 可以這樣 $ n!\over(n-m)! $ 方式，不是 $ m! $ 方法; 解決這個問題，我們會得到 $ {11!\over(11-5)!}\cdot\text{}!(11-5)=14,691,600 $ ，更可信；
- 但在第一次分配之後 $ m=5 $ 不受約束的事情，分配給 $ n-m=6 $ 其他事情取決於我們如何安排不受約束的事物（如果我們將其中一個不受約束的事物分配給最初受約束的事物，則後者變得不受約束）；因此，上述 $ 14,691,600 $ 明顯太低。
深吸一口氣，我們可以看到 $ N(n,m) $ 可以得到
$$ \begin{cases} 1 &\text{if }n=0, m=0\ 0 &\text{if }n=1, m=0\ n\cdot N(n-1,n-1) &\text{if }n>0, m=n\ (n-1)\cdot N(n-1,1) &\text{if }n>1, m=0\ m\cdot N(n-1,m-1)+(n-m)\cdot N(n-1,m)&\text{if }0<m<n\ \end{cases} $$ 理由：
什麼時候 $ n=0, m=0 $ ：只有一種方法可以映射任何內容；與 $ 0!=\text{}!0=1 $ .
什麼時候 $ n=1, m=0 $ ：沒有一個事物的排列不會將該事物映射到自身；與 $ \text{}!1=0 $ .
什麼時候 $ n>0, m=n $ ：我們將一個不受約束的事物分配給一個不受約束的事物（因此在 $ n $ 可能的方式），離開 $ n-1 $ 不受約束的事物；這就是經典的階乘遞歸。
什麼時候 $ n>1, m=0 $ ：我們將一個受約束的事物分配給一個受約束的事物而不是它本身（因此在 $ n-1 $ 可能的方式），離開 $ n-1 $ 其中的東西 $ 1 $ 變得不受約束。
什麼時候 $ 0<m<n $ ：我們分配一個不受約束的東西，要麼
- 對一個不受約束的事物（因此在 $ m $ 可能的方式），離開 $ n-1 $ 其中的東西 $ m-1 $ 不受約束的；
- 對受約束的事物（因此在 $ n-m $ 可能的方式），離開 $ n-1 $ 其中的東西 $ m $ 不受約束的，包括變得不受約束的。
我明白了 $ N(13,6)=3,597,143,040 $ ， 和 $ N(11,5)\equiv67\pmod{97} $ .
如果我們不介意 $ m=n+1 $ 潛入， $ N(n,m) $ 也可以得到
$$ \begin{cases} (n-1)\cdot N(n-1,1) &\text{if }n>0, m=0\ m\cdot N(n-1,m-1)+(n-m)\cdot N(n-1,m)&\text{if }0<m\le n\ 1 &\text{otherwise}\ \end{cases} $$ 或作為 $$ \begin{cases} n\cdot N(n-1,n-1) &\text{if }n>0, m=n\ m\cdot N(n-1,m)+(n-m-1)\cdot N(n-1,m+1)&\text{if }0\le m<n\ 1 &\text{otherwise}\ \end{cases} $$ 新關係的正當性 $ 0\le m<n $ ：我們分配一個受約束的東西，要麼
- 對一個不受約束的事物（因此在 $ m $ 可能的方式），離開 $ n-1 $ 其中的東西 $ m $ 不受約束的；
- 對除自身以外的受約束的事物（因此在 $ n-m-1 $ 可能的方式），離開 $ n-1 $ 其中的東西 $ m+1 $ 不受約束的，包括變得不受約束的。
基於由數字證據證實的直覺， $ m\mapsto N(n,m) $ 之間接近指數 $ m=0 $ 和 $ m=n $ , 我斷言
$$ N(n,m)\approx n!\cdot e^{m/n-1} $$ 這個近似值是多餘的，當 $ m>0 $ . 所犯的錯誤小於 $ 4.0% $ 為了 $ n\ge4 $ ; 少於 $ 1.8% $ 為了 $ n\ge8 $ ; 少於 $ 1.0% $ 為了 $ n\ge14 $ . 更嚴格的說：
$$ \forall r\in\mathbb R, 0\le r\le1\implies\lim_{n\rightarrow\infty}{n!\cdot e^{r-1}\over N(n,\lfloor r\cdot n\rfloor)}=1 $$