f(n)=(n-1)*(f(n-2)+f(n-1));

顏書先生《“裝錯(cuò)信封問(wèn)題”的數(shù)學(xué)模型與求解》一文（見(jiàn)《數(shù)學(xué)通報(bào)》 2000 年第 6 期 p.35 ），給出了該經(jīng)典問(wèn)題的一個(gè)模型和求解公式：

編號(hào)為 1 ， 2 ，……， n 的 n 個(gè)元素排成一列，若每個(gè)元素所處位置的序號(hào)都與它的編號(hào)不同，則稱這個(gè)排列為 n 個(gè)不同元素的一個(gè)錯(cuò)排。記 n 個(gè)不同元素的錯(cuò)排總數(shù)為 f(n) ，則

f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]（ 1 ）

本文從另一角度對(duì)這個(gè)問(wèn)題進(jìn)行一點(diǎn)討論。

1. 一個(gè)簡(jiǎn)單的遞推公式

n 個(gè)不同元素的一個(gè)錯(cuò)排可由下述兩個(gè)步驟完成：

第一步，“錯(cuò)排” 1 號(hào)元素（將 1 號(hào)元素排在第 2 至第 n 個(gè)位置之一），有 n - 1 種方法。

第二步，“錯(cuò)排”其余 n - 1 個(gè)元素，按如下順序進(jìn)行。視第一步的結(jié)果，若 1 號(hào)元素落在第 k 個(gè)位置，第二步就先把 k 號(hào)元素“錯(cuò)排”好， k 號(hào)元素的不同排法將導(dǎo)致兩類不同的情況發(fā)生：（ 1 ） k 號(hào)元素排在第 1 個(gè)位置，留下的 n - 2 個(gè)元素在與它們的編號(hào)集相等的位置集上“錯(cuò)排”，有 f(n -2) 種方法；（ 2 ） k 號(hào)元素不排第 1 個(gè)位置，這時(shí)可將第 1 個(gè)位置“看成”第 k 個(gè)位置，于是形成（包括 k 號(hào)元素在內(nèi)的） n - 1 個(gè)元素的“錯(cuò)排”，有 f(n - 1) 種方法。據(jù)加法原理，完成第二步共有 f(n - 2)+f(n - 1) 種方法。

根據(jù)乘法原理， n 個(gè)不同元素的錯(cuò)排種數(shù)

f(n) = (n-1)[f(n-2)+f(n-1)] (n>2) 。 （ 2 ）

Ps: HDOJ-1645

#include<iostream>  #include<string.h>  #include<math.h>  #include<queue>  using namespace std;  int n,i;  long long s[27];  int main()  {       s[0]=0; s[1]=0; s[2]=1;      for (i=3;i<=20;i++)         s[i]=(i-1)*(s[i-1]+s[i-2]);           while (cin>>n)         cout<<s[n]<<endl;        return 0;  }