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

前言

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

內(nèi)容概要

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

書籍目錄

總序第2版前言第1版前言緒論第1章  鴿巢原理  1.1  鴿巢原理的簡單形式  1.2  鴿巢原理的加強(qiáng)形式  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章  二項(xiàng)式系數(shù)  3.1  二項(xiàng)式定理  3.2  二項(xiàng)式系數(shù)的基本性質(zhì)  3.3  組合恒等式  3.4  多項(xiàng)式定理第4章  容斥原理  4.1  引論  4.2  容斥原理  4.3  容斥原理的應(yīng)用    4.3.1  具有有限重?cái)?shù)的多重集合的r組合數(shù)    4.3.2  錯(cuò)排問題    4.3.3  有禁止模式的排列問題    4.3.4  實(shí)際依賴于所有變量的函數(shù)個(gè)數(shù)的確定  4.4  有限制位置的排列及棋子多項(xiàng)式  4.5  Mobius反演及可重復(fù)的圓排列第5章  生成函數(shù)  5.1  引論  5.2  形式冪級(jí)數(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章  特殊計(jì)數(shù)序列  7.1  Fibonacci數(shù)  7.2  Catalan數(shù)  7.3  集合的分劃與第二類Stirling數(shù)  7.4  分配問題第8章  Polya計(jì)數(shù)理論  8.1  引論  8.2  群的基本概念  8.3  置換群  8.4  計(jì)數(shù)問題的數(shù)學(xué)模型  8.5  Burnside引理    8.5.1  共軛類    8.5.2  足不動(dòng)置換類    8.5.3  等價(jià)類    8.5.4  Burnside引理  8.6  映射的等價(jià)類  8.7  Polya計(jì)數(shù)定理第9章  相異代表系  9.1  引論  9.2  相異代表系  9.3  棋盤覆蓋問題  9.4  二分圖的匹配問題  9.5  最大匹配算法第10章  組合設(shè)計(jì)  10.1  兩個(gè)古老問題    10.1.1  36名軍官問題    10.1.2  女生問題  10.2  衡不完全區(qū)組設(shè)計(jì)    10.2.1  幾個(gè)基本術(shù)語    10.2.2  關(guān)聯(lián)矩陣及其性質(zhì)    10.2.3  三連系  10.3  幾何設(shè)計(jì)    10.3.1  有限射影平面    10.3.2  平面設(shè)計(jì)    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個(gè)隊(duì)之間的循環(huán)賽總共有多少場比賽？　?。?）如何設(shè)計(jì)一個(gè)學(xué)校的課程表，使得同一間教室、同一個(gè)班級(jí)以及同一位教員在同一時(shí)間內(nèi)沒有安排兩門課程？　?。?）一位旅客要去n個(gè)城市旅游，如何安排其行程，使得總的行程最短、花費(fèi)最少？　　組合數(shù)學(xué)也稱為組合學(xué)或組合分析，它是一門既古老又年輕的數(shù)學(xué)分支。說其古老，是因?yàn)樗芯康挠行﹩栴}可以追溯到很久很久以前，組合學(xué)在17和18世紀(jì)與數(shù)論、概率計(jì)算交叉地發(fā)展，特別是在數(shù)學(xué)游戲中有著較深的根源，以往只是它的娛樂性及高雅性吸引人們?nèi)パ芯克?。近幾十年來，?jì)算機(jī)科學(xué)、數(shù)字通信理論、規(guī)劃論和試驗(yàn)設(shè)計(jì)等理論和應(yīng)用學(xué)科的發(fā)展促進(jìn)了組合學(xué)的飛速發(fā)展，特別是20世紀(jì)50年代末以來計(jì)算機(jī)科學(xué)的飛速發(fā)展，又使這門古老的數(shù)學(xué)分支煥發(fā)了新的生機(jī)。計(jì)算機(jī)驚人的計(jì)算速度，使得其可以解決以前難以想象的大規(guī)模計(jì)算問題，但計(jì)算機(jī)是不能獨(dú)立工作的，它所執(zhí)行的只是人編寫的程序，這些程序中經(jīng)常包含了許多組合問題的求解算法?，F(xiàn)在，組合學(xué)不僅在理論科學(xué)，而且在應(yīng)用科學(xué)中也產(chǎn)生了很大的作用，它的“思想”和“技巧”在物理學(xué)、生物學(xué)乃至社會(huì)科學(xué)中都有應(yīng)用。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

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

---