問題：五封標(biāo)號(hào)為1～5的信放入五個(gè)編號(hào)為1～5的信封中，如果信的編號(hào)與信封的編號(hào)不同，有多少種不同的放法？

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

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

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

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

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

可以看到該通項(xiàng)公式是一個(gè)級(jí)數(shù)形式。對(duì)于冪級(jí)數(shù)了解較深的人會(huì)知道，當(dāng)n趨近于無窮大時(shí)，括號(hào)里面的級(jí)數(shù)實(shí)際上是e的倒數(shù)。

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

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

推廣到n個(gè)臺(tái)階，我們可以得到以下表達(dá)式：

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

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

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

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

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

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

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