1、组合数学清华大学 卢开澄1999年 7月前言组合数学是一个古老而又年轻的数学分支。据传说，大禹在 4000多年前就观察到神龟背上的幻方 .前言幻方可以看作是一个 3阶方阵，其元素是 1到 9的正整数，每行、每列以及两条对角线的和都是 15。5193 7248 6前言贾宪 北宋数学家（约 11世纪） 著有黄帝九章细草、算法斅古集斅 音 “笑（ “古算法导引 ”）都已失传。杨辉著详解九章算法（ 1261年）中曾引贾宪的 “开方作法本源 ”图（即指数为正整数的二项式展开系数表，现称 “杨辉三角形 ”）和 “增乘开方法 ”（求高次幂的正根法）。前者比帕斯卡三角形早 600年，后者比霍纳（ Willia
2、m Geoge Horner， 17861837 ） 的方法（ 1819年）早 770年。前言1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics） 一词。前言组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。前言 本学期主要讲组合分析（计数和枚举）以及组合优化的一部分（线性规划的单纯形解法）。 组合分析是组合算法的基础。前言组合数学经常使用的方法并不高深复杂。最主要的方法是 计数时的合理分类 和 组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。第一章 排列组合1.1 加法法则与乘法法则1.1 加法法则与乘法法则 加法法则 设事件 A有 m种产生方式，事件 B有 n种产生方式，则事件 A或 B之一有 m+n种产生方式。集合论语言：若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。
