本書的每一個(gè)證明最終都可以歸納為一個(gè)計(jì)數(shù)問(wèn)題, 通常用兩種不同的方法數(shù)數(shù). 計(jì)數(shù)會(huì)給出美麗, 通�；�本, 且簡(jiǎn)潔的證明. 雖然它不一定是最簡(jiǎn)單的方法, 但它卻提供了另一種理解數(shù)學(xué)事實(shí)的途徑. 對(duì)于一個(gè)組合數(shù)學(xué)
研究者, 這種證明方法才是唯一正確的. 我們把這本書獻(xiàn)給各位讀者, 作為羅杰􀅰 內(nèi)爾森的著作 «數(shù)學(xué)寫真集Ⅰ ———無(wú)需語(yǔ)言的證明» (機(jī)械工業(yè)出版社出版) 相應(yīng)的計(jì)數(shù)版本.
為什么計(jì)數(shù)?
作為人類, 我們?cè)诤苄〉臅r(shí)候就學(xué)會(huì)了如何數(shù)數(shù). 一般一個(gè)兩歲的孩子就會(huì)自豪地?cái)?shù)到 10, 以得到父母的稱贊. 雖然很多成年人說(shuō)自己數(shù)學(xué)很差,但卻沒(méi)有人承認(rèn)自己不會(huì)計(jì)數(shù). 計(jì)數(shù)是我們最早用到的工具之一. 物理學(xué)家恩斯特􀅰 馬赫甚至說(shuō): “在數(shù)學(xué)中不存在不能通過(guò)直接計(jì)算解決的問(wèn)題.”[36]
組合證明可以尤其強(qiáng)大. 至今, 我 (A􀆰 T􀆰 B􀆰 ) 仍記得當(dāng)我還是一名大
一新生時(shí), 第一次接觸組合證明時(shí)的情形. 我的教授通過(guò) ( x + y)n =
(x + y)(x + y)􀆺(x + y)
üïïïïïýïïïïïþ
n次 證明了二項(xiàng)式定理
(x + y)n = ∑
n
k = 0
(nk )xkyn - k.
在證明定理的過(guò)程中, 他問(wèn)大家有多少種方法可以得到 xkyn - k項(xiàng). 忽然一切都清楚了. 是的, 我之前見過(guò)很多種二項(xiàng)式定理的證明, 但他們看起來(lái)十分笨拙, 我那時(shí)常想一個(gè)思維正常的人是怎么創(chuàng)造出這么一個(gè)結(jié)果的. 但現(xiàn)
在, 這看起來(lái)非常自然. 我永遠(yuǎn)也不會(huì)忘記這個(gè)結(jié)果.
數(shù)什么?
我們選擇了我們最喜歡的, 使用數(shù)學(xué)中常出現(xiàn)數(shù)字的 (二項(xiàng)式系數(shù)､ 斐波那契數(shù)､ 斯特林?jǐn)?shù)等) 恒等式, 并且選用了優(yōu)雅的計(jì)數(shù)證明. 在一個(gè)典型的恒等式中, 我們提出一個(gè)計(jì)數(shù)問(wèn)題, 分別用兩種不同的方法回答. 一種方法的答案是恒等式的左邊, 另一種方法是恒等式右邊. 由于兩個(gè)答案解決的
是同一個(gè)計(jì)數(shù)問(wèn)題, 所以它們必須相等. 恒等式可以看作是從兩個(gè)不同的角度解決的計(jì)數(shù)問(wèn)題. 我們用恒等式 nk = 0(nk ) = 2n 來(lái)舉例說(shuō)明本書的證明結(jié)構(gòu). 計(jì)算 (nk )不需
要使用公式 n􀆱k􀆱 (n - k) 􀆱 . 取而代之, 我們用 (nk )表示由 n 個(gè)元素組成的集合中任意選取 k 個(gè)元素組成的子集的個(gè)數(shù), 或是更形象地, 其表示從有 n 個(gè)人的班級(jí)中選出 k 名學(xué)生組成一個(gè)班委會(huì)的方法數(shù).
問(wèn)題 從有 n 個(gè)人的班級(jí)中組成一個(gè)班委會(huì)有多少種選法?
答 1 由 0 個(gè)學(xué)生組成的班委會(huì)為 (0n )個(gè), 由 1 個(gè)學(xué)生組成的班委會(huì)為(1n )個(gè), 總而言之, 由 k 個(gè)學(xué)生組成的班委會(huì)的種類是 (nk )種. 因此, 班委會(huì)的種類的總和為 ∑
n
k = 0
(nk )種.
答 2 為了組建一個(gè)任意學(xué)生數(shù)目的班委會(huì), 我們需要決定每個(gè)學(xué)生是否屬于班委會(huì). 因?yàn)檫@ n 個(gè)學(xué)生中的每一個(gè)學(xué)生要么在班委會(huì), 要么不在,所以每個(gè)學(xué)生都有兩種可能性, 因此有 2n 種方法.
我們?cè)谶@兩個(gè)答案上的邏輯都無(wú)懈可擊, 因此它們一定是相等的, 即恒等式成立.
另一個(gè)有用的證明技巧是把一個(gè)恒等式的左邊表示為一個(gè)集合的大小,右邊表示為另一個(gè)不同的集合的大小, 然后在兩個(gè)集合之間建立一個(gè)一一對(duì)應(yīng)關(guān)系. 我們用如下恒等式說(shuō)明證明結(jié)構(gòu)
∑k≥0
(2nk ) = ∑k≥ 0 (2kn+ 1 ), n > 0.
這兩個(gè)求和都是有限的, 因?yàn)楫?dāng) i > n 時(shí), 有 (ni ) = 0. 因此很容易看出等式兩邊計(jì)數(shù)的意義, 關(guān)鍵是找出它們之間的對(duì)應(yīng)關(guān)系.
集合 1 從有 n 個(gè)人的班里選偶數(shù)個(gè)人組成一個(gè)班委會(huì), 這個(gè)集合的大小是 ∑k≥0(2nk ).
集合 2 從有 n 個(gè)人的班里選奇數(shù)個(gè)人組成一個(gè)班委會(huì), 這個(gè)集合的大小是 ∑k≥0(2kn+ 1 ).
對(duì)應(yīng)關(guān)系: 假設(shè)班里有一名學(xué)生叫作沃爾多, 那么任何一個(gè)有偶數(shù)個(gè)成員的班委會(huì)都可以通過(guò)問(wèn) “沃爾多在哪兒” ∗ 變成一個(gè)有奇數(shù)個(gè)成員的班委會(huì).如果沃爾多在班委會(huì)里, 那就去掉他ꎻ 如果他不在班委會(huì)里, 那就加上他. 無(wú)論哪種方法, 班委會(huì)的成員數(shù)都將由偶數(shù)變成奇數(shù). 由于 “去掉或加上沃爾多” 的過(guò)程是完全可逆的, 所以我們?cè)谶@些集合間得到
一個(gè)一一對(duì)應(yīng)的關(guān)系. 因此, 這兩個(gè)集合必須大小相等, 于是恒等式成立.
如果我們認(rèn)為另一種證明方法會(huì)給問(wèn)題的解決帶來(lái)新的思路, 通常我們會(huì)用不止一種方法證明恒等式. 例如, 上面的恒等式也能通過(guò)直接計(jì)算偶數(shù)子集數(shù)來(lái)證明. 參見恒等式 129 及后續(xù)討論.
在閱讀本書時(shí), 你會(huì)期待看到哪些內(nèi)容呢? 第 1 章介紹了一種斐波那契數(shù)列的組合解釋, 即用方磚和多米諾磚進(jìn)行平鋪的問(wèn)題, 它是第 2 ~ 4 章的基礎(chǔ).我們從此處切入是因?yàn)殪巢�那契�?shù)列本身很有趣, 并且作為組合學(xué)的內(nèi)容, 它
的證明過(guò)程對(duì)于許多讀者來(lái)說(shuō)也將是一種意外的愉悅. 與所有章節(jié)一樣, 本章以基本的恒等式和簡(jiǎn)單的論證開始, 這將有助于讀者在接觸更多復(fù)雜材料前熟悉概念. 推廣斐波那契平鋪將允許我們探究涉及廣義范圍的斐波那契數(shù)的恒等式, 包括盧卡斯數(shù) (第 2 章)､ 線性遞推 (第 3 章) 和連分式 (第 4 章).
第 5 章介紹的是二項(xiàng)式系數(shù)的經(jīng)典組合內(nèi)容. 對(duì)集合計(jì)數(shù)的計(jì)重或不計(jì)重會(huì)得出有關(guān)二項(xiàng)式系數(shù)的恒等式. 第 6 章介紹了含有交錯(cuò)正負(fù)號(hào)的二項(xiàng)式恒等式. 通過(guò)在兩個(gè)含有奇數(shù)個(gè)元素的集合和偶數(shù)個(gè)元素的集合間尋找對(duì)應(yīng)關(guān)系,
我們可以通過(guò) “容斥原理” 避免使用已熟知的過(guò)度計(jì)數(shù)或計(jì)數(shù)不足的方法.
調(diào)和數(shù), 就像連分?jǐn)?shù), 都不是整數(shù). 因此, 組合解釋需要研究具體表達(dá)式的分子和分母. 調(diào)和數(shù)與第一類斯特林?jǐn)?shù)是相互關(guān)聯(lián)的, 第 7 章探究了這種關(guān)聯(lián)以及第二類斯特林恒等式.
第 8 章考慮了更多的經(jīng)典結(jié)果, 它們均來(lái)自算術(shù)､ 數(shù)論和代數(shù)學(xué), 包括連續(xù)整數(shù)之和､ 連續(xù)平方和､ 連續(xù)立方和及費(fèi)馬小定理､ 威爾遜定理以及拉格朗日定理的一個(gè)部分逆定理.
第 9 章我們處理了更為復(fù)雜的斐波那契恒等式和二項(xiàng)式恒等式. 這些恒等式需要巧妙的論證, 引入著色平鋪或用概率模型等. 它們也許是本書最具挑戰(zhàn)的部分, 但的確值得花時(shí)間去研究.
我們偶爾會(huì)脫離恒等式去證明有趣的應(yīng)用, 例如, 第 1 章中關(guān)于斐波那契數(shù)的可除性證明, 第 2 章中一個(gè)小魔術(shù), 第 5 章中計(jì)算二項(xiàng)式系數(shù)奇偶性的捷徑以及第 8 章中任意素?cái)?shù)同余的推廣等.
除了第 9 章, 每一章節(jié)都給有興趣的讀者準(zhǔn)備了一些對(duì)應(yīng)的練習(xí), 從而幫助他們檢測(cè)自己的計(jì)數(shù)技巧. 大多數(shù)章節(jié)都包含了一些依然在尋求組合證明的恒等式. 書中包括了習(xí)題提示, 參考書目, 并且在附錄中列出了書中所涉及的全部恒等式.
我們希望每一章節(jié)是獨(dú)立的, 這樣您就可以用一種非線性的方式去閱讀.
誰(shuí)應(yīng)當(dāng)計(jì)數(shù)?
這個(gè)問(wèn)題最直接的答案是 “每一個(gè)人!” , 我們希望本書可以讓沒(méi)有經(jīng)過(guò)數(shù)學(xué)專業(yè)訓(xùn)練的讀者來(lái)欣賞. 本書的大多數(shù)，證明高中水平的學(xué)生都可以接受.另一方面, 教師也許可以將這本書作為有用的教學(xué)資源, 它側(cè)重了證明的書寫過(guò)程以及對(duì)問(wèn)題的創(chuàng)造性處理技巧. 我們不將這本書看成是對(duì)組合證明的
完整概述. 相反, 這只是一個(gè)開始. 閱讀完之后, 你再也不會(huì)用之前的方法看待斐波那契數(shù)和連分?jǐn)?shù)之類的數(shù)字了, 我們希望例如表示斐波那契數(shù)的恒等式f2n + 1 = ∑ni = 0n∑j=0(n -j i ) (n i- j )可以讓你感覺(jué)到有些東西正在被計(jì)數(shù)并且有去計(jì)數(shù)的意愿. 最后, 我們希望這
本書能激勵(lì)那些希望發(fā)現(xiàn)舊恒等式的組合學(xué)解釋或是新的恒等式的數(shù)學(xué)家. 親
愛的讀者, 我們誠(chéng)邀您在之后的版本中與我們分享你們喜愛的組合學(xué)證明.
我們希望為完成這本書的所有努力在某些方面是有價(jià)值的.誰(shuí)對(duì)本書的完成做出了貢獻(xiàn)?
我們榮幸地感謝為這本書的完成做出直接貢獻(xiàn)或間接貢獻(xiàn)的人們. 那些早于我們的, 對(duì)組合學(xué)證明的興起具有推動(dòng)作用的人. 以下的書籍是我們不能忽視的, 有丹尼斯􀅰 斯坦頓和丹尼斯􀅰 懷特的 «構(gòu)造組合學(xué)», 理查德􀅰 斯坦利的«計(jì)數(shù)組合學(xué)» 的第一和第二輯, 伊恩􀅰 古爾登和大衛(wèi)􀅰 杰克遜的 «組合計(jì)算»,
榮􀅰 雷姆爾特､ 高德納和帕塔許尼克的 «具體數(shù)學(xué)». 除了這些數(shù)學(xué)家, 其他人的工作也啟發(fā)了我們, 包括喬治 E􀆰 安德魯斯､ 大衛(wèi)􀅰 布雷蘇德､ 理查德􀅰 布魯阿爾迪､ 倫納德􀅰 卡里茨､ 艾拉􀅰 蓋賽爾､ 阿德里亞諾􀅰 蓋莎､ 拉爾夫􀅰 格里
馬爾迪､ 理查德􀅰 蓋伊､ 斯蒂芬􀅰 米爾恩､ 吉姆􀅰 普羅普､ 瑪爾塔􀅰 斯韋德､赫伯特􀅰 維爾夫, 以及多倫􀅰 澤爾博格.尋求組合學(xué)定理證明過(guò)程的好處之一是能讓本科研究者參與進(jìn)來(lái). 在此感謝羅賓􀅰 鮑爾､ 蒂姆􀅰 加內(nèi)斯､ 丹􀅰 奇喬､ 卡爾􀅰 馬赫博格､ 格雷格􀅰 普勒斯
頓以及克里斯􀅰 哈努撒､ 大衛(wèi)􀅰 蓋普勒､ 羅伯特􀅰 蓋普勒和杰里米􀅰 勞斯, 他們獲得了哈維穆德學(xué)院貝克曼研究基金､ 霍華休斯醫(yī)學(xué)研究中心以及珍妮特􀅰邁爾的本科生研究獎(jiǎng)勵(lì)支持. 我們的同行們彼得 G􀆰 安德森､ 鮑勃􀅰 比爾斯､ 杰
伊􀅰 科德斯､ 杜安􀅰 德􀅰 唐普勒､ 佩爾西􀅰 戴康尼斯､ 艾拉􀅰 蓋塞爾､ 湯姆􀅰哈爾沃森､ 梅爾文 􀅰 豪斯特､ 丹 􀅰 卡爾曼､ 格雷格 􀅰 萊溫､ T􀆰 S􀆰 邁克爾､邁克􀅰 歐瑞森､ 羅伯􀅰 普拉特､ 吉姆􀅰 普羅普､ 詹姆斯􀅰 坦頓､ 道格􀅰 韋斯特､
比爾􀅰 茲維克爾, 尤其是弗朗西斯􀅰 蘇, 為我們提供了思路､ 恒等式､ 結(jié)果或是其他珍貴的信息.
如果沒(méi)有唐􀅰 阿爾伯斯的鼓勵(lì), 丹􀅰 威爾曼的工作以及美國(guó)數(shù)學(xué)協(xié)會(huì)的道奇阿尼委員會(huì), 我們將不會(huì)完成本書.
最后, 我們永遠(yuǎn)感激我們的家人所給予的愛與支持.