組合數學

第1章  基本解題方法與計數法則
    1.1  組合數學簡介與基本解題方法
        1.1.1  組合數學簡介
        1.1.2  基本解題方法
    1.2  常用符號與基本計數法則
        1.2.1  常用符號
        1.2.2  基本計數法則
    習題1
第2章  二項式與多項式定理
    2.1  二項式定理與楊輝三角形
        2.1.1  二項式定理
        2.1.2  楊輝三角形
    2.2  多項式定理
        2.2.1  多項式定理簡介
        2.2.2  多項式系數的性質
        2.2.3  多項式系數的計數意義
    習題2
第3章  排列與組合
    3.1  初等排列與組合
        3.1.1  排列
        3.1.2  組合
    3.2  排列與組合恒等式
        3.2.1  基本恒等式
        3.2.2  組合恒等式
        3.2.3  排列恒等式
        3.2.4  可重組合恒等式
    3.3  網絡路徑問題
    3.4  進位制與正整數的階乘表示法
        3.4.1  進位制
        3.4.2  最優(yōu)進制
        3.4.3  正整數的階乘表示法
    3.5  排列與組合的生成
        3.5.1  排列的生成算法
        3.5.2  組合的生成算法
    3.6  Wallis公式
    3.7  Stirling公式
    習題3
第4章  母函數與遞推關系
    4.1  母函數
        4.1.1  母函數的定義
        4.1.2  母函數的性質
    4.2  遞推關系
        4.2.1  Hanoi塔問題
        4.2.2  Fibonacci級數
        4.2.3  遞推關系的定義
        4.2.4  有理分式的分項表示
        4.2.5  遞推關系的解
    4.3  普母函數與遞推關系
        4.3.1  示例
        4.3.2  線性常系數齊次遞推關系的母函數解法
        4.3.3  線性常系數非齊次遞推關系的母函數解法
    4.4  母函數與排列組合
        4.4.1  普母函數與組合
        4.4.2  指母函數與排列
    4.5  指母函數與錯排
    4.6  普母函數與分拆
        4.6.1  分拆的定義
        4.6.2  有序分拆
        4.6.3  Ferrers圖
        4.6.4  無序分拆
        4.6.5  關于p(n)
    4.7  普母函數與Catalan數
        4.7.1  三角剖分問題
        4.7.2  乘法結合方式問題
        4.7.3  Catalan數的通項公式
        4.7.4  Catalan數的組合意義
        4.7.5  Catalan數的性質
    4.8  母函數與Stirling數
        4.8.1  Stirling數的定義
        4.8.2  Stirling數的遞推關系
        4.8.3  Stirling數的母函數
        4.8.4  Stirling數的通項公式
        4.8.5  Stirling數的組合意義
        4.8.6  Stirling數的性質
    4.9  球盒分配問題
    4.10  有限和式
        4.10.1  遞推關系求有限和式
        4.10.2  母函數求有限和式
        4.10.3  差分表求有限和式
    習題4
第5章  容斥原理
    5.1  容斥原理
        5.1.1  容斥原理的簡單形式
        5.1.2  容斥原理的一般形式
        5.1.3  對稱篩公式
    5.2  容斥原理與限位排列
    5.3  棋盤多項式與限位排列
        5.3.1  棋盤多項式
        5.3.2  限位排列
    5.4  Mbius函數與Euler函數
    5.5  Mbius反演
    5.6  多重集的圓排列
    習題5
第6章  鴿籠原理
    6.1  鴿籠原理
        6.1.1  鴿籠原理的簡單形式
        6.1.2  鴿籠原理的基本形式
        6.1.3  鴿籠原理的推廣
    6.2  Ramsey理論
        6.2.1  Ramsey定理
        6.2.2  Ramsey數
    習題6
第7章  幾何圖形計數
    7.1  簡單圖形計數
    7.2  子圖形計數
    7.3  圖形的切割
    7.4  折線法
    7.5  整點與整邊三角形
    習題7
第8章  P′olya定理
    8.1  群的基本概念
    8.2  置換與置換群
        8.2.1  置換
        8.2.2  置換群
    8.3  輪換與置換的奇偶性
        8.3.1  輪換
        8.3.2  置換的奇偶性
    8.4  Burnside引理
        8.4.1  共軛類
        8.4.2  置換群的軌道
        8.4.3  不變置換類
        8.4.4  Burnside引理
    8.5  P′olya定理
    8.6  母函數型的P′olya定理
    習題8
第9章  組合設計
    9.1  拉丁方
        9.1.1  拉丁方的概念
        9.1.2  正交拉丁方
    9.2  域
        9.2.1  域的概念
        9.2.2  Galois域
        9.2.3  正交拉丁方的構造
    9.3  區(qū)組設計
        9.3.1  區(qū)組設計
        9.3.2  完全區(qū)組設計
        9.3.3  均衡不完全區(qū)組設計
        9.3.4  區(qū)組設計的構造
    9.4  Hadamard矩陣
        9.4.1  Hadamard矩陣
        9.4.2  Hadamard矩陣的構成
    9.5  編碼理論簡介
        9.5.1  編碼及其分類
        9.5.2  線性碼
    習題9
第10章  組合算法及其復雜性
    10.1  排序
        10.11  選擇排序
        10.1.2  氣泡浮起排序
        10.1.3  分段交換排序
        10.1.4  樹型排序
        10.1.5  合并排序
        10.1.6  FORD_JOHNSON排序
    10.2  查找
        10.2.1  順序查找
        10.2.2  折半查找
        10.2.3  分塊查找
    10.3  尋求第k個元素
    10.4  快速Fourier變換
    10.5  組合算法的復雜性
        10.5.1  示例
        10.5.2  貪心算法的時間上界
        10.5.3  “倒樹”算法
        10.5.4  組合算法的復雜性問題
    習題10
附錄A  習題答案與提示
    習題1答案
    習題2答案
    習題3答案
    習題4答案
    習題5答案
    習題6答案
    習題7答案
    習題8答案
    習題9答案
參考文獻