錯位重排公式推導(dǎo)

基本公式：Dn =(n-1)×(Dn-2 +Dn-1)，其中D1=0,D2=1。

Dn表示n個數(shù)的錯位重排的方法數(shù)。

公式推導(dǎo)：若有n個人，n個座位，錯位重排。

(1)若n=1,1個人對應(yīng)1個座位，無法錯位，故D1=0;

(2)若n=2,2個人,2個座位，要實現(xiàn)錯位，只能是如下的方式，故D2=1;

(3)對于n個人，n個座位，要實現(xiàn)錯位，分步來操作：

第一步，先安排第1個的座位，第1個人選擇的是第i個座位，有(n-1)種坐法;

第二步，安排剩下(n-1)個人的座位，分類來操作：

第一類，若第i個人選擇第1個座位，有一種坐法，剩下的(n-2)個人，有(n-2)個座位錯位重排，有Dn-2種坐法，共有1×Dn-2= Dn-2種坐法。

第二類，若第i個人選擇不是第1個座位，即相當(dāng)于除了第1 個人外，其余的(n-1)個人，(n-1)個座位，錯位重排，共有Dn-1種坐法。

綜上所述，根據(jù)計數(shù)原理可得，共有(n-1)×(Dn-2+ Dn-1)種坐法，即Dn =(n-1)×(Dn-2 +Dn-1)，其中D1=0,D2=1。