【正文】 本 科 畢 業(yè) 論 文 第 1 頁(yè) 共 23 頁(yè) 1 引言 說(shuō)起來(lái)，組合數(shù)學(xué)是一門很古老的科學(xué)，人們對(duì)它的興趣和研究肇源頗早，它起始于數(shù)學(xué)游戲，起初只是研究娛樂或?qū)徝酪笏婕暗慕M合問題，據(jù)傳，早在《河圖》、《洛書》中我國(guó)人民就已對(duì)一些有趣的組合問題給出了正確的解答。 賈憲，北宋數(shù)學(xué)家（約 11 世紀(jì)）著有《黃帝九章細(xì)草》、《算法斅古集》（ “古算法導(dǎo)引 ”）都已失傳。楊輝著《詳解九章算法》（ 1261 年）中曾引賈憲的 “開方作法本源 ”圖（即指數(shù)為正整數(shù)的二項(xiàng)式展開系數(shù)表，現(xiàn)稱 “楊輝三角形 ”）和 “增乘開方法 ”（求高次冪的正根法）。前者比帕斯卡三角形早 600 年，后者比 霍納（ William Geoge Horner，17861837）的方法（ 1819）早 770 年。 1666 年萊布尼茲所著《組合學(xué)論文》一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論 （ Combinatorics） 一詞。 但是，這門學(xué)科的飛速發(fā)展和不完善則是近幾十年的事。這是多種因素促進(jìn)的結(jié)果。 一方面，它受到了許多新興的應(yīng)用和理論學(xué)科的推動(dòng)和刺激，諸如計(jì)算科學(xué)、數(shù)字通訊理論、規(guī)劃論和試驗(yàn)設(shè)計(jì)等等。另一方面，它自身內(nèi)部的要求和力量也使它不停息地向前發(fā)展，因而這門具有悠久歷史的學(xué)科又煥發(fā)出青春的光彩， 在近幾十年來(lái)顯得異常活躍，并且頗富成果。今天無(wú)論在基礎(chǔ)理論方面還是在應(yīng)用科學(xué)當(dāng)中都起著非常重要的作用，它已經(jīng)發(fā)展成為數(shù)學(xué)的一個(gè)重要分支，而且其影響正在迅速擴(kuò)大。 還有一個(gè)重要的原因，就是計(jì)算機(jī)的發(fā)展對(duì)社會(huì)所產(chǎn)生和將繼續(xù)產(chǎn)生的巨大沖擊力。由于計(jì)算機(jī)的閃電般的運(yùn)算速度，為用組合數(shù)學(xué)來(lái)解決實(shí)際問題提供了一個(gè)理想的工具，要解決過去根本無(wú)法想象的大規(guī)模問題，現(xiàn)在已經(jīng)成為可能與現(xiàn)實(shí)。 對(duì)于組合數(shù)學(xué)人們有不同的認(rèn)識(shí)。有人認(rèn)為廣義的組合數(shù)學(xué)就是 離散數(shù)學(xué) ，也有人認(rèn)為離散數(shù)學(xué)是狹義的組合數(shù)學(xué)和 圖論 、 代數(shù)結(jié)構(gòu) 、 數(shù)理邏輯 等的總稱。但這只是不同學(xué)者在叫法上的區(qū)別。 組合數(shù)學(xué)問題在生活中隨處可見。例如， n 個(gè)球隊(duì)參賽，每隊(duì)只和其他隊(duì)比賽一次，計(jì) 算在此賽制下總的比賽次數(shù)。網(wǎng)絡(luò)路徑問題，計(jì)算兩點(diǎn)之間路徑有幾種。還有身邊普遍的分組問題。所有這些都是組合數(shù)學(xué)問題。過去研究過的許多問題，不論出于消遣還 本 科 畢 業(yè) 論 文 第 2 頁(yè) 共 23 頁(yè) 是出于對(duì)其美學(xué)的考慮，如今在純科學(xué)和應(yīng)用科學(xué)中都具有高度的重要性。組合數(shù)學(xué)算法與計(jì)算機(jī)技術(shù)的結(jié)合在現(xiàn)代科學(xué)技術(shù)領(lǐng)域發(fā)揮著極為重要的作用。對(duì)從事數(shù)學(xué)的人員來(lái)講，學(xué)習(xí)數(shù)學(xué)組合可以提高分析問題的能力；對(duì)從事計(jì)算機(jī)的人員來(lái)講，若沒有組合數(shù)學(xué)的基礎(chǔ)，就難以深入研究與分析有關(guān)算法。所以說(shuō)，組合數(shù)學(xué)不僅是近年來(lái)最活躍、最迷人的數(shù)學(xué)分支，也是計(jì)算機(jī)科學(xué)技術(shù)的重要理論基礎(chǔ)之一。 組合數(shù)學(xué)近期發(fā)展的另一個(gè)重要原因是它對(duì)于那些過去很少與數(shù)學(xué)正式接觸的學(xué)科的適用性。由此我們發(fā)現(xiàn)，組合數(shù)學(xué)的思想和技巧不僅僅正在用于數(shù)學(xué)應(yīng)用的傳統(tǒng)自然科學(xué)領(lǐng)域，而且也用于電子工程、數(shù)字通信、物理學(xué)、力學(xué)、管理科學(xué)等諸多領(lǐng)域。此外，組合數(shù)學(xué)和組合學(xué)思想在許多數(shù)學(xué)分支中已經(jīng)變得越來(lái)越重要。 組合數(shù)學(xué)中有許多計(jì)數(shù)和歸納原理。本文主要討論網(wǎng)絡(luò)路徑問題、母函數(shù)與排列組合、容斥原理以及幾何圖形計(jì)數(shù)。 1． 1 課題的背景及研究的目的和意義 組合數(shù)學(xué)在在日常生活中的作用日益明顯，本論文主要介紹研究組合數(shù)學(xué)中的四種組合方法。 本論文主 要目是對(duì)四種組合方法進(jìn)行分析，研究其在簡(jiǎn)單數(shù)學(xué)問題中的應(yīng)用。運(yùn)用離散數(shù)學(xué)的思維培養(yǎng)自身分析、解決數(shù)學(xué)問題的能力。討論組合方法在簡(jiǎn)單數(shù)學(xué)問題中的應(yīng)用是本論文研究的中心。 1． 2 本課題研究的內(nèi)容 本論文主要研究的內(nèi)容是對(duì) 網(wǎng)絡(luò)路徑問題、母函數(shù)與排列組合、容斥原理以及幾何圖形計(jì)數(shù)等四種組合方法進(jìn)行分析，研究其在簡(jiǎn)單數(shù)學(xué)中的應(yīng)用。 并且給出四種組合方法的基本組合解釋，并應(yīng)用這些組合方法解決簡(jiǎn)單的組合問題，理解組合方法在組合數(shù)學(xué)研究中的重要意義。培養(yǎng)自己初步研究數(shù)學(xué)問題的能力，從而使自己具有一定的科研獨(dú)立性。 2 網(wǎng)絡(luò)路徑問題 路徑問題的矩陣算法 路徑問題是組合數(shù)學(xué)中的一個(gè)重要問題，本論文主要是在提出的矩陣算法的例子中 本 科 畢 業(yè) 論 文 第 3 頁(yè) 共 23 頁(yè) 總結(jié)出一般算法。 首先規(guī)定所要討論的圖為簡(jiǎn)單的有向圖 ? ?UVD ,? ，其中 },{ 21 nvvvV ?? 表示非空集合， VVU ?? ，其元素稱為弧。 定義矩陣 ? ?nnijaA ??，其中： 若從 iv 點(diǎn)到 jv 點(diǎn)有邊 ? ?ji vv, 相連，則 1?ija ， 若從 iv 點(diǎn)到 jv 點(diǎn)無(wú)邊相連，則 0?ija 。 A 中元素 ija 為 1，表示 1條從 iv 一步到 jv 的道路。 我們?cè)倏?? ?? ?22 ijaAAA ??? ，其中： ? ? njinjijink kjikij aaaaaaaaa ????? ?? ?221112 . 0?ljilaa 當(dāng)且僅當(dāng) 1?ljilaa ，也就是說(shuō)從 iv 到 lv 和從 lv 到 jv 都有直接相通的道路，所以 ??2ija 的值表示從 iv 點(diǎn)出發(fā)經(jīng)過 lv ，再到 jv 的路徑數(shù)目。 進(jìn)而，一般有 ? ?? ? ? ?nknnaA kijk ??? ，其中 ? ? ? ????? nl ljkilkij aaa11 ， ??kija 表示從 iv 出發(fā) k步到達(dá) jv 的路徑數(shù)目。 矩陣算法與乘法原理、加法原理的統(tǒng)一性 加法、乘法原理 加法原理：如果完成一件工作，只要采取 n 類方式中的某一種方式就可以完成，第一類方式有 1m 種做法，第 2類方式有 2m 種做法， ? ，第 n類方式有 nm 種做法，那么，完成這件工作共有 nmmm ??? ?21 種做法。 乘法原理：如果完成一件工作，必須依次經(jīng)過 n個(gè)步驟，第 1步有 1m 種做法，第 2步有 2m 種做法， ? ，第 n步有 nm 種做法，那么，完成這件工作共有 nmmm ??? ?21 種做法。 本 科 畢 業(yè) 論 文 第 4 頁(yè) 共 23 頁(yè) 建立模型 例 下圖為從重慶到義和的路線模型，問共有多少種不同的走法 ? 用加法、乘法原理分析解決問題 第一種，從重慶→義和， 1種走法； 第二種，從重慶→開縣→義和， 11? 種走法； 第三種，從重慶→達(dá)州→開江縣→梅家壩→義和 ↓→開縣→義和 ， 2111 ??? 種走法。 52111111111 ?????????? ，所以從重慶到義和共有 5種不同的走法。 用矩陣方法分析解決問題 為了方便表示，用 7654321 ,, vvvvvvv 分別表示重慶、達(dá)州、開江縣、梅家壩、義和、開縣、萬(wàn)縣，得到一個(gè)單向圖 ? ?UVD ,? ，其中 },{ 721 vvvV ?? 表示 7個(gè)地點(diǎn)， U表示路線，即下圖所示。問題就轉(zhuǎn)變?yōu)閺?1v 到 5v 共有幾條不同的道路。 引進(jìn)矩陣 ? ?77?? ijaA，其中： 本 科 畢 業(yè) 論 文 第 5 頁(yè) 共 23 頁(yè) 若從 iv 點(diǎn)到 jv 點(diǎn)有邊 ? ?ji vv, 相連，則 1?ija ； 若從 iv 點(diǎn)到 jv 點(diǎn)無(wú)邊相連，則 0?ija . 得到765432176543210100000001000000000000010000010100000001001110010vvvvvvvvvvvvvvA???????????????????????從 A中可以看出 1v 到 5v 有一條直 通道路，相當(dāng)于上述分類中的第一類。 ? ?27654321765432120010000000000000000000000000002022001010000110100ijavvvvvvvvvvvvvvAAA ??????????????????????????從 2A 可以看出 1v 到 5v 有一條經(jīng)過一個(gè)