组合数学—第一章.pdf

组合数学排列与组合 任世军 Email: renshijun@hit.edu.cn 哈尔滨工业大学 计算机学院 November23, 2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 任世军 (哈尔滨工业大学) 组合数学排列与组合 November23, 2015 1/66 目录 1 课程简介 2 排列 3 多重集的排列 4 组合 5 多重组合 6 二项式定理 7 组合恒等式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 任世军 (哈尔滨工业大学) 组合数学排列与组合 November23, 2015 2/66 课程简介 本课程针对计算机科学中的一个重要学科——组合数学，组合数学是数 学的一个分支，它研究事物在结定模式下的配置，研究这种配置的存在性， 所有可能配置的计数和分类以及配置的各种性质。组合数学在计算机科 学中有着极其广泛的应用。 组合学问题求解方法层出不穷、干变万化，应以理解为基础，善于总结各 种技巧，掌握科学的组织和推理方法。 相关课程 《数学分析》《高等代数》《离散数学》 使用的教材 书名：组合数学作者：RichardA.Brualdi 出版社：机械工业出版社 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 任世军 (哈尔滨工业大学) 组合数学排列与组合 November23, 2015 3/66 组合数学研究的中心问题 安排的存在性 如果人们想把有限多个对象按照它们所应满足的条件来进行安排， 当符合要求的安排并非显然存在或显然不存在时，首要的问题就是 要证明或者否定它的存在。这就是存在性问题。 安排的计数 如果所要求的安排存在，则可能有多种不同的安排，这又经常给人们 提出这样的问题：有多少种可能的安排方案？如何对安排的方案进行 分类？这就是计数问题。 安排的结构 如果一个组合问题有解，则往往需要给出求其某一特定解的算法，这 就是所谓的构造性问题。如果算法很多，就需要在一定的条件下找出 一个或者几个最优或近乎最优的安排方案，这就是优化问题。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 任世军 (哈尔滨工业大学) 组合数学排列与组合 November23, 2015 4/66