组合数学

第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  最优进制
        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  区组设计
        9.3.1  区组设计
        9.3.2  完全区组设计
        9.3.3  均衡不完全区组设计
        9.3.4  区组设计的构造
    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答案
参考文献