組合數(shù)學(xué)

第1章  基本解題方法與計數(shù)法則
    1.1  組合數(shù)學(xué)簡介與基本解題方法
        1.1.1  組合數(shù)學(xué)簡介
        1.1.2  基本解題方法
    1.2  常用符號與基本計數(shù)法則
        1.2.1  常用符號
        1.2.2  基本計數(shù)法則
    習(xí)題1
第2章  二項式與多項式定理
    2.1  二項式定理與楊輝三角形
        2.1.1  二項式定理
        2.1.2  楊輝三角形
    2.2  多項式定理
        2.2.1  多項式定理簡介
        2.2.2  多項式系數(shù)的性質(zhì)
        2.2.3  多項式系數(shù)的計數(shù)意義
    習(xí)題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)絡(luò)路徑問題
    3.4  進(jìn)位制與正整數(shù)的階乘表示法
        3.4.1  進(jìn)位制
        3.4.2  最優(yōu)進(jìn)制
        3.4.3  正整數(shù)的階乘表示法
    3.5  排列與組合的生成
        3.5.1  排列的生成算法
        3.5.2  組合的生成算法
    3.6  Wallis公式
    3.7  Stirling公式
    習(xí)題3
第4章  母函數(shù)與遞推關(guān)系
    4.1  母函數(shù)
        4.1.1  母函數(shù)的定義
        4.1.2  母函數(shù)的性質(zhì)
    4.2  遞推關(guān)系
        4.2.1  Hanoi塔問題
        4.2.2  Fibonacci級數(shù)
        4.2.3  遞推關(guān)系的定義
        4.2.4  有理分式的分項表示
        4.2.5  遞推關(guān)系的解
    4.3  普母函數(shù)與遞推關(guān)系
        4.3.1  示例
        4.3.2  線性常系數(shù)齊次遞推關(guān)系的母函數(shù)解法
        4.3.3  線性常系數(shù)非齊次遞推關(guān)系的母函數(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  關(guān)于p(n)
    4.7  普母函數(shù)與Catalan數(shù)
        4.7.1  三角剖分問題
        4.7.2  乘法結(jié)合方式問題
        4.7.3  Catalan數(shù)的通項公式
        4.7.4  Catalan數(shù)的組合意義
        4.7.5  Catalan數(shù)的性質(zhì)
    4.8  母函數(shù)與Stirling數(shù)
        4.8.1  Stirling數(shù)的定義
        4.8.2  Stirling數(shù)的遞推關(guān)系
        4.8.3  Stirling數(shù)的母函數(shù)
        4.8.4  Stirling數(shù)的通項公式
        4.8.5  Stirling數(shù)的組合意義
        4.8.6  Stirling數(shù)的性質(zhì)
    4.9  球盒分配問題
    4.10  有限和式
        4.10.1  遞推關(guān)系求有限和式
        4.10.2  母函數(shù)求有限和式
        4.10.3  差分表求有限和式
    習(xí)題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  多重集的圓排列
    習(xí)題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ù)
    習(xí)題6
第7章  幾何圖形計數(shù)
    7.1  簡單圖形計數(shù)
    7.2  子圖形計數(shù)
    7.3  圖形的切割
    7.4  折線法
    7.5  整點(diǎn)與整邊三角形
    習(xí)題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定理
    習(xí)題8
第9章  組合設(shè)計
    9.1  拉丁方
        9.1.1  拉丁方的概念
        9.1.2  正交拉丁方
    9.2  域
        9.2.1  域的概念
        9.2.2  Galois域
        9.2.3  正交拉丁方的構(gòu)造
    9.3  區(qū)組設(shè)計
        9.3.1  區(qū)組設(shè)計
        9.3.2  完全區(qū)組設(shè)計
        9.3.3  均衡不完全區(qū)組設(shè)計
        9.3.4  區(qū)組設(shè)計的構(gòu)造
    9.4  Hadamard矩陣
        9.4.1  Hadamard矩陣
        9.4.2  Hadamard矩陣的構(gòu)成
    9.5  編碼理論簡介
        9.5.1  編碼及其分類
        9.5.2  線性碼
    習(xí)題9
第10章  組合算法及其復(fù)雜性
    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  組合算法的復(fù)雜性
        10.5.1  示例
        10.5.2  貪心算法的時間上界
        10.5.3  “倒樹”算法
        10.5.4  組合算法的復(fù)雜性問題
    習(xí)題10
附錄A  習(xí)題答案與提示
    習(xí)題1答案
    習(xí)題2答案
    習(xí)題3答案
    習(xí)題4答案
    習(xí)題5答案
    習(xí)題6答案
    習(xí)題7答案
    習(xí)題8答案
    習(xí)題9答案
參考文獻(xiàn)