组合数学讲义及课后答案 1章 排列组合.pdfVIP

《组合数学》 第一章 组合数学基础 第1章 组合数学基础 1、排列组合的基本计数问题（研、本） 2、计算多项式系数（研、本） 3、排列组合算法（研） 1.1 绪 论 （一） 背景 起源：数学游戏 2 幻方问题：给定自然数1, 2, …, n ，将其排列成n 阶方阵，要求每 行、每列和每条对角线上n 个数字之和都相等。这样的n 阶 方阵称为 n 阶幻方。每一行（或列、或对角线）之和称为幻 方的和。 例：3 阶幻方，幻和＝(1＋2＋3＋…＋9)/3＝15。 （1） 存在性问题：即n 阶幻方是否存在？ （2） 计数问题：如果存在，对某个确定的n，这样的幻方有 多少种？ （3） 构造问题：即枚举问题，亦即如何构造n 阶幻方。 8 1 6 2 7 6 3 5 7 9 5 1 4 9 2 4 3 8 图1.1.1 3 阶幻方 奇数阶幻方的生成方法： 奇数阶幻方最经典的填法是罗伯法。填写的方法是： 把1(或最小的数)放在第一行正中； 按以下规律排列剩下的 1/69 《组合数学》 第一章 组合数学基础 (n×n－1)个数 (1)每一个数放在前一个数的右上一格； (2)如果这个数所要放的格已经超出了顶行那么就把它放在底 行，仍然要放在右一列； (3)如果这个数所要放的格已经超出了最右列那么就把它放在 最左列，仍然要放在上一行； (4)如果这个数所要放的格已经超出了顶行且超出了最右列， 那么就把它放在前一个数的下一行同一列的格内； (5)如果这个数所要放的格已经有数填入，那么就把它放在前 一个数的下一行同一列的格内。 一坐上行正中央，依次斜填切莫忘， 上边出格往下填，右边出格往左填， 右上有数往下填，右上出格往下填。 例：将2，4，6，8，10，12，14，16，18 填入下列幻方： 例1.1.1 （拉丁方）36 名军官问题：有 1，2，3，4，5，6 共六个团队，从每个团队中分别选出具有A、B、C、D、E、F 六 种军衔的军官各一名，共36 名军官。问能否把这些军官排成6 ×6 的方阵，使每行及每列的 6 名军官均来自不同的团队且具有不同 军衔？ 本问题的答案是否定的。 反例： A1 B2 C3 D4 E5 F6 A1 B2 C3 D4 E5 F6 B2 C3 D4 E5 F6 A1 B3 C4 D5 E6 F1 A2 C3 D4 E5 F6 A1 B2 C5 D6 E1 F2 A3 B4 2/69 《组合数学》 第一章 组合数学基础 D4 E5 F6 A1 B2 C3 D2 E3 F4 A5 B6 C1 E5