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

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

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

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

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