錯位排列問題探究：從信封到臺階的數(shù)學(xué)之旅

問題：五封標號為1～5的信放入五個編號為1～5的信封中，如果信的編號與信封的編號不同，有多少種不同的放法？

更廣泛的問題是：如果有n封標號為1～n的信，要放入n個編號為1～n的信封中，且信的編號與信封的編號不同，有多少種不同的放法。數(shù)學(xué)家歐拉研究過這個問題，使用了構(gòu)造遞推式的方法來解決。

設(shè)A、B、C、...代表n個信封，a、b、c、... 代表n份寫的信。如果a錯誤地放入了B中，考慮在這種情況下有多少種錯誤的放法。我們可以分為兩類：第一類是b放入A中；第二類是b不放入A中。

對于第一類情況，剩下的n-2封信的錯誤放置與A和B無關(guān)。設(shè)n封信錯誤放置的總方法數(shù)記為f(n)，則在第一類情況下，錯誤的放置方式有f(n-2)種。

對于第二類情況，這相當于n-1封信的錯誤放置問題，因此錯誤放置的方式有f(n-1)種。這樣，在a放入B中的情況下，總共有f(n-2)+f(n-1)種錯誤的放置方式。由于a可以放入B也可以放入C、D...，所以n封信的錯誤放置方式可以表示為：

接下來，我們要根據(jù)這個遞推式求出通項公式。已知f(2)=1, f(1)=0，則

可以看到該通項公式是一個級數(shù)形式。對于冪級數(shù)了解較深的人會知道，當n趨近于無窮大時，括號里面的級數(shù)實際上是e的倒數(shù)。

現(xiàn)在我們來考慮一個看似簡單的問題：一個樓梯有10個臺階，如果規(guī)定每一步可以上一個或者兩個臺階，有多少種不同的走法？

很多同學(xué)看到這個問題，通常會根據(jù)登上兩個臺階的次數(shù)來進行分類，共有以下幾種情況：全部用上1個臺階的方式、1次用上2個臺階的方式、2次用上2個臺階的方式、3次用上2個臺階的方式、4次用上2個臺階的方式、5次用上2個臺階的方式。根據(jù)這個分類：

推廣到n個臺階，我們可以得到以下表達式：

這里的組合數(shù)是廣義的組合數(shù)。例如：

可以看到，這里涉及到無窮級數(shù)。如果我們換一種方法來解決這個問題，可以找到答案的另一種表達方式，并探索其中是否存在遞推關(guān)系。對于登上10個臺階的情況，我們可以這樣思考：第一類情況是先登上9個臺階，最后再用上1個臺階的方式完成；第二類情況是先登上8個臺階，最后用上2個臺階的方式完成。

設(shè)f(n)表示登上n個臺階的走法總數(shù)，那么就有以下遞推式：

而且已知f(1)=1, f(2)=2。這與斐波那契數(shù)列非常相似，只不過這里的第1項是斐波那契數(shù)列的第二項。根據(jù)斐波那契數(shù)列的通項公式，我們可以寫出：

這樣我們就得到了一個與前面使用級數(shù)形式不同的通項公式。在這個問題中，我們雖然使用了遞推式，但沒有求出一個可以用n的初等函數(shù)表示的式子。

因此，有些級數(shù)可能并不對應(yīng)和函數(shù)。這個問題還可以進一步推廣，例如：如果規(guī)定每一步可以上一個臺階或三個臺階，有多少種不同的走法？此時遞推式變?yōu)閒(n)=f(n-1)+f(n-3)（n>3），它是一個線性遞推式，也可以求出通項公式。對此感興趣的讀者可以自行進行推導(dǎo)。

(責(zé)任編輯：佚名)