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