問題

高中選修2-3有這么一道組合題：

0,1,2,3,4,5這6個數(shù)中任選4個數(shù)組成一個四位數(shù)，如果這個數(shù)的任意一位上的數(shù)字都比它右邊一位上的數(shù)字大，那么稱這個數(shù)為“漸降數(shù)”。問：一共可組成多少個漸降數(shù)？

關(guān)于這個問題的解答，懂得組合的都很容易做出來：其實(shí)就是6個數(shù)中選4個數(shù)，共有多少種選法，也就是：

很容易得到對于n個數(shù)中的m位漸降數(shù)，其個數(shù)是：

開辟新思路

似乎，我們可以換一個角度來看看這個問題。0,1,2,3,4,5中要分別選出一個數(shù)作為個、十、百、千位上的數(shù)字，因?yàn)橐鬂u降，所以千位最大取5的時候，百位最大只能取4，十位最大取3，個位最大取2，同樣的，個位最小可以取0，因此十位最小取1，百位最小取2，千位最小取3，由此可列出下表

分析這個表格：個位取0的時候十位任取都能比個位大，個位取1的時候十位只能取2和3，個位取2的時候十位只能取3。對于十位，十位取1的時候百位任取，十位取2的時候百位取3和4，以此類推，便發(fā)現(xiàn)一個規(guī)律：一個位數(shù)上的數(shù)字，若取第一行，則下一位有3種取法，若取第2行，下一位有2種取法，若取第三行，下一位有1種取法。這有點(diǎn)別扭，不妨倒過來看，由下至上分別是1、2、3行，于是就有：若取第n行，則下一位有n種取法。畫出以下樹圖

個位中，數(shù)字“0”向下引出3條線，十位中數(shù)字“1”向下引出3條線，所以個位中的“0”與十位中的“1”可看作同種性質(zhì)，或者說同樣地位，如果把向下引出n條線的節(jié)點(diǎn)上的數(shù)字改成n，那這個圖就相當(dāng)明了了

最后一行不是0，而是有不同的數(shù)字，原因是這個圖還沒完，可以這樣無限地畫下去。但是從這里已經(jīng)可以看出這種遞歸的模式了。

遞歸模式

如果有這么一個序列(a?a?a?……an)（各項(xiàng)不是相乘的意思，而是這種排列順序），對它進(jìn)行一個遞歸操作：f(an)→a?a?a?……an，也就是用a?a?a?……an替換原來的an，例如f(a?a?a?)=a?a?a?a?a?a?，記這個操作為Z，其中對n項(xiàng)序列進(jìn)行m次這樣的操作，記為

于是有：

對于m=-1時結(jié)果為0，我更傾向于把它看成“起始點(diǎn)”，上文的兩張樹圖，其實(shí)第一行每個數(shù)還應(yīng)該往上連線匯聚成一點(diǎn)，有個“起始點(diǎn)”才叫完整，不是嗎？而起始點(diǎn)的個數(shù)始終為1，這是一個很重要的性質(zhì)，下文將會用到。

遞歸模式f(an)→a?a?a?……an在探討漸降數(shù)問題的時候有一個說法，就是“若取第n行，則下一位有n種取法”，換做這個模式，可翻譯成“若取下標(biāo)為n的項(xiàng)，則它將變成n個項(xiàng)”，而它不是變成其他的比如n個an或者n個a?等等，是因?yàn)檫@個模式有一個隱含的規(guī)律，就是所謂的“下一位”。每一個位置的每種選法都決定下一個位置的選擇范圍，比如個位的“1”決定了十位是“2”或“3”，“2”與“3”又對百位有不同的決定，倘若下標(biāo)為n的項(xiàng)是變成n個an，就意味著下一位對下下一位的決定都相同（都是an來決定），這不符合“漸降數(shù)中的每一種選擇對下一位的決定都不同”。那么，如果要形成n項(xiàng)，每項(xiàng)還不同，但都滿足“若取下標(biāo)為n的項(xiàng)，則它將變成n個項(xiàng)”，只能是f(an)→a?a?a?……an這個模式了。

為了把逼格拉起來，我起個名字吧，叫做“順次遞歸”，意思是順著當(dāng)前項(xiàng)的位次進(jìn)行遞歸。

求項(xiàng)數(shù)

當(dāng)然了，對于一個沒有固定數(shù)值，甚至可以不用數(shù)字組成的序列（a?a?a?可以分別是紅黃綠什么的），最大的意義就是它的項(xiàng)數(shù)了，我們用符號S來記，用“代”來表示經(jīng)過遞歸后的序列，起始點(diǎn)為第0代，初始序列是第1代，經(jīng)過一次遞歸之后的序列是第2代，以此類推，“代”數(shù)為m，初始序列項(xiàng)數(shù)為n，則n項(xiàng)序列的第m代項(xiàng)數(shù)為

因?yàn)榻?jīng)過m次遞歸之后是m+1代，所以

據(jù)上文又知道上標(biāo)為-1的時候，Z=0，也就是只有一項(xiàng)，因此m=0時S為1，同時也印證了“起始點(diǎn)個數(shù)始終為1”這句話。而“若取下標(biāo)為n的項(xiàng)，則它將變成n個項(xiàng)”又告訴我們，對第2代序列進(jìn)行求項(xiàng)數(shù)，就是對第1代下標(biāo)進(jìn)行求和，同理，對第m+1代序列進(jìn)行求項(xiàng)數(shù)，就是對第m代下標(biāo)進(jìn)行求和。接下來分析一下對第m代下標(biāo)進(jìn)行求和具體是什么

這是n=4的序列經(jīng)過2次遞歸得到的3代序列，留意紅色框框部分，是由第1代的第3項(xiàng)經(jīng)過遞歸得到的。其中第2代的紅色框框部分包含了第1代紅框前的部分（就是a?a?），而第3代紅框部分也包含了第2代紅框前的部分，這很好解釋：已知第2代紅框部分會包含第1代紅框前部分，那么第2代紅框部分向下形成的第3代的紅框部分也自然包含了第1代紅框前部分向下形成的部分，也就是第2代的紅框前部分，若第n代紅框部分包含第n-1代紅框前部分，則第n代紅框部分向下形成的第n+1代的紅框部分也自然包含了第n-1代紅框前部分向下形成的部分，也就是第n代的紅框前部分，這是數(shù)學(xué)歸納法。紅框部分是我在初代（第1代）序列中選的某一項(xiàng)進(jìn)行遞歸得到的，忽略紅框后面的所有項(xiàng)，可以看出，紅框向下形成的新紅框內(nèi)的項(xiàng)數(shù)，就是紅框及其前面部分的所有項(xiàng)數(shù)，因此對第m+1代序列求項(xiàng)數(shù)，就是求其所有“紅框”內(nèi)的項(xiàng)數(shù)和，而“紅框”內(nèi)的項(xiàng)數(shù)就是第m代序列從頭一直到紅框最后一項(xiàng)的項(xiàng)數(shù)，正好紅框取的是初代序列的某一項(xiàng)。根據(jù)f(an)→a?a?a?……an可知紅框內(nèi)最后一項(xiàng)是初代序列選中的那一項(xiàng)，所以在第m代序列中從頭一直到紅框內(nèi)最后一項(xiàng)求項(xiàng)數(shù)，就是求初代序列形成的第m代的項(xiàng)數(shù)，于是我們有

回到問題，引出公式

算了半天的項(xiàng)數(shù)，這……和漸降數(shù)有什么關(guān)系呢？難道跑題了？

不，再認(rèn)真看看，漸降數(shù)的每位組成滿足以上遞歸，要求漸降數(shù)的個數(shù)，不正是要求經(jīng)過多次遞歸之后的序列的項(xiàng)數(shù)嗎？假設(shè)一共有n個數(shù)，求m位漸降數(shù)的個數(shù)，那么根據(jù)之前列的表格，每位上都有n-m+1種選擇的可能，并且對下一位的決定都滿足順次遞歸，也就是說漸降數(shù)的個數(shù)就是對n-m+1項(xiàng)序列的第m代進(jìn)行求項(xiàng)數(shù)

整理成一般的公式，n項(xiàng)序列的第m代項(xiàng)數(shù)的表達(dá)式就是

簡單的推廣與應(yīng)用

對于這個定理

我想到把它一項(xiàng)一項(xiàng)列出來，第一行是上標(biāo)為0，第二行是上標(biāo)為1，等等

只列了部分，但是已經(jīng)可以看出什么端倪了，這就是楊輝三角

把右邊的一列1看成是圖1中的第一行，左邊一列1看成圖1中左邊的第一列，那么求楊輝三角第x行第y個數(shù)，就是求圖1中第x-y+1行第y個數(shù)，也就是y項(xiàng)序列的第x-y代項(xiàng)數(shù)（第一行是第0代，因此要行數(shù)-1），而由公式得知

所以楊輝三角第x行第y個數(shù)就是

對此，會排列組合的人來說不難計算吧。

考慮下面這一個問題：一條路上有10個紅綠燈，倘若遇到的是紅燈，則下一個有可能遇到紅黃綠三種，倘若遇到黃燈，下一個有可能遇到黃綠兩種，倘若遇到綠燈，下一個也必定是綠燈，問一共有多少種情況。

根據(jù)以上遞歸模式，可把紅的看作a?，黃燈看作a?，綠燈看作a?，且它們均滿足f(an)→a?a?a?……an，因此初代序列為(a?a?a?)=(綠黃紅)。共有10個紅綠燈，由公式可知第10代的項(xiàng)數(shù)是

計算12！/2！10！=66，共有66種情況

尾聲

本人僅為高一學(xué)生，以上是做作業(yè)之余對作業(yè)題目的多角度想法與剖析，用來打發(fā)閑暇時間的小興趣罷了，出現(xiàn)很多不嚴(yán)謹(jǐn)甚至錯誤的地方也不足為奇，但請多指正。以上為個人原創(chuàng)，如有雷同純屬巧合，若數(shù)學(xué)愛好者們對這個問題有更深刻的看法或者推廣，歡迎在評論區(qū)留下腳印。這是我第一次寫專欄，也僅是瞎做，還請多多指教。