1第一章-排列与组合.ppt

组合数学Combinatorial mathematicsor combinatorics 参考书 组合数学习题解答，曹汝成，华南理工大学出版社； 组合数学，Richard，机械工业出版社； 应用组合数学(applied combinatorics), Fred S. Roberts, 冯速 译，机械工业出版社； 组合数学，卢开澄，清华大学出版社。 组合数学，南基洙，高等教育出版社 幻 方 药物试验设计一 Problem：考虑测试五种药物对人体药效的试验设计，假设这些药物编号为1, 2, 3, 4, 5，挑选5个人，并给每一个不同的药物。 药物试验设计二 同时测试两种类型的药物，头痛药和发烧药，希望测试头痛药和发烧药的所有组合，而且头痛药和发烧药均是按拉丁方来设计。 36军官 分球模型 将n个球分到m个盒子中 球可区分、盒子可区分 球不可区分、盒子可区分 球可区分、盒子不可区分 球不可区分、盒子也不可区分 附加条件：每个盒子至少分到一个 递推与通项公式 数列：1, 1, 2, 3, 5, 8, 13,…… 递推公式： 问题：你能写出这个公式的通项吗？ 问题 存在性？ 如何构造？ 多少个？！！！ 最优？ 内容简介 排列组合: permutation and combination 容斥原理: inconlusion and exclusion principle 递推关系: recurrence relation 生成函数: generation function 整数分拆: partition of integer 鸽笼定理: pigeon hole principle 第一章 排列与组合 §1 计数的基本原则 三条原则 相等原则 equivalence principle 加法原则 addition principle 乘法原则 multiplication principle 相等原则 设A，B是两个有限集，如果存在由A到B上的一个一一对应（双射），则|A|=|B|，即，若存在双射， 则 |A|=|B|. 加法原则 乘法原则 §2 排列permutation n元集合r-排列 n元集的r-可重复排列 多重集的排列 n元集合r-排列 n-元集的r-可重复排列 多重集的排列 §3 T路的计数 T路 反射原理 Catalan数 T路 反射原理 Catalan数 §4 组 合combination n元集的r-组合 n元集的r-可重复组合 组合数的性质 多项式定理 组合恒等式 n元集的r-组合 n元集的r-可重复组合 组合数的基本性质 多项式定理 组合恒等式 §5 二项式反演公式 二项式反演公式 有限集的覆盖 多元二项式反演公式 作业 1，4 ，9，11，13，17，19，23，30，34(2,4)，38（2），45 反演公式 由反演公式 由加法原理 由反演公式 K={由A到B的经过x轴的全体T路} K’={由A’到B的的全体T路} B A A’ G * 1 2 3 4 5 6 7 8 9 23 5 14 16 4 6 13 10 22 12 20 19 21 3 11 18 25 2 9 17 24 1 8 15 7 5 4 3 2 1 E 5 4 3 2 1 D 5 4 3 2 1 C 5 4 3 2 1 B 5 4 3 2 1 A F Th W Tu M 方案一 4 3 2 1 5 E 3 2 1 5 4 D 2 1 5 4 3 C 1 5 4 3 2 B 5 4 3 2 1 A F Th W Tu M 方案二，拉丁方 拉丁方一 拉丁方二 并置，正交的拉丁方 问题： 有36名军官，分别来自6个不同的军团，每个军团 的6名军官又具有6种不同的军衔，能否把他们排成6×6 的编队，使得每行每列的6名军官恰好来自6个不同的团 且他们的军衔不同？ 定理：（1）不存在2阶和6阶的正交拉丁方； （2）对于任何n≠2,6的正整数，都存在一对正交拉丁方。 2 2 3 1 4 3 Step1 确定a1 Y/N Step2 确定a2 Y/N … Y/N Stepn 确定an 解：n的每个约数可以表示为 其中 答案 Case 1: 万位数为3 此时，千位数是5或6 Case 2: 万位数大于3 ＋ ＋ = 41