組合數(shù)學(xué)引論

前言

　　2008年是中國科學(xué)技術(shù)大學(xué)建校五十周年。為了反映五十年來辦學(xué)理念和特色，集中展示教材建設(shè)的成果，學(xué)校決定組織編寫出版代表中國科學(xué)技術(shù)大學(xué)教學(xué)水平的精品教材系列。在各方的共同努力下，共組織選題281種，經(jīng)過多輪、嚴(yán)格的評審，最后確定50種入選精品教材系列?！　?958年學(xué)校成立之時，教員大部分都來自中國科學(xué)院的各個研究所。作為各個研究所的科研人員，他們到學(xué)校后保持了教學(xué)的同時又作研究的傳統(tǒng)。同時，根據(jù)“全院辦校，所系結(jié)合”的原則，科學(xué)院各個研究所在科研第一線工作的杰出科學(xué)家也參與學(xué)校的教學(xué)，為本科生授課，將最新的科研成果融入到教學(xué)中。五十年來，外界環(huán)境和內(nèi)在條件都發(fā)生了很大變化，但學(xué)校以教學(xué)為主、教學(xué)與科研相結(jié)合的方針沒有變。正因為堅持了科學(xué)與技術(shù)相結(jié)合、理論與實踐相結(jié)合、教學(xué)與科研相結(jié)合的方針，并形成了優(yōu)良的傳統(tǒng)，才培養(yǎng)出了一批又一批高質(zhì)量的人才?！　W(xué)校非常重視基礎(chǔ)課和專業(yè)基礎(chǔ)課教學(xué)的傳統(tǒng)，也是她特別成功的原因之一。當(dāng)今社會，科技發(fā)展突飛猛進、科技成果日新月異，沒有扎實的基礎(chǔ)知識，很難在科學(xué)技術(shù)研究中作出重大貢獻。建校之初，華羅庚、吳有訓(xùn)、嚴(yán)濟慈等老一輩科學(xué)家、教育家就身體力行，親自為本科生講授基礎(chǔ)課。他們以淵博的學(xué)識、精湛的講課藝術(shù)、高尚的師德，帶出一批又一批杰出的年輕教員，培養(yǎng)了一屆又一屆優(yōu)秀學(xué)生。這次入選校慶精品教材的絕大部分是本科生基礎(chǔ)課或?qū)I(yè)基礎(chǔ)課的教材，其作者大多直接或間接受到過這些老一輩科學(xué)家、教育家的教誨和影響，因此在教材中也貫穿著這些先輩的教育教學(xué)理念與科學(xué)探索精神。

內(nèi)容概要

本書以組合計數(shù)問題為重點，介紹了組合數(shù)學(xué)的基本原理和思想方法。全書共分10章：鴿巢原理，排列與組合，二項式系數(shù)，容斥原理，生成函數(shù)，遞推關(guān)系，特殊計數(shù)序列，Polya計數(shù)理論，相異代表系，組合設(shè)計。取材的側(cè)重點在于體現(xiàn)組合數(shù)學(xué)在計算機科學(xué)特別是在算法分析領(lǐng)域中的應(yīng)用。每章后面都附有一定數(shù)量的習(xí)題，供讀者練習(xí)和進一步思考。    本書可作為計算機專業(yè)、應(yīng)用數(shù)學(xué)專業(yè)研究生和高年級本科生的教材或教學(xué)參考書，也可供從事這方面工作的教學(xué)、科研和技術(shù)人員參考。

書籍目錄

總序第2版前言第1版前言緒論第1章  鴿巢原理  1.1  鴿巢原理的簡單形式  1.2  鴿巢原理的加強形式  1.3  Ramsey問題與Ramsey數(shù)    1.3.1  Ramsey問題    1.3.2  Ramsey數(shù)  1.4  Ramsey數(shù)的推廣第2章  排列與組合  2.1  加法原則與乘法原則    2.1.1  加法原則    2.1.2  乘法原則  2.2  集合的排列  2.3  集合的組合  2.4  多重集合的排列  2.5  多重集合的組合第3章  二項式系數(shù)  3.1  二項式定理  3.2  二項式系數(shù)的基本性質(zhì)  3.3  組合恒等式  3.4  多項式定理第4章  容斥原理  4.1  引論  4.2  容斥原理  4.3  容斥原理的應(yīng)用    4.3.1  具有有限重數(shù)的多重集合的r組合數(shù)    4.3.2  錯排問題    4.3.3  有禁止模式的排列問題    4.3.4  實際依賴于所有變量的函數(shù)個數(shù)的確定  4.4  有限制位置的排列及棋子多項式  4.5  Mobius反演及可重復(fù)的圓排列第5章  生成函數(shù)  5.1  引論  5.2  形式冪級數(shù)  5.3  生成函數(shù)的性質(zhì)  5.4  組合型分配問題的生成函數(shù)    5.4.1  組合數(shù)的生成函數(shù)    5.4.2  組合型分配問題的生成函數(shù)  5.5  排列型分配問題的指數(shù)型生成函數(shù)    5.5.1  排列數(shù)的指數(shù)型生成函數(shù)    5.5.2  排列型分配問題的指數(shù)型生成函數(shù)  5.6  正整數(shù)的分拆    5.6.1  有序分拆    5.6.2  無序分拆    5.6.3  分拆的Ferrers圖    5.6.4  分拆數(shù)的生成函數(shù)第6章  遞推關(guān)系  6.1  遞推關(guān)系的建立  6.2  常系數(shù)線性齊次遞推關(guān)系的求解  6.3  常系數(shù)線性非齊次遞推關(guān)系的求解  6.4  用迭代歸納法求解遞推關(guān)系  6.5  用生成函數(shù)求解遞推關(guān)系    6.5.1  用生成函數(shù)求解常系數(shù)線性齊次遞推關(guān)系    6.5.2  用生成函數(shù)求解常系數(shù)線性非齊次遞推關(guān)系第7章  特殊計數(shù)序列  7.1  Fibonacci數(shù)  7.2  Catalan數(shù)  7.3  集合的分劃與第二類Stirling數(shù)  7.4  分配問題第8章  Polya計數(shù)理論  8.1  引論  8.2  群的基本概念  8.3  置換群  8.4  計數(shù)問題的數(shù)學(xué)模型  8.5  Burnside引理    8.5.1  共軛類    8.5.2  足不動置換類    8.5.3  等價類    8.5.4  Burnside引理  8.6  映射的等價類  8.7  Polya計數(shù)定理第9章  相異代表系  9.1  引論  9.2  相異代表系  9.3  棋盤覆蓋問題  9.4  二分圖的匹配問題  9.5  最大匹配算法第10章  組合設(shè)計  10.1  兩個古老問題    10.1.1  36名軍官問題    10.1.2  女生問題  10.2  衡不完全區(qū)組設(shè)計    10.2.1  幾個基本術(shù)語    10.2.2  關(guān)聯(lián)矩陣及其性質(zhì)    10.2.3  三連系  10.3  幾何設(shè)計    10.3.1  有限射影平面    10.3.2  平面設(shè)計    10.3.3  仿射平面  10.4  正交拉丁方    10.4.1  拉丁方及正交拉丁方    10.4.2  用有限域構(gòu)造正交拉丁方完備組  10.5  Hadamard矩陣  10.6  用有限域構(gòu)造Hadamard矩陣

章節(jié)摘錄

　　許多組合問題經(jīng)常出現(xiàn)在我們的日常工作、生活及娛樂中，相信本書的讀者在此之前一定接觸過組合問題，例如：　?。?）n個隊之間的循環(huán)賽總共有多少場比賽？　　（2）如何設(shè)計一個學(xué)校的課程表，使得同一間教室、同一個班級以及同一位教員在同一時間內(nèi)沒有安排兩門課程？　?。?）一位旅客要去n個城市旅游，如何安排其行程，使得總的行程最短、花費最少？　　組合數(shù)學(xué)也稱為組合學(xué)或組合分析，它是一門既古老又年輕的數(shù)學(xué)分支。說其古老，是因為它所研究的有些問題可以追溯到很久很久以前，組合學(xué)在17和18世紀(jì)與數(shù)論、概率計算交叉地發(fā)展，特別是在數(shù)學(xué)游戲中有著較深的根源，以往只是它的娛樂性及高雅性吸引人們?nèi)パ芯克?。近幾十年來，計算機科學(xué)、數(shù)字通信理論、規(guī)劃論和試驗設(shè)計等理論和應(yīng)用學(xué)科的發(fā)展促進了組合學(xué)的飛速發(fā)展，特別是20世紀(jì)50年代末以來計算機科學(xué)的飛速發(fā)展，又使這門古老的數(shù)學(xué)分支煥發(fā)了新的生機。計算機驚人的計算速度，使得其可以解決以前難以想象的大規(guī)模計算問題，但計算機是不能獨立工作的，它所執(zhí)行的只是人編寫的程序，這些程序中經(jīng)常包含了許多組合問題的求解算法。現(xiàn)在，組合學(xué)不僅在理論科學(xué)，而且在應(yīng)用科學(xué)中也產(chǎn)生了很大的作用，它的“思想”和“技巧”在物理學(xué)、生物學(xué)乃至社會科學(xué)中都有應(yīng)用。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    組合數(shù)學(xué)引論 PDF格式下載

---