錯(cuò)排問題

2022-01-21 19:26 作者:匆匆-cc 0人讀過 | 我要投稿

（浙江理科.2010.17）有4位同學(xué)在同一天的上午和下午參加“身高與體重”、“立定跳遠(yuǎn)”、“肺活量”、“握力”、“臺(tái)階”等五個(gè)項(xiàng)目的測試，每位同學(xué)上午和下午各測試一個(gè)項(xiàng)目，且不重復(fù)。若上午不測“握力”項(xiàng)目，下午不測“臺(tái)階”項(xiàng)目，其余項(xiàng)目上午和下午都各測試一人，則不同的安排方式共有________種。（用數(shù)字作答）

????????先吐槽一句，引號(hào)之間不該用頓號(hào)連接。

? ? ? ? 枚舉自然不在話下，關(guān)鍵在于有無一通用的思路。

???????? $n$ 個(gè)有序的元素應(yīng)有 $n!$ 個(gè)不同的排列，若存在一個(gè)排列使得所有的元素均不在原來的位置上，則稱這個(gè)排列為錯(cuò)排。

? ? ? ? 錯(cuò)排問題

????????涉及 $n$ 的問題，我們考慮數(shù)列遞推解題。

????????顯然有 $D_%7B1%7D%3D0$ ， $D_%7B2%7D%3D1$ 。

????????對(duì)于 $D_%7Bn%2B1%7D$ 中的第 $1$ 個(gè)元素，不妨設(shè)其對(duì)應(yīng)第 $i$ 個(gè)元素（ $i%5Cneq%201$ ），這共有 $n$ 種情況。然后考慮以下兩種情況：

????????①第 $i$ 個(gè)元素同時(shí)對(duì)應(yīng)第 $1$ 個(gè)元素，即為剩下（ $n-1$ ）個(gè)元素錯(cuò)排，有 $D_%7Bn-1%7D$ 種情況。

????????②第 $i$ 個(gè)元素并不同時(shí)對(duì)應(yīng)第 $1$ 個(gè)元素，仔細(xì)一想，會(huì)發(fā)現(xiàn)這等價(jià)于 $n$ 個(gè)元素錯(cuò)排（一定要仔細(xì)想，精髓在此），有 $D_%7Bn%7D$ 種情況。

????????所以，根據(jù)加法原理與乘法原理，我們得到：

$D_%7Bn%2B1%7D%3Dn(D_%7Bn-1%7D%2BD_%7Bn%7D)$

????????這是這一問題的核心等式。

????????下面進(jìn)行數(shù)列推導(dǎo)。

$D_%7Bn%7D%3D(n-1)D_%7Bn-1%7D%2B(n-1)D_%7Bn-2%7D$

$D_%7Bn%7D-nD_%7Bn-1%7D%3D-%5BD_%7Bn-1%7D-(n-1)D_%7Bn-2%7D%5D$

$%5Cbegin%7Balign%7D%0AD_%7Bn%7D-nD_%7Bn-1%7D%26%3D(-1)%5E%7Bn-2%7D(D_2-2D_1)%0A%5C%5C%26%3D(-1)%5E%7Bn-2%7D(1-2%5Ctimes0)%0A%5C%5C%26%3D(-1)%5E%7Bn-2%7D%0A%5C%5C%26%3D(-1)%5En%0A%5Cend%7Balign%7D$

$%5Cfrac%7BD_n%7D%7Bn!%7D-%5Cfrac%7BD_%7Bn-1%7D%7D%7B(n-1)!%7D%3D%5Cfrac%7B(-1)%5En%7D%7Bn!%7D$

$%5Cbegin%7Balign%7D%0A%5Cfrac%7BD_n%7D%7Bn!%7D%26%3D%5Csum_%7Bi%3D2%7D%5En%20%5Cfrac%7B(-1)%5Ei%7D%7Bi!%7D%2B%5Cfrac%7BD_1%7D%7B1!%7D%0A%5C%5C%26%3D%5Csum_%7Bi%3D2%7D%5En%20%5Cfrac%7B(-1)%5Ei%7D%7Bi!%7D%0A%5C%5C%26%3D%5Csum_%7Bi%3D0%7D%5En%20%5Cfrac%7B(-1)%5Ei%7D%7Bi!%7D%0A%5Cend%7Balign%7D$

$D_n%3Dn!%5Csum_%7Bi%3D0%7D%5En%20%5Cfrac%7B(-1)%5Ei%7D%7Bi!%7D$

????????該數(shù)列前幾項(xiàng)為：

$0%2C1%2C2%2C9%2C44%2C265%EF%BC%8C%E2%80%A6$

????????有意思的是，該數(shù)列還有一個(gè)簡化公式：

$D_n%3D%5B%5Cfrac%7Bn!%7D%7Be%7D%2B%5Cfrac%7B1%7D%7B2%7D%5D$

????????也就是說， $D_n%3D%5Cfrac%7Bn!%7D%7Be%7D$ 四舍五入的結(jié)果。

????????不妨進(jìn)行程序驗(yàn)證。

????????結(jié)果如下：

????????其實(shí)這個(gè)公式只是個(gè)障眼法。由 $e%5Ex$ 的麥克勞林展開式，我們有：

$e%5Ex%20%3D%201%2B%5Cfrac%7Bx%7D%7B1!%7D%2B%5Cfrac%7Bx%5E2%7D%7B2!%7D%2B%E2%80%A6%2B%5Cfrac%7Bx%5En%7D%7Bn!%7D%2BR_%7Bn%2B1%7D(x)$

????????令 $x%3D-1$ ，得

$%5Cfrac%7B1%7D%7Be%7D%3D1-%5Cfrac%7B1%7D%7B1!%7D%2B%5Cfrac%7B1%7D%7B2!%7D%2B%E2%80%A6%2B(-1)%5En%5Cfrac%7B1%7D%7Bn!%7D%2BR_%7Bn%2B1%7D$

????????代入即得到

$D_%7Bn%7D%3D%5Cfrac%7Bn!%7D%7Be%7D-n!%5Ctimes%20R_%7Bn%2B1%7D%5Capprox%20%5Cfrac%7Bn!%7D%7Be%7D$

????????其中，根據(jù)拉格朗日余項(xiàng)知：

$R_n(x)%3D%5Cfrac%7Bf%5E%7Bn%2B1%7D(%5Ctheta)%7D%7B(n%2B1)!%7D(x-x_0)%5E%7Bn%2B1%7D%2C%5Ctheta%5Cin%20(x%2Cx_0)$

????????有：

$%5Cbegin%7Balign%7D%0A%5Csigma%20%26%3D-n!%5Ctimes%20%5Cfrac%7Be%5E%7B-%5Ctheta%7D%7D%7B(n%2B1)!%7D(-1)%5E%7Bn%2B1%7D%2C0%3C%5Ctheta%3C1%0A%5C%5C%26%3D%5Cfrac%7Be%5E%7B-%5Ctheta%7D%7D%7Bn%2B1%7D(-1)%5En%0A%5Cend%7Balign%7D$

$%5Cvert%20%5Csigma%20%5Cvert%20%3D%5Cfrac%7Be%5E%7B-%5Ctheta%7D%7D%7Bn%2B1%7D%3C%5Cfrac%7B1%7D%7B2%7D$

另一種采用容斥原理的證明

????????簡單證明如下：

????????設(shè) $A_k$ 為 $i_k%3Dk$ 的排列，則

???????? $%5Cbegin%7Balign%7D%0A%5Cvert%20%5Coverline%7BA_1%7D%5Ccap%20%5Coverline%7BA_2%7D%5Ccap%20%E2%80%A6%5Ccap%5Coverline%7BA_n%7D%20%5Cvert%20%26%3D%5Cvert%5Coverline%7BA_1%5Ccup%20A_1%5Ccup%E2%80%A6%5Ccup%20A_n%7D%5Cvert%0A%5C%5C%26%3Dn!-%5Cvert%20A_1%5Ccup%20A_1%5Ccup%E2%80%A6%5Ccup%20A_n%5Cvert%0A%5C%5C%26%3Dn!-(%5Csum_%7Bi%3D1%7D%5En%20%5Cvert%20A_i%20%5Cvert%20-%20%5Csum_%7B1%5Cleq%20i%3Cj%5Cleq%20n%7D%20%5Cvert%20A_iA_j%20%5Cvert%20%2B%5Csum_%7B1%5Cleq%20i%3Cj%3Ck%20%5Cleq%20n%7D%5Cvert%20A_iA_jA_k%20%5Cvert%2B%E2%80%A6)%0A%5C%5C%26%3Dn!-(C%5E1_n%20(n-1)!-C%5E2_n(n-2)!%2BC%5E3_n(n-3)!%2B%E2%80%A6)%0A%5C%5C%26%3Dn!-(n!-%5Cfrac%7Bn!%7D%7B2!%7D%2B%5Cfrac%7Bn!%7D%7B3!%7D%2B%E2%80%A6)%0A%5C%5C%26%3Dn!(%5Cfrac%7B1%7D%7B0!%7D-%5Cfrac%7B1%7D%7B1!%7D%2B%5Cfrac%7B1%7D%7B2!%7D-%5Cfrac%7B1%7D%7B3!%7D%2B%E2%80%A6)%0A%5C%5C%26%3Dn!%5Csum%5En_%7Bi%3D0%7D%5Cfrac%7B(-1)%5Ei%7D%7Bi!%7D%0A%5Cend%7Balign%7D$