《組合數(shù)學(xué)》教學(xué)大綱

1、組合數(shù)學(xué)Combinatorial Mathematics一、課程基本情課程類別：專業(yè)任選課課程學(xué)分： 2學(xué)分課程總學(xué)時： 32學(xué)時，其中講課：32 學(xué)時，實驗（含上機）：0學(xué)時，課外0學(xué)時課程性質(zhì)：選修開課學(xué)期：第5學(xué)期先修課程：離散數(shù)學(xué)，高等代數(shù)適用專業(yè)：信息與計算科學(xué)教 材：盧開澄，盧華明，組合數(shù)學(xué)(第4版)，清華大學(xué)出版社，2006。開課單位：數(shù)學(xué)與統(tǒng)計學(xué)院，信息與計算科學(xué)系二、課程性質(zhì)、教學(xué)目標(biāo)和任務(wù)組合數(shù)學(xué)不僅在基礎(chǔ)數(shù)學(xué)研究中具有極其重要的地位，在其它的學(xué)科中也有重要的應(yīng)用，如計算機科學(xué)、編碼和密碼學(xué)、物理、化學(xué)、生物等學(xué)科中均有重要應(yīng)用。本課程主要通過組合數(shù)學(xué)的學(xué)習(xí)，鍛煉學(xué)生的論

2、證能力，用組合學(xué)的思想和方法培養(yǎng)學(xué)生分析問題和解決問題的能力。使學(xué)生能得到嚴(yán)格的邏輯推理與抽象思維能力的訓(xùn)練，了解數(shù)學(xué)中的抽象思維、建立數(shù)學(xué)模型與計算機科學(xué)實踐之間的內(nèi)在聯(lián)系，不僅提高專業(yè)開發(fā)能力，而且為其它課程的學(xué)習(xí)打好數(shù)學(xué)基礎(chǔ)。具體來說，通過本課程的學(xué)習(xí)，應(yīng)達(dá)到知識和能力兩方面的目標(biāo)，知識方面：系統(tǒng)地學(xué)習(xí)組合數(shù)學(xué)中的排列與組合、遞推關(guān)系、生成函數(shù)、容斥原理及其應(yīng)用、鴿巢原理和Ramsey定理、Plya定理。為解決實際問題打好知識基礎(chǔ)。能力方面：使學(xué)生能得到組合數(shù)學(xué)的思想、方法和理論嚴(yán)格的邏輯推理與抽象思維能力的訓(xùn)練，了解數(shù)學(xué)中的抽象思維與實踐之間的內(nèi)在聯(lián)系，提高分析問題和解決問題的能力。三

3、、教學(xué)內(nèi)容和要求第1章 緒論（1學(xué)時）（1）理解組合數(shù)學(xué)的性質(zhì)、研究對象、方法、特點與意義； （2）理解組合數(shù)學(xué)三問題：存在問題、計數(shù)問題、優(yōu)化問題；（3）了解組合數(shù)學(xué)的歷史和應(yīng)用；（4）了解本課的學(xué)習(xí)內(nèi)容、意義與目標(biāo)；重點：組合數(shù)學(xué)的性質(zhì)、研究對象，組合數(shù)學(xué)的三問題難點：組合數(shù)學(xué)的三問題第2章 排列與組合（7學(xué)時）（1）掌握加法法則與乘法法則；（2）理解一一對應(yīng)概念；（3）理解排列與組合的概念：掌握組合的主要性質(zhì)熟練掌握排列數(shù)與組合數(shù)的計算方法；（4）掌握圓周排列的求法；（5）了解全排列與組合的生成方法；（6）掌握允許重復(fù)的組合與不相鄰的組合；（7）理解組合意義的解釋；（8）了解Stir1i

4、ng公式和Stir1ing數(shù)；重點：排列與組合的概念、計算方法難點：允許重復(fù)的組合與不相鄰組合，組合解釋第3章 遞推關(guān)系與母函數(shù)（12學(xué)時）（1）理解母函數(shù)與遞推關(guān)系的基本概念；（2）掌握母函數(shù)的性質(zhì)；（3）理解Fibonacci序列及其在優(yōu)選法中的應(yīng)用；（4）理解線性遞推關(guān)系的概念，掌握常系數(shù)線性遞推關(guān)系的解法；（5）掌握建立簡單問題的遞推關(guān)系式的方法；（6）理解整數(shù)拆分的意義和方法，掌握Ferrers圖像的性質(zhì)；（7）理解指數(shù)生成函數(shù)的概念，會用它解有關(guān)簡單問題；（8）了解廣義二項式定理和非線性遞推關(guān)系的應(yīng)用；重點：母函數(shù)的概念與性質(zhì)，常系數(shù)線性遞推關(guān)系的解法難點：母函數(shù)的用法，整數(shù)拆分的

5、方法第4章 容斥原理與鴿巢原理（7學(xué)時）（1）理解De Morgan定理；（2）理解容斥原理，掌握容斥原理的應(yīng)用；（3）理解棋盤多項式的意義和應(yīng)用，掌握利用棋盤多項式計算有禁區(qū)排列；（4）了解廣義容斥原理和應(yīng)用；（5）了解第二類Stir1ing數(shù)的展開式；（6）理解鴿巢原理的簡單形式，掌握鴿巢原理應(yīng)用；（7）理解鴿巢原理的一般形式；（8）了解Ramsey問題和Ramsey數(shù)的概念；重點：De Morgan定理，容斥原理，鴿巢原理難點：棋盤多項式、廣義容斥原理、Ramsey數(shù)第5章 Burnside引理與Plya定理（5學(xué)時）（1）理解群的概念及性質(zhì)，理解置換群的概念；（2）掌握Burnside引理的意義及應(yīng)用；（3）掌握Plya定理的意義及應(yīng)用；重點：群的概念，Burnside引理 ，Plya定理難點：Burnside引理 ，Plya定理四、課程考核（1）作業(yè)等：作業(yè)：6次，課程論文： 0篇；（2）考核方式：閉卷考試（3）總評成績計算方式：平時成績*20期末考試成績*80五、參考書目（1）R. A. Brualdi著，馮舜璽，羅平，