05 計數的數 Numbers That Count

從計數問題中自然產生的數很重要，因此它們已經被研究得很深入了。這裏我將介紹二項式係數，以及卡特蘭、斐波那契和斯特林所發現的數。這些數被用於枚舉某些自然形成的集合。不過，還是讓我們從一些非常基本的數列開始吧。

三角形數、算術數列和幾何數列

因為它們在二項式係數裏還會出現，讓我們花點時間複習一下三角形數(triangular numbers)。這一數列的第n項，記為tn，定義為前n個正整數的和。它的值依賴於n，可以用下麵這個技巧來計算。我們將剛剛提到的和的形式寫作tn，接著以倒序再寫一遍：

tn=1+2+3+…+(n-2)+(n-1)+n.

tn=n+(n-1)+(n-2)+…+3+2+1.

例如，取a=1和b=2，則前n個奇數之和為n+n(n-1)=n+n2-n=n2，即n的平方。

如果把加法操作替換為乘法，算術數列就變成了幾何數列[1](geometric series)。算術數列中，相鄰兩項相差一個公差(common difference)，即我們的b。換句話說，從一項到下一項，我們要加上b。幾何數列中，我們還是取一個任意數a為首項，但是通過乘一個固定的數——稱為公比(common ratio)，來得到下一項。這個比值記為r。也就是說，典型的幾何數列具有a，ar，ar2，…的形式，其第n項為arn-1。就像算術數列一樣，幾何數列的前n項和也有一個公式[2]：

要想看出這一公式的正確性，最快的方法是將等式兩邊同乘(r-1)並將括號展開。等式左端我們有：

(ar+ar2+ar3+…+arn)-(a+ar+ar2+…+arn-1).

這一表達式可以裂項相消(telescope)，即一個括號中，幾乎每一項都可以與另一括號中的一項互相消去，僅剩下arn-a=a(rn-1)。由此可見我們的求和公式是正確的。舉個例子，設a=1，r=2，我們得到2的各次冪之和：

1+2+4+…+2n-1=2n-1.

第3章中歐幾裏得通過梅森素數導出了偶完全數，這裏的公式恰好可以讓你驗證他的方法。

階乘、排列和二項式係數

我們已經看到，第n個三角形數來自於對1到n之間所有的數求和。這個過程中，倘若將加法換成乘法，我們就得到了所謂的階乘。這一概念已經在第2章中出現過。

階乘常常現身於計數和概率問題中，比如打撲克時抽到特定牌的概率。因而它有單獨的記號：n的階乘記為n!=n×(n-1)×…×2×1。隨著n的增長，三角形數的大小增長得相當快，增長率差不多能達到n2的一半，然而階乘變大還要快得多——很快就能增大到百萬量級。比如10! = 3 628 800。階乘由感歎號來代表，恰恰提醒著我們那令人驚歎的增長速度!

在關於計數的問題——或稱為枚舉(enumerations)問題中，最特殊的一類數便是二項式係數(binomial coefficients)。之所以叫這個名字，是因為它們是將二項式(1+x)n展開後x的各階冪次前的係數。二項式係數C(n，r)代表了我們從n個元素中挑選出r個元素一共有多少種不同的方法。例如，C(4，2)=6，因為從4個元素中取一對有6種方法(不在乎這兩者的次序)。再具體些，假設我們有4位兒童：A，B，C和D。那麽有6種方法從中選出1對：AB，AC，AD，BC，BD和CD。

這個用階乘計算二項式係數的公式確實提供了一種簡便的代數方法，使我們能夠證明這些係數的許多特殊性質。然而，如果我們用第二種方法來導出這些整數，這些性質的演化會更清楚。這種方法基於算術三角形[3](Arithmetic triangle)(如圖2)，又稱為帕斯卡三角形(Pascal’s triangle)，以紀念17世紀法國數學家和哲學家布萊士·帕斯卡(Blaise Pascal)。算術三角形在過去的1000年裏被波斯、印度和中國數學家各自發現。它出現在1303年朱世傑[4]所著《四元玉鑒》的封麵上。

算術三角形的結構能夠給出正確的答案，這一點不難理解。每一行都由上一行所產生。我們可以輕鬆看出前三行是正確的：例如，第三行中央的2告訴我們從一對人當中選出一位總共有兩種方法。頂端的1表明從空集中選出0個元素就隻有一種方法。實際上，從任意集合中選出0個元素的方法都是一種，這就是為什麽每行都從1開始。我們重點看剛才的例子——共有21 = 15+6種方法從7人中選出5人。這21種選法自然地分成兩類。第一類，有15種方法從前6人中選出4人，我們可以再加上第七位湊成5人組。或者如果我們不選第七位，則要從前6人中一次選出5人，共有6種方法。這個例子告訴我們一行是如何生成下一行的：每個元素都是上麵兩數之和，按照這一模式從上到下建立起整個三角形。這個規則可用符號表示成以下形式：

C(n，r) =C(n-1，r)+C(n-1，r-1) .

算術三角形蘊含著豐富的規律。比如：將每行的數分別相加可以得到倍增數列1， 2， 4， 8， 16，32，…，即2的各次冪。以1， 8， 28， 56，…這行為例，我們是在將從8個元素中選出0個、1個、2個、3個……元素的方法個數相加，最後得到的是從8個元素中一次選取任意個數的元素共有多少種方法。這一數字為28，因為一般一個有n個元素的集合擁有2n個子集。

上麵這一事實也可以直接推出，原因是一個n個元素集合的任意一個子集可以使用長度為n的二進製字符串來識別。方法如下：我們考慮一個集合，比如{a1，a2，…，an}，則一個長度為n的二進製字符串定義了它的一個子集，因為字符串中的每個1表示相應的元素ai存在於我們的子集中。例如，假設n=4，字符串0111和0000分別代表{a2，a3，a4}和空集。由於二進製字符串的每個位置都有兩種取值選擇，因此共有2n個這樣的字符串，一個n元素集合便含有2n個子集。

卡特蘭數

這種數有種最簡單的圖形表達，是用n段上斜線段和n段下斜線段能畫出多少組不同的“山脈”(見圖3)。

每種不同的山脈構型都對應一組有意義的括號，因此將n對括號有意義地排列起來的方法個數，恰好是第n個卡特蘭數。例如，(())()和((()))是有意義的括號方法，但())(()不是：有意義是指從左向右數時，左括號的個數從不小於右括號的個數。這對應於山脈始終位於地麵上方這一自然條件。比方說，圖3中第一個和最後一個山脈的構型分別對應於()(())和()()()這兩種括號排列。

第n個卡特蘭數還代表將n+2邊的正多邊形被互不相交的對角線分成三角形的方法個數。沿著這一思路，卡特蘭數還有其他解讀方法。正如二項式係數，也有公式聯係了卡特蘭數和更小的卡特蘭數，這使對它們的計算變得很簡便。

斐波那契數列

恐怕沒有第二個數列像斐波那契數列(Fibonacci sequence)那樣使普羅大眾著迷了，它是如下的數列：

1， 1， 2， 3， 5， 8， 13， 21， 34， 55， 89，144， 233， 377， 610，…

在起始的兩個數之後，每個數都是其之前兩數之和。在這一點上，二項式係數與其有相似之處，因為那裏每一項也是之前兩數之和。但是斐波那契數列的組成方式更簡單：

fn=fn-1+fn-2

這裏fn表示第n個斐波那契數，並且我們規定f1=f2=1。我們將這種用先行項來定義當前項的公式叫作遞歸(recursion)或遞推關係(recurrence relation)。

這一數列是從哪裏來的呢？它最先是由比薩的萊昂納多(Leonardo of Pisa)——更有名的稱呼是斐波那契——在他著名的兔子問題中引入的。一隻雌兔出生兩個月後達到生育年齡，並在這之後的每個月生下一隻雌兔。那麽每個月初雌兔的總數由斐波那契數列給出。第一個和第二個月初當然隻有一隻兔子。第三個月初雌兔生下一隻雌兔，因而我們有2隻雌兔。到了下個月，它又生下一隻，於是共有3隻雌兔。再下個月，雌兔總數達到5隻，因為雌兔和它的大女兒都能夠生育。一般地，在這之後的每個月初，新生雌兔的數量等於兩個月前雌兔的總數，因為此刻隻有它們處於生育年齡。於是，每月初雌兔總數等於上月雌兔的數量與上上個月雌兔數量之和(斐波那契的雌兔是永生的)。因而斐波那契數列的產生方式完全符合他的雌兔繁殖的方式。

盡管真實世界的兔子並不是以這種異想天開的方式來繁殖的，斐波那契數列依然換著麵孔出現在自然界中，包括植物的生長。我們對這一現象的原因已經有了透徹的理解，這與該數列的更微妙的性質有關，即黃金分割比(Golden Ratio)。我們這就來談談它。

最簡單的數列類型便是我們在本章第一部分介紹的算術和幾何數列。雖然斐波那契數列並非它們中的一種，它卻與後者有驚人的聯係。當計算斐波那契數列鄰項之差並將它們也排成一列時，我們得到0， 1， 1， 2， 3， 5， 8， 13，…，於是又得到了一組斐波那契數列，隻是這次是從0開始的!其中的原因正是這個數列形成的方式：兩個相鄰斐波那契數之差恰好等於它倆之前的那個數，(想要代數地證明這一點，可以將上麵的斐波那契遞推公式兩邊同時減去fn-1)所以它不是算術數列。它也不是幾何數列，因為相鄰兩項斐波那契數之比並不是常數。但我們觀察鄰項之比的時候，它似乎在一個極限值附近穩定下來，而且這個比值很快就趨於穩定了。讓我們將每個斐波那契數除以它前一個數：

這個逐漸顯露的神秘的數，1.6180…，到底是什麽呢？這個數τ被稱為黃金分割比，它也會出現在一些幾何問題中，而這些問題看起來跟斐波那契的兔子相差十萬八千裏。例如，τ是正五邊形的對角線與邊長之比(如圖4)。任意兩條對角線的交點將它們各自分成兩段，這兩段長度之比也是τ∶1。一對相交的邊和一對相交的對角線構成一個菱形(一個“正方的”平行四邊形)，即如圖4中的ABCD。所有對角線的交點又組成了一個小的倒立的五邊形。

另一種獲得τ的值的方法是通過它的連分數。連分數能將τ和斐波那契數列直接聯係起來，我們將在第7章中探索這一方法。

不斷數下去，斐波那契數列看起來就像一個幾何數列，它的公比是黃金分割比。正是由於這一性質和它簡單的構成規則，斐波那契數列無處不在。

斯特林數和貝爾數

像二項式係數一樣，斯特林數[6](Stirling numbers)經常在計數問題中出現。它依賴於兩個變量，n和r。斯特林數S(n，r)是將一個有n個元素的集合分割成r個子塊的方法的個數，每一塊都非空，且無關於塊的次序和塊內部元素的順序。(嚴格地說這些稱為第二類斯特林數。第一類斯特林數與此相關，但代表了非常不同的東西，即將n個物體排列成r個環的方法總數。)例如，含有元素a，b，c的集合隻能以一種方式分成三塊：{a}，{b}，{c}；或是以三種方式分成兩塊，分別是{a，b}，{c}和{a}，{b，c}和{a，c}，{b}；或是以唯一一種方式分成一塊：{a，b，c}。因此S(3，1) = 1，S(3，2) = 3以及S(3，3) = 1。由於將一個n元素集合分割為一塊或是n塊都隻有一種方式，因此S(n，1) = 1 = S(n，n)。如果我們仿照帕斯卡三角形，也將斯特林數放置在一個三角形中，將得到如圖5所示的陣列。現在我們來解釋這個三角形是如何產生的。

這些數也滿足了一個遞推關係，意味著每個數都聯係到陣列中之前的數。就像二項式係數一樣，每個斯特林數都可以由它上方的兩個數生成，但這次不再是簡單的加和。另外，我們看到二項式係數生成的算術三角形具有行對稱性，這在斯特林三角形中不再成立。如S(5，2) = 15，然而S(5，4) = 10。不過遞推規則依然簡單。比如，90這一項等於15+3×25。這其實揭示了一般情形：要找到三角形中的某個數，取其上方的兩個數，將第二個數乘以當前未知數所在的(自身行內的)列數，再加上第一個數。(不同於算術三角形，這次列數從1開始計。)用類似的方法，S(5，4) = 10 = 6+4×1。以上計算規則中隻有加粗的部分跟算術三角形的情形不同，但這足以使對斯特林數的研究難度大大超過二項式係數。舉個例子，我們推導出了一個簡單的、基於階乘的顯式公式，可以計算所有二項式係數。類似地，第n個斐波那契數也有一個基於黃金分割比的冪次的通項公式[7]，但是對於斯特林數，還沒有這類公式為人所掌握。

這個遞推關係並不難解釋。我們的推理類似於二項式係數的遞歸，給出的遞推式也與那裏的形式一致，隻是相差了一個乘數。為了將一個n元素集合分成r個非空子塊，我們可以采取兩種不同的方法。我們可以取集合的前n-1個元素，並將其分成r-1個非空塊，共有S(n-1，r-1)種方法，最後一個元素將構成第r個塊。或者，我們可以將集合的前n-1個元素分成r個非空塊，這有S(n-1，r)種方法，接下來再決定將最後一個元素放進r個塊的哪一個，這就需要用r乘以目前的方法數。因此有S(n，r) =S(n-1，r-1)+rS(n-1，r)，這裏n= 2，3，… .

用這個遞歸公式，我們就可以基於上一行計算每一行斯特林三角形的值。如，設n = 7和r = 5我們得到：

S(7， 5) = S(6， 4)+5S(6， 5) = 65+5×15 = 65+75 = 140 .

可以用定義直接計算S(n， 2)和S(n， n-1)。將一個n元素集合分割成兩個子集，這一過程可以由一個長度為n的二進製字符串來描述，其中1表示相應位置的元素在第一個子集中，而0則表示該元素屬於第二個子集(類似於我們證明n元素集合的子集個數是2n)。於是，有2n個這樣的有序子集對。但是因為分割與塊的次序無關，我們將這個數目除以2，便可得到將n元素集合分成兩個子集的方法個數，即2n-1。最後，還需要從中減掉1，去除掉其中一個子集為空的情況。因此，S(n， 2) = 2n-1-1。對照圖5，你可以檢查看看，這個公式給出了右上到左下方向第二對角線上的數，即1， 3， 7， 15，31， 63，…。

算術三角形中任意一行的和給出了對應2的冪次——一個集合的子集數量。類似地，斯特林三角形的第n行的和給出的是將n個物體分成任意個數子塊的方法總數，這被稱作第n個貝爾數(Bell number)。分拆數

另一方麵，如果待分割集合中的n個物體是一模一樣、無法區分開的，將整個集合分拆為子塊的方法數就變得小得多了。這稱為第n個分拆數[8](partition number)。每一個特定的分拆對應於將n寫成一些不考慮次序的正整數的和。例如，1+1+1+1+1是5的一個分拆，還有6種其他分拆，因為我們還可以將5表示成1+1+1+2， 1+2+2，1+1+3， 2+3， 1+4，或直接就是5。因此第5個分拆數為7(對比第5個貝爾數，後者可由斯特林三角形計算，即1+15+25+10+1 = 52)。沒有簡單的精確公式可以計算第n個分拆數，但有一個複雜的公式。該公式基於印度天才數學家斯裏尼瓦瑟·拉馬努金(Srinivasa Ramanujan)給出的一個優美近似。

分拆具有一種簡單的對稱性，那就是將n分拆為m個數的方案數等於將n分拆後所得數中最大值恰為m的方法個數。要想看到這一結論的正確性，一種方法是通過分拆的費勒斯圖像(Ferrar’s graph)——或稱楊表[9](Young diagram)。這個圖表並不神秘，無非是將分拆表示成元素逐行減少的點陣。

在圖6的例子中，我們把17拆分為5+4+4+2+1+1。注意到從左向右各列也以降序排布。如果我們繞著左上到右下的對角線翻轉整個點陣，我們就得到圖示的第二個費勒斯圖像，這個圖像可以闡釋為分拆17 = 6+4+3+3+1。對第二個圖像做同樣的翻轉，又會回到第一個圖像。我們稱這兩種分拆互為共軛(dual)。這一對稱性表明兩種類型的分拆方案數是相等的：一種是m為結果中最大的數的分拆(即頂端行有m個點)，它的共軛是一個有m行的分拆，即拆分為m個數。例如，將17拆分為6個數的方案數，等於將17拆分使得最大數為6的方案數。

冰雹數

盡管不是一種計數工具，冰雹數(hailstone numbers)仍然耐人尋味，因為它也是被遞推定義的，不過這個數列更像我們在第3章中遇到的真因數和數列。以下問題有好幾個名字，考拉茲算法(Collatz algorithm)、敘拉古問題(Syracuse problem)，或者有時就叫3n+1問題[10]。它基於一個簡單的觀察，即從任意數n開始，經過以下步驟似乎最終總是得到1：若n是偶數，將其除以2；若n是奇數，用3n+1代替它。例如，從n = 7開始，我們按照這些規則得到以下數列：

7→22→11→34→17→52→26→13→40

→20→10→5→16→8→4→2→1.

於是這一猜想對n = 7成立。實際上該猜想已經被證實對於直到一萬億以上的某個數都是正確的[11]。但是如果你亂動了規則，事情就大不一樣了。比如，用3n-1代替3n+1會導致一個循環：

7→20→10→5→14→7→….

考拉茲算法產生的數列類似於冰雹，在很長一段時間內它們的取值大起大落，但最終似乎總會降落到地麵。在前1000個正整數中，有超過350個數上升到最大高度9232，而後則迅速跌落到1。一旦你遇到2的冪次，就會最終得到1，因為之後這些數不會經曆任何爬升，隻能一路衰減到底。

所有這些奇妙的特性都可以在基於冰雹數列的圖像中被發現，這讓人不禁聯想起數學和物理中出現的其他混沌現象。在搜索引擎中輸入“冰雹數”，你會找到一大堆信息，這些信息往往看上去奇妙異常，有時候是猜想性質的，但通常不能給出一個確定的結論。

[1]　即等比數列。

[2]　該公式中r≠1。

[3]　即楊輝三角形。

[4]　朱世傑，字漢卿，號鬆庭，元代數學家和教育家。

[5]　尤金·查理·卡特蘭(Eugène Charles Catalan)，法國和比利時數學家。

[6]　詹姆斯·斯特林(James Stirling)，蘇格蘭數學家。埃裏克·坦普爾·貝爾(Eric Temple Bell)，英國數學家、科幻小說家。

[7]　如果可以將數列{an}的第n項用一個含參數n的式子表示出來，則稱該式為該數列的通項公式。

[8]　又稱拆分數或分割數。

[9]　又稱楊氏矩陣。

[10]　又名考拉茲猜想、敘拉古猜想、3n+1猜想、奇偶歸一猜想、冰雹猜想、角穀猜想、哈塞猜想、烏拉姆猜想。

[11]　世界各地的數學愛好者們利用分布式計算，不斷地提高這個極限。已知的猜想成立的最大整數似乎已超過1020(一億億的一百倍)，而仍未找到反例。有興趣的讀者可以參考以下網站：https://boinc.thesonntags.com/collatz/， http://www.ericr.nl/wondrous/。