組合數(shù)學(xué)的歷史、方法及在生活中的應(yīng)用.doc

組合數(shù)學(xué)的歷史、方法及在生活中的應(yīng)用摘 要:組合數(shù)學(xué)從數(shù)千年前開始萌芽，經(jīng)歷了著名的幻方問題和楊輝三角，直到萊布尼茨正式提出這一科學(xué)門類。組合數(shù)學(xué)也稱為組合分析或者組合學(xué). 簡單地說, 組合數(shù)學(xué)是“按照一定的規(guī)則（模式)來安排一些離散個體”.組合數(shù)學(xué)在基礎(chǔ)理論方面和生活應(yīng)用方面都發(fā)揮著越來越重要的作用, 如在計算機(jī)科學(xué)、編碼和密碼學(xué)、物理、化學(xué)、生物等學(xué)科中均有重要應(yīng)用。本文從對組合數(shù)學(xué)歷史、基本內(nèi)容和基本思想,結(jié)合具體的應(yīng)用舉例介紹組合數(shù)學(xué)。關(guān)鍵詞:組合數(shù)學(xué);歷史起源；基本方法；生活應(yīng)用一、組合數(shù)學(xué)的歷史。組合數(shù)學(xué)是一個古老而又年輕的數(shù)學(xué)分支。最早起源于幻方問題。據(jù)傳說，大禹在4000多年前(2200B.C.)就觀察到神龜背上的幻方.1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號。之后，希臘文寫在羊皮紙上的阿基米德手稿副本，距今約1000年。2003年，科學(xué)家借助現(xiàn)代科技手段初步破譯了這篇論文, 結(jié)論是這篇論文解決的是組合數(shù)學(xué)問題十四巧板。中國最早的組合數(shù)學(xué)理論可追溯到宋朝時期的”賈憲三角”, 后來被楊輝引用, 所以普遍稱之為”楊輝三角”, 這在西方是1654年由帕斯卡提出，但比中國晚了400多年。最后是組合數(shù)學(xué)的正式提出。1666年萊布尼茲所著論組合的藝術(shù)一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。一切推理和發(fā)現(xiàn)，不管是否用語言描述，都能歸結(jié)為如數(shù)，字，聲，色這些元素經(jīng)過某種組合的有序集合。2、 組合數(shù)學(xué)的基本內(nèi)容與方法組合數(shù)學(xué)最早是同數(shù)論和概率論交叉在一起的.本世紀(jì)五十年代以來,特別是由于計算機(jī)科學(xué)的巨大發(fā)展,促使組合數(shù)學(xué)成為一支富有生命力的新興數(shù)學(xué)分支.與傳統(tǒng)的數(shù)學(xué)課程相比,組合數(shù)學(xué)研究的主要是一些離散事物之間所存在的某些數(shù)學(xué)關(guān)系,包括計數(shù)性問題、存在性問題、最優(yōu)化問題以及構(gòu)造性問題等,其內(nèi)容主要是枚舉和計數(shù).組合學(xué)中研究最多的主要是計數(shù)問題,該問題通常出現(xiàn)在所有的數(shù)學(xué)分支之中.計算機(jī)科學(xué)通常需要研究有關(guān)算法的內(nèi)容,就必須估計出算法所需的存儲單元和運(yùn)算量,即分析算法的空間復(fù)雜性和時間復(fù)雜性.關(guān)于組合數(shù)學(xué)的基本方法有一下幾種：排列與組合、母函數(shù)與遞推關(guān)系、容斥原理、反演公式、鴿巢原理、Plya計數(shù)定理、區(qū)組設(shè)計與編碼理論等內(nèi)容.僅僅知道方法是遠(yuǎn)遠(yuǎn)不夠的，組合數(shù)學(xué)的一些相關(guān)思想也是非常重要的，這里總結(jié)一下幾條。首先是組合對應(yīng)法，在組合數(shù)學(xué)的學(xué)習(xí)中經(jīng)常使用此法,可以毫不夸張的說貫穿于組合數(shù)學(xué)始終,并且該思想極易理解.設(shè)有一集合,要確定其元素個數(shù),若直接求的元素個數(shù)則相對困難,我們可另找一集合,若在集與集間可建立一一對應(yīng)的關(guān)系,并能確定中的元素個數(shù),那么也能得到種元素的個數(shù).其次是組合分析法，或稱組合解釋法,此法對組合數(shù)學(xué)的初學(xué)者來說相對重要一些,它與代數(shù)演算法有明顯的區(qū)別,其思想主要是給組合數(shù)以確定的現(xiàn)實(shí)意義,對提出的問題給以組合解釋.這種方法的特點(diǎn)是相對直觀,便于理解和記憶,富有啟發(fā)性,類似于我們在連續(xù)型數(shù)學(xué)學(xué)習(xí)中常說的“幾何意義”.第三是分類法在組合數(shù)學(xué)中使用頻率也較高.此方法的基本思想是:設(shè)有某一集合,根據(jù)某一準(zhǔn)則(具體問題具體確定),將分成若干兩兩不交子集之并.最后，是放球模型法，此法是把很多組合問題用放球模型來模擬,盡管組合數(shù)學(xué)中處理問題的方法不帶一般性,但利用此法能解決不少組合問題. 3、 組合數(shù)學(xué)在生活中的應(yīng)用 組合數(shù)學(xué)是十分貼近于人們的生活的，因此組合問題在生活中非常常見。這樣一個簡單的組合數(shù)學(xué)問題：一個船夫要把一只狼，一只羊和一棵白菜運(yùn)過河。而當(dāng)人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運(yùn)其中的一個，問人怎樣才能把三者都運(yùn)過河。下面介紹幾種組合數(shù)學(xué)中的著名問題。中國郵差問題：由中國組合數(shù)學(xué)家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是一個NP完全問題，存在多項(xiàng)式復(fù)雜度算法：先求出度為奇數(shù)的點(diǎn)，用匹配算法算出這些點(diǎn)間的連接方式，然后再用歐拉路徑算法求解。、 信息檢索是計算機(jī)科學(xué)中一個基本而又重要的問題。如何組織數(shù)據(jù), 使用什么樣的查找方法, 對檢索的效率有很大的影響。所熟知的在有序表結(jié)構(gòu)上的二分搜索算法是一種很有效的方法, 那么二分搜索是最好的算法嗎?Yao 4 利用Ramsey 數(shù)對這一問題作了肯定的回答。 地圖著色問題：對世界地圖著色，每一個國家使用一種顏色。如果要求相鄰國家的顏色相異，是否總共只需四種顏色？四色定理是一個著名的數(shù)學(xué)定理。它指出，如果將平面分成一些鄰接的區(qū)域，那么可以用不多于四種顏色來給這些區(qū)域染色，使得每兩個鄰接區(qū)域染的顏色都不一樣。盡管四色定理最初提出是和地圖染色工作有關(guān)，但四色定理本身對地圖著色工作并沒有特別的意義。人們發(fā)現(xiàn)，要證明寬松一點(diǎn)的“五定理”（即“只用五種顏色就能為所有地圖染色”）很容易，但四色問題卻出人意料地異常困難。曾經(jīng)有許多人發(fā)表了四色問題的證明或反例，但都被證實(shí)是錯誤的。1977年，數(shù)學(xué)家Kenneth Appl和Wolfgang Haken借助電子計算機(jī)首次得到了一個完全的證明，四色問題也終于成為了四色定理。這是首個主要由計算機(jī)證明的定理。這個證明一開始并不為許多數(shù)學(xué)家接受，因?yàn)椴簧偃苏J(rèn)為這個證明無法用人手直接驗(yàn)證。盡管隨著計算機(jī)的普及，數(shù)學(xué)界對計算機(jī)輔助證明更能接受，但仍有數(shù)學(xué)家對四色定理的證明存疑。 是否存在穩(wěn)定婚姻的問題：假如能找到兩對夫婦（如張（男）-李（女）和趙（男）-王（女），如果張（男）更喜歡王（女），而王（女）也更喜歡張（男），那么這樣就可能有潛在的不穩(wěn)定性。組合數(shù)學(xué)的方法可以找到一種婚姻的安排方法，使得沒有上述的不穩(wěn)定情況出現(xiàn)（當(dāng)然這只是理論上的結(jié)論）。這種組合數(shù)學(xué)的方法卻有 一個實(shí)際的用途：美國的醫(yī)院在確定錄取住院醫(yī)生時，他們將考慮申請者的志愿的先后次序，同時也給申請排序。按這樣的 次序考慮出的總的方案將沒有醫(yī)院和申請者兩者同時后悔的情況。 實(shí)際上，高考學(xué)生的最后錄取方案也可以用這種方法。組合數(shù)學(xué)還可用于金融分析：組合數(shù)學(xué)還可用于金融分析，投資方案的確定，怎樣找出好的投資組合以降低投資風(fēng)險。南開大學(xué)組合數(shù)學(xué)研究中心開發(fā)出了金沙股市風(fēng)險分析系統(tǒng)現(xiàn)已投放市場，為短線投資者提供了有效的風(fēng)險防范工具。 總之，組合數(shù)學(xué)無處不在，它的主要應(yīng)用就是在各種復(fù)雜關(guān)系中找出最優(yōu)的方案。所以組合數(shù)學(xué)完全可以看成是一門量化的關(guān)系學(xué)，一門量化了的運(yùn)籌學(xué)，一門量化了的管理學(xué)。參考資料 4 A. C. Yao. Should T ables Be Sorted J . ACM, 1981, 28.1 陳家.組合數(shù)學(xué)在計算機(jī)科學(xué)中的應(yīng)用J.成都信息工程學(xué)院學(xué)報,2006(21):94-97.2 陳永川.話說組合數(shù)學(xué)J.科學(xué)中國人,2003(5):15-17.6 左光紀(jì).組合數(shù)學(xué)的科學(xué)藝術(shù)表現(xiàn)J.青海