(1)全錯排

也稱為伯努利-歐拉錯裝信封問題

問題表述：某人寫瞭n封信，這n封信對應的有n個信封，問把所有的信都裝錯信封的情況共有多少種？

首先，我們求其遞推式：

設錯排數為 D_n

步驟1：考慮第n封信，把它裝入其他信封中的第k個信封中，有n-1種方法

步驟2：考慮第k封信，這時有2種情況：

情況1：第k封信裝入第n個信封中，那麼接著對(除第n封和第k封信外)剩餘的n-2封信進行全錯排即完成瞭該事，有 D_{n-2} 種方法；

情況2：第k封信不裝入第n個信封中，那麼接著對(除第n封信外)剩餘的n-1封信進行全錯排即完成瞭該事，有 D_{n-2} 種方法；

於是根據分步乘法原理，有： boxed{{large D_n=(n-1)(D_{n-2}+D_{n-1})}},ngeqslant 3

有瞭這個遞推式就成功一半瞭，下面的思路就是考慮找到通項公式

比較遺憾的是這個數列沒有具體的通項公式 f(n) ，但可以寫成求和的形式，推導過程如下：

運用一個巧妙的代數變形(參考書上的推導)：

begin{align*} D_n-nD_{n-1}& =(n-1)(D_{n-1}+D_{n-2})-nD_{n-1}\ & =-[D_{n-1}-(n-1)D_{n-2}]\ & =(-1)^2[D_{n-2}-(n-3)D_{n-3}]\ & =cdots \ & =(-1)^{n-2}(D_2-2D_1)\ & =(-1)^n\ end{align*}

Rightarrow D_n=nD_{n-1}+(-1)^n

兩邊同除 n! 得：

{color{Blue} {frac{D_n}{n!}}} ={color{Blue} {frac{D_{n-1}}{(n-1)!}}} +frac{(-1)^n}{n!}

於是

begin{align*} frac{D_n}{n!} & =frac{D_{n-1}}{(n-1)!}+frac{(-1)^n}{n!}\ &=frac{D_{n-2}}{(n-2)!}+frac{(-1)^{n-1}}{(n-1)!}+frac{(-1)^n}{n!} \ &=cdots \ &=frac{D_0}{0!}+frac{(-1)^1}{1!}+cdots +frac{(-1)^n}{n!} \ &=sum_{i=0}^{n}frac{(-1)^i}{i!} \ end{align*}

Rightarrow boxed{{large D_n=n!sum_{i=0}^{n}frac{(-1)^i}{i!} } }

於是得到瞭全錯排數的通項公式(隻能寫成上述求和形式瞭)

易知初值 D_0=1,D_1=0,D_2=1

如果要求信都裝錯信封的概率，那麼拿 D_n 除以總事件數 A_{n}^{n}=n! 即可

即 boxed{{large P_n=sum_{i=0}^{n}frac{(-1)^i}{i!} } }

(2)部分錯排

問題表述：某人寫瞭n封信，這n封信對應的有n個信封，問有k封信裝對信封(即有n-k封信裝錯信封)的情況共有多少種？

其實我們隻需類比全錯排中的分步討論，在前面加多一個步驟即可，具體推導如下：

步驟1：先從n封信中選k封信裝對信封，有 C_{n}^{k} 種方法

步驟2：再對剩餘的n-k封信進行全錯排(這裡就化為瞭全錯排問題)，有 D_{n-k} 種方法

根據分步乘法原理，共有 p_{n}(k)=C_{n}^{k} D_{n-k} 種排法

begin{align*} & p_{n}(k)=C_{n}^{k} (n-k)!sum_{i=0}^{n-k}frac{(-1)^i}{i!} \ & =boxed{frac{n!}{k!}sum_{i=0}^{n-k}frac{(-1)^i}{i!}}\ end{align*}

於是得到瞭部分錯排數的通項公式(這裡k是裝對信封的數目)

如果要求k封信裝對信封的概率，那麼拿 p_{n}(k) 除以總事件數 A_{n}^{n}=n! 即可

即 boxed{P_{n}(k)=frac{1}{k!}sum_{i=0}^{n-k}frac{(-1)^i}{i!}}

例題

先來幾道練練手：

例1：5人各拿出一件禮品，再從中選一件他人禮品，共有幾種可能？

審題知其為全錯排問題，有 D_5=5!sum_{i=0}^{5}frac{(-1)^i}{i!} =44 種可能

例2：重排6人小組座次，恰有2人位置沒有改變，共有幾種排法？

審題知其為部分錯排問題，有 p_{6}(2)=frac{6!}{2!}sum_{i=0}^{4}frac{(-1)^i}{i!}=135 種排法

例3：調動5人小組座次，至少3人位置發生改變，共有幾種排法？

審題知其為錯排問題(2種部分錯排和一種全錯排)，有

p_{5}(0)+p_{5}(1)+p_{5}(2)=44+45+20=109 種排法

例4：

2023肇慶二模

對A，(樣本空間)總事件數為 A_{4}^{4} (對賀卡進行全排列)

滿足條件的事件數為2(即剩餘兩人都拿到自己的賀卡或互換賀卡)，也即對剩餘的兩張賀卡進行全排列 A_{2}^{2}

則 P(A)=frac{A_{2}^{2} }{A_{4}^{4}} =frac{1}{12} ，故A錯誤；

對B，為條件概率，有兩種做法

法一：縮樣，將"小王抽到小張的賀卡"當作已知，那麼小張需要從(除自己賀卡外)剩餘的3張賀卡中抽取1張，抽到小王的賀卡的概率為 P(B)=frac{1}{3} ，故B正確；

法二：直接法。即用"小王抽到小張的賀卡 且 小張抽到小王的賀卡"的概率比上"小王抽到小張的賀卡"的概率

記前者為事件 B_1 ，後者為事件 B_2

則 P(B_1)=frac{A_{3}^{3} }{A_{4}^{4} } (讓小王抽到小張的賀卡，則還需對剩餘的3張賀卡進行全排列，即分子的 A_{3}^{3} )

P(B_2)=P(A) (即小王和小張恰好交換賀卡的概率)

於是 P(B)=frac{P(A)}{P(B_1)} =frac{1}{3} ，故B正確；

對C，也就用到瞭前文所提及的部分錯排問題，有瞭這一背景作為鋪墊，可直接寫出概率為：

{color{Green} {P_{4}(1)=frac{1}{1!}sum_{i=0}^{3}frac{(-1)^i}{i!}=frac{1}{3} }} ，故C正確；

對D，也就用到瞭前文所提及的全錯排問題，有瞭這一背景作為鋪墊，可直接寫出概率為：

{color{Green} {P_4=sum_{i=0}^{4}frac{(-1)^i}{i!} =frac{3}{8} }} ，故D錯誤；

例5：

(1)依題意隻有(2,1,1,1)這種分組方式

步驟1：先選出4個盒子以備放球，有 C_{5}^{4}=5 種選法

步驟2：對5個球進行分組，有 frac{C_{5}^{2}C_{3}^{1}C_{2}^{1}C_{1}^{1} }{A_{3}^{3}}=10 種分法

步驟3：將這4組分配到4個盒子中，有 A_{4}^{4}=24 種分法

根據分步乘法原理，共有 5times 10times 24=1200 種分法

(2)審題知，其為錯排問題，可直接寫出總分法數為：

{color{Green} {p_{5}(0)+p_{5}(1)+p_{5}(2)+p_{5}(3)+p_{5}(4)}}

當然我們用間接法更簡單，"球的編號與盒子的編號不全相同"的對立事件為"球的編號與盒子的編號全相同"，有 p_{5}(5)=1 種分法

(樣本空間)總事件數為： A_{5}^{5} =120

故滿足題意的分法有120-1=119 種

(3)審題知，其為錯排問題，可直接寫出總分法數為：

{color{Green} {p_{5}(2)+p_{5}(3)+p_{5}(4)+p_{5}(5)}} =20+10+0+1=31

總結

熟知這個錯排模型後遇到類似的題解起來會事半功倍，但不要因此就選擇硬背公式，盡可能掌握其推導過程，因為推導過程中貫穿的分類/分步思想，以及遞推的化歸思想才是內核，這些思想才是我們解決問題時真正的利刃。