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

1、 組合數(shù)學(xué)教學(xué)大綱組合數(shù)學(xué)課程是數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)的專業(yè)選修課程，也是應(yīng)用性很強的一門數(shù)學(xué)課。本課程主要研究一組離散對象滿足一定條件的安排的存在性，以及這種安排的構(gòu)造，枚舉計數(shù)及優(yōu)化問題，它是整個離散數(shù)學(xué)的一個重要組成部分。目前組合數(shù)學(xué)不僅成為數(shù)學(xué)中的一個重要分支，而且還成為計算機科學(xué)，管理科學(xué)及其它學(xué)科的數(shù)學(xué)基礎(chǔ)。設(shè)置本課程的目的是：一方面使學(xué)生學(xué)好作為專業(yè)課程的組合數(shù)學(xué)課，為組合方向的后續(xù)研究打下基礎(chǔ)；另一方面培養(yǎng)學(xué)生理論聯(lián)系實際和分析問題、解決問題的能力，會用組合的想法解決實際問題。學(xué)習(xí)本課程的要求是：通過本課程的學(xué)習(xí)，要使學(xué)生具有現(xiàn)代數(shù)學(xué)的觀點和方法，初步掌握常用組合計數(shù)的構(gòu)造思想和計

2、算方法。要求掌握鴿巢原理、排列組合原理、容斥原理、遞推關(guān)系與生成函數(shù)。同時，也要培養(yǎng)學(xué)生抽象思維和慎密概括的能力，使學(xué)生具有良好的開拓專業(yè)理論的素質(zhì)和使用所學(xué)知識，分析和解決實際問題的能力。先修課程要求：數(shù)學(xué)分析，高等代數(shù)，概率論本課程計劃72學(xué)時，3學(xué)分選用教材：孫淑玲 許胤龍編著，組合數(shù)學(xué)引論，中國科技大學(xué)出版社，2005教學(xué)手段：課堂講授為主，習(xí)題課與討論課為輔考核方法：閉卷書面考試教學(xué)進(jìn)程安排表周次學(xué)時數(shù)教學(xué)主要內(nèi)容教學(xué)環(huán)節(jié)備注12鴿巢原理的簡單形式及其應(yīng)用講課12鴿巢原理的加強形式，相關(guān)推論講課22Ramsey問題的提出及證明，Ramsey數(shù)及其相關(guān)結(jié)論講課22Ramsey數(shù)的推廣形

3、式，Ramsey定理講課與習(xí)題課相結(jié)合32加法原則與乘法原則，排列與組合，多重集合的排列與組合討論課32二項式定理與二項式系數(shù)的基本性質(zhì)組合恒等式，多項式定理講課42集合的分化與第二類Stirling數(shù)的相關(guān)定理講課42正整數(shù)的分拆，有序分拆及其相關(guān)定理無序分拆及其相關(guān)定理講課52分拆的Ferrers圖，F(xiàn)errers圖的共軛圖講課52分配問題的基本想法，分配問題的實例講課與習(xí)題課相結(jié)合62容斥原理的引入背景，容斥原理的簡單實例講課62容斥原理的一般形式及其證明，容斥原理的幾個推論，講課72容斥原理的進(jìn)一步討論講課72具有有限重復(fù)數(shù)的多重集合的r組合數(shù)問題，錯排問題講課82有禁止模式的的排列問

4、題，mnage問題與mnage數(shù)講課82Mbius函數(shù)的定義，Mbius反演定理及其證明講課92可重復(fù)排列問題講課與習(xí)題課相結(jié)合92遞推關(guān)系的概念，遞推關(guān)系的建立講課102常系數(shù)線性齊次遞推關(guān)系的概念與解的結(jié)構(gòu)講課與習(xí)題課相結(jié)合102常系數(shù)線性齊次遞推關(guān)系的求解過程與應(yīng)用舉例講課112常系數(shù)線性非齊次遞推關(guān)系的概念與解的結(jié)構(gòu)講課112常系數(shù)線性非齊次遞推關(guān)系的求解過程與應(yīng)用舉例講課122Fibonacci數(shù)的引入，組合意義，推倒過程與應(yīng)用舉例講課122Catalan數(shù)的引入，組合意義，推倒過程與應(yīng)用舉例講課與習(xí)題課相結(jié)合132生成函數(shù)的引入與舉例，形式冪級數(shù)的概念講課132形式冪級數(shù)的基本性質(zhì)

5、，形式冪級數(shù)的形式導(dǎo)數(shù)講課142生成函數(shù)的性質(zhì)與證明講課142幾種常見的簡單數(shù)列生成函數(shù)的求解講課152用生成函數(shù)求解常系數(shù)線性齊次遞推關(guān)系的具體方法講課152用生成函數(shù)求解常系數(shù)線性非齊次遞推關(guān)系的具體方法講課162組合數(shù)的生成函數(shù)，排列數(shù)的指數(shù)型生成函數(shù)講課162分拆數(shù)的生成函數(shù)，組合型分配問題的生成函數(shù)講課172排列型分配問題的生成函數(shù)，有限制位置的排列講課172有限制位置的排列的基本結(jié)論，棋子多項式講課182復(fù)習(xí)習(xí)題課182復(fù)習(xí)習(xí)題課第一章預(yù)備知識一、學(xué)習(xí)目的通過本章的學(xué)習(xí)，要求學(xué)生掌握鴿巢原理與鴿巢原理的加強形式，并會用鴿巢原理與鴿巢原理的加強形式討論和解決實際問題。理解Ramsey

6、問題，會討論簡單的Ramsey數(shù)，了解Ramsey的推廣形式和Ramsey定理。本章計劃8學(xué)時。二、課程內(nèi)容11鴿巢原理的簡單形式鴿巢原理的簡單形式，利用鴿巢原理解決實際問題。12鴿巢原理的加強形式鴿巢原理的加強形式及推論，鴿巢原理加強形式的應(yīng)用舉例。13Ramsey問題與Ramsey數(shù)經(jīng)典Ramsey問題的提出與證明，Ramsey問題的延伸，Ramsey數(shù)及其相關(guān)定理。14Ramsey數(shù)的推廣Ramsey問題與Ramsey數(shù)的推廣形式，Ramsey定理及其證明。三、教學(xué)基本要求了解：經(jīng)典Ramsey問題的引入，Ramsey定理。理解：鴿巢原理與鴿巢原理的推廣形式。鴿巢原理所體現(xiàn)的組合思想。掌

7、握：利用鴿巢原理解決實際問題，判斷簡單Ramsey數(shù)的方法。四、重點、難點提示和教學(xué)手段（一）本章重點鴿巢原理的應(yīng)用，Ramsey數(shù)的判定。（二）本章難點Ramsey定理及其證明。（三）教學(xué)手段課堂講授與習(xí)題課相結(jié)合五、思考與練習(xí)思考：如何將鴿巢原理和Ramsey定理有機的聯(lián)系起來。練習(xí)由授課教師自行確定。第二章基本計數(shù)問題一、學(xué)習(xí)目的通過本章的學(xué)習(xí)，熟練掌握加法原則，乘法原則，排列組合及二項式定理及其相關(guān)結(jié)論，理解集合的分化和正整數(shù)分拆的思想。掌握第二類Stirling數(shù)的相關(guān)性質(zhì)。能夠給出分拆的Ferrers圖，能夠求解簡單的分配問題，并能分析，解決實際問題。本章計劃14學(xué)時。二、課程內(nèi)容

8、21加法原則和乘法原則加法原則及其相關(guān)定理，乘法原理及其相關(guān)定理。22排列與組合排列的基本定義，排列數(shù)，組合的定義，組合數(shù)，排列數(shù)與組合數(shù)的應(yīng)用舉例。23多重集合的排列與組合多重集合的概念，多重集合排列的概念與基本定理，多重集合組合的概念與基本定理，增字。24二項式系數(shù)二項式定理，二項式定理的基本性質(zhì)(對稱關(guān)系，遞推關(guān)系，單峰性)與組合意義。一些組合恒等式，多項式定理。25集合的分化與第二類Stirling數(shù)集合分化的定義，第二類Stirling數(shù)的定義及相關(guān)性質(zhì)。26正整數(shù)的分拆正整數(shù)分拆的定義。有序分拆的定義及相關(guān)結(jié)論，無序分拆的定義及相關(guān)結(jié)論，正整數(shù)分拆的Ferrers圖與共軛。利用分拆

9、的Ferrers圖證明的關(guān)于分拆的基本結(jié)論。27分配問題分配問題的提出及分析。三、教學(xué)基本要求理解：多重集合的概念，集合的分化和正整數(shù)分拆的思想。掌握：加法原則，乘法原則，排列組合，多重集合的排列組合及二項式定理及其相關(guān)結(jié)論，第二類Stirling數(shù)的相關(guān)性質(zhì)，實際應(yīng)用的分配問題。四、重點、難點提示和教學(xué)手段（一）本章重點多重集合的概念及其排列組合，二項式定理及其基本性質(zhì)，Stirling數(shù)的性質(zhì)。（二）本章難點有序分拆，無序分拆的相關(guān)結(jié)論。（三）教學(xué)手段課堂講授與討論課、習(xí)題課相結(jié)合五、思考與練習(xí)思考：討論幾種分配問題之間的聯(lián)系。練習(xí)由授課教師自行確定。第三章容斥原理一、學(xué)習(xí)目的通過本章的學(xué)

10、習(xí)，掌握一種重要的組合計數(shù)方法：容斥原理。了解容斥原理引入的背景，理解容斥原理原理的思想，會用容斥原理解決一些實際問題，了解Mbius反演及可重復(fù)圓排列的思想。本章計劃16學(xué)時。二、課程內(nèi)容31引論容斥原理引入的背景及重要意義，容斥原理在幾個簡單問題上的應(yīng)用。32容斥原理容斥原理及其證明，容斥原理的推論及其證明。33容斥原理的應(yīng)用具有有限重復(fù)數(shù)的多重集合的人r組合數(shù)問題，錯排問題，有禁止模式的錯排問題，mnage問題及既化的mnage問題，實際依賴于所有變量的函數(shù)個數(shù)的確定問題。34Mbius反演及可重復(fù)的圓排列Mbius函數(shù)的定義，Mbius反演定理及其證明，可重復(fù)排列問題。三、教學(xué)基本要求

11、理解：理解容斥原理原理的思想，Mbius函數(shù)的概念。了解：容斥原理引入的背景及重要意義，了解Mbius反演及可重復(fù)圓排列的思想。掌握：利用容斥原理解決組合計數(shù)問題。四、重點、難點提示和教學(xué)手段（一）本章重點容斥原理的思想及表達(dá)形式，具有有限重復(fù)數(shù)的多重集合的人r組合數(shù)問題，錯排問題，可重復(fù)排列問題。（二）本章難點Mbius反演及可重復(fù)圓排列，容斥原理解決組合計數(shù)問題（三）教學(xué)手段課堂講授與習(xí)題課相結(jié)合五、思考與練習(xí)思考與練習(xí)由授課教師自行確定。第四章遞推關(guān)系一、學(xué)習(xí)目的通過本章的學(xué)習(xí)，理解遞推關(guān)系內(nèi)在的組合結(jié)構(gòu)，掌握遞推關(guān)系的建立方法，掌握幾種特殊遞推關(guān)系的求解方法。了解幾種特殊的遞推關(guān)系：F

12、ibonacci數(shù)列合Catalan數(shù)列。本章計劃14學(xué)時。二、課程內(nèi)容41遞推關(guān)系的建立遞推關(guān)系的概念，幾個實例遞推關(guān)系的建立。42常系數(shù)線性齊次遞推關(guān)系的求解k階常系數(shù)線性齊次遞推關(guān)系的概念，遞推關(guān)系特征根的定義，k階常系數(shù)線性齊次遞推關(guān)系解的結(jié)構(gòu)，k階常系數(shù)線性齊次遞推關(guān)系求解的一般方法。43常系數(shù)線性非齊次遞推關(guān)系的求解k階常系數(shù)線性非齊次遞推關(guān)系的概念，k階常系數(shù)線性非齊次遞推關(guān)系通解的結(jié)構(gòu)，k階常系數(shù)線性非齊次遞推關(guān)系求解的一般方法，k階常系數(shù)線性非齊次遞推關(guān)系應(yīng)用舉例。44用迭代歸納法求解的遞推關(guān)系用迭代歸納法求解的遞推關(guān)系基本思想，用迭代歸納法求解的遞推關(guān)系步驟，應(yīng)用舉例。45

13、 Fibonacci數(shù)與Catalan數(shù)Fibonacci數(shù)列的引入背景與組合意義，F(xiàn)ibonacci數(shù)的求解過程。Catalan數(shù)列的引入背景與組合意義，Catalan數(shù)列的求解過程，應(yīng)用舉例。三、教學(xué)基本要求理解：k階常系數(shù)線性齊次遞推關(guān)系求解的思想，k階常系數(shù)線性非齊次遞推關(guān)系求解的基本思想，迭代歸納法求解遞推關(guān)系的基本思想。了解：Fibonacci數(shù)列與Catalan數(shù)列的引入背景及組合意義。掌握：遞推關(guān)系的建立方法，k階常系數(shù)線性(非)齊次遞推關(guān)系通解的結(jié)構(gòu)與一般解法。四、重點、難點提示和教學(xué)手段（一）本章重點遞推關(guān)系的建立過程，k階常系數(shù)線性齊次遞推關(guān)系通解結(jié)構(gòu)，k階常系數(shù)線性齊次

14、遞推關(guān)系求解的一般方法。（二）本章難點k階常系數(shù)線性非齊次遞推關(guān)系通解的結(jié)構(gòu)。迭代歸納法求解的遞推關(guān)系基本思想與具體步驟。（三）教學(xué)手段課堂講授與習(xí)題課相結(jié)合。五、思考與練習(xí)思考與練習(xí)由授課教師自行確定。第五章生成函數(shù)一、學(xué)習(xí)目的通過本章的學(xué)習(xí)，了解生成函數(shù)引入的背景，理解形式冪級數(shù)的相關(guān)概念，了解形式冪級數(shù)的一些基本性質(zhì)，掌握利用生成函數(shù)求解遞推關(guān)系的方法，會利用生成函數(shù)討論一些組合計數(shù)問題。本章計劃20學(xué)時。二、課程內(nèi)容51引論生成函數(shù)的引入與應(yīng)用舉例。52形式冪級數(shù)形式冪級數(shù)的概念，形式冪級數(shù)的相等，形式冪計數(shù)的數(shù)乘，加法，代數(shù)分析。形式冪級數(shù)的形式導(dǎo)數(shù)及相關(guān)性質(zhì)。53生成函數(shù)的性質(zhì)生成

15、函數(shù)的基本性質(zhì)及其證明過程，幾個常見的生成函數(shù)。54用生成函數(shù)求解遞推關(guān)系用生成函數(shù)求解遞推的基本想法與步驟，用生成函數(shù)求解常系數(shù)線性齊次遞推關(guān)系的方法，通解形式。用生成函數(shù)求解常系數(shù)線性非齊次遞推關(guān)系的方法，通解形式。55生成函數(shù)在計數(shù)問題中的應(yīng)用幾類特殊的生成函數(shù)，組合數(shù)的生成函數(shù)，排列數(shù)的指數(shù)型生成函數(shù)，分拆數(shù)的生成函數(shù)，組合型分配問題的生成函數(shù)，排列型分配問題的生成函數(shù)。56有限位置的排列及棋子多項式有限制位置的排列的理論推倒，棋盤問題與棋子多項式。三、教學(xué)基本要求理解：形式冪級數(shù)的相關(guān)概念，利用生成函數(shù)求解組合計數(shù)問題的想法。了解：生成函數(shù)引入的背景，有限制位置的排列與棋盤問題。掌握：用生成函數(shù)求解常系數(shù)線性齊次遞推關(guān)系的方法，通解形式。用生成函數(shù)求解常系數(shù)線性非齊次遞推關(guān)系的方法，通解形式。四、重點、難點提示和教學(xué)手段（一）本章重點形式冪級數(shù)的概念。用生成函數(shù)求解常系數(shù)線性齊