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

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

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

3、、教學內(nèi)容和要求第1章 緒論（1學時）（1）理解組合數(shù)學的性質(zhì)、研究對象、方法、特點與意義； （2）理解組合數(shù)學三問題：存在問題、計數(shù)問題、優(yōu)化問題；（3）了解組合數(shù)學的歷史和應(yīng)用；（4）了解本課的學習內(nèi)容、意義與目標；重點：組合數(shù)學的性質(zhì)、研究對象，組合數(shù)學的三問題難點：組合數(shù)學的三問題第2章 排列與組合（7學時）（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學時）（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學時）（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學時）（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著，馮舜璽，羅平，