組合數(shù)學

第1章  基本解題方法與計數(shù)法則
    1.1  組合數(shù)學簡介與基本解題方法
        1.1.1  組合數(shù)學簡介
        1.1.2  基本解題方法
    1.2  常用符號與基本計數(shù)法則
        1.2.1  常用符號
        1.2.2  基本計數(shù)法則
    習題1
第2章  二項式與多項式定理
    2.1  二項式定理與楊輝三角形
        2.1.1  二項式定理
        2.1.2  楊輝三角形
    2.2  多項式定理
        2.2.1  多項式定理簡介
        2.2.2  多項式系數(shù)的性質
        2.2.3  多項式系數(shù)的計數(shù)意義
    習題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  網(wǎng)絡路徑問題
    3.4  進位制與正整數(shù)的階乘表示法
        3.4.1  進位制
        3.4.2  最優(yōu)進制
        3.4.3  正整數(shù)的階乘表示法
    3.5  排列與組合的生成
        3.5.1  排列的生成算法
        3.5.2  組合的生成算法
    3.6  Wallis公式
    3.7  Stirling公式
    習題3
第4章  母函數(shù)與遞推關系
    4.1  母函數(shù)
        4.1.1  母函數(shù)的定義
        4.1.2  母函數(shù)的性質
    4.2  遞推關系
        4.2.1  Hanoi塔問題
        4.2.2  Fibonacci級數(shù)
        4.2.3  遞推關系的定義
        4.2.4  有理分式的分項表示
        4.2.5  遞推關系的解
    4.3  普母函數(shù)與遞推關系
        4.3.1  示例
        4.3.2  線性常系數(shù)齊次遞推關系的母函數(shù)解法
        4.3.3  線性常系數(shù)非齊次遞推關系的母函數(shù)解法
    4.4  母函數(shù)與排列組合
        4.4.1  普母函數(shù)與組合
        4.4.2  指母函數(shù)與排列
    4.5  指母函數(shù)與錯排
    4.6  普母函數(shù)與分拆
        4.6.1  分拆的定義
        4.6.2  有序分拆
        4.6.3  Ferrers圖
        4.6.4  無序分拆
        4.6.5  關于p(n)
    4.7  普母函數(shù)與Catalan數(shù)
        4.7.1  三角剖分問題
        4.7.2  乘法結合方式問題
        4.7.3  Catalan數(shù)的通項公式
        4.7.4  Catalan數(shù)的組合意義
        4.7.5  Catalan數(shù)的性質
    4.8  母函數(shù)與Stirling數(shù)
        4.8.1  Stirling數(shù)的定義
        4.8.2  Stirling數(shù)的遞推關系
        4.8.3  Stirling數(shù)的母函數(shù)
        4.8.4  Stirling數(shù)的通項公式
        4.8.5  Stirling數(shù)的組合意義
        4.8.6  Stirling數(shù)的性質
    4.9  球盒分配問題
    4.10  有限和式
        4.10.1  遞推關系求有限和式
        4.10.2  母函數(shù)求有限和式
        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函數(shù)與Euler函數(shù)
    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數(shù)
    習題6
第7章  幾何圖形計數(shù)
    7.1  簡單圖形計數(shù)
    7.2  子圖形計數(shù)
    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  母函數(shù)型的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答案
參考文獻