《组合数学》教案-1章(排列组合基础)61页.doc

第1章 组合数学基础1. 排列组合的基本计数问题2. 多项式系数的计算及其组合意义3. 排列组合算法1.1 绪 论（一） 背景起源：数学游戏幻方问题：给定自然数1, 2, , n2，将其排列成n阶方阵，要求每行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和（简称幻和）。例：3阶幻方，幻和(1239)/315。关心的问题 （1） 存在性问题：即n阶幻方是否存在？ （2） 计数问题：如果存在，对某个确定的n，这样的幻方有多少种？ （3） 构造问题：即枚举问题，亦即如何构造n阶幻方。816276357951492438奇数阶幻方的生成方法：一坐上行正中央，依次斜填切莫忘，上边出格往下填，右边出格往左填，右上有数往下填，右上出格往下填。例：将2，4，6，8，10，12，14，16，18填入下列幻方：