教材和参考书,教材 Introductory Combinatorics（组合数学） R. A. Bruadli 著 机械工业出版社 第四版（中文）45 元 第四版（英文）59 元 销售经理余勇：13801271785 参考书 组合数学引论 孙淑玲 许胤龙 中国科学技术大学出版社 组合数学 卢开澄 清华大学出版社 成绩 作业 40% 考试 60%,组合数学,第 1 章 什么是组合数学 第 2 章 鸽巢原理 第 3 章 排列与组合 第 4 章 生成排列和组合 第 5 章 二项式系数 第 6 章 容斥原理及应用 第 7 章 递推关系和生成函数 第 8 章 特殊计数序列,第1章 什么是组合数学,组合数学是研究“安排”的学科。主要研究以下四类 问题。 存在性问题（是否存在某种安排） 计数问题（安排的个数、枚举、分类） 构造问题（寻找安排的算法） 优化问题（找出一定条件下的最优安排）,排课表问题,需安排甲、乙、丙、丁四位教师教英语、日语、德语、法语四门课，每人教一门。 甲和乙能教英语、日语， 丙能教英语、德语、法语， 丁只能教德语， 是否能够排出课表？ 甲、乙、丙、丁分别教英语、日语、法语、德语。,棋盘完美覆盖问题,一个多米诺骨牌可覆盖同一行或同一列两相邻方格。若用若干多米诺骨牌覆盖棋盘所有方格，并且多米诺骨牌不重叠，则称该覆盖为完美覆盖。 m n 棋盘有完美覆盖 iff m 和 n 中至少有一个是偶数。 当 m 是偶数时，每块多米诺骨牌竖放。 当 m 是奇数且 n 是偶数时，每块多米诺骨牌横放。 当 m 和 n 都是奇数时，棋盘的方格数 mn 是奇数。,幻方,在由 1, 2, , n2 组成的 n n 方阵中，若每行之和、每列之和、每条对角线之和都相等，则称该方阵为 n 阶幻方。对于 n 2，存在 n 阶幻方。例如，左下方方阵是 3 阶幻方。若右下方方阵是 2 阶幻方，则 u + v = u + y，所以 v = y，矛盾。无 2 阶幻方。,计数问题,将三角形顶点染红、蓝两色，共有 23 = 8 种方法，若一种染色旋转后可变为另一种，则认为这两种染色相同，那么仅有 4 种方法（分别有 0, 1, 2, 3 个顶点染红色）。 有多少种方法将正整数 n 表示成正整数之和，即 n 有多少个分拆。如 4 有 5 个分拆： 4，3 + 1，2 + 2，2 + 1 + 1，1 + 1 + 1 + 1,构造问题,构造 n 阶幻方的方法，其中 n 是奇数。 将 1 放在第一行中间。 自左下至右上沿对角线顺次放随后各数，将最后一行认为是第一行上面的行，第一列认为是最后一列右面的列。 若要放数的位置已有数，则将数放在原数下方。,优化问题,第 2 章 鸽巢原理,本章主要讨论简单形式和加强形式的鸽巢原理及其应用。 本章还简单讨论鸽巢原理的推广：Ramsey 定理。 2.1 鸽巢原理：简单形式 2.2 鸽巢原理：加强形式 2.3 Ramsey定理 作业,2.1 鸽巢原理：简单形式,定理2.1.1 若将多于 n 个物体放入 n 个盒子，则至少有一个盒子中的物体数大于 1。 设 f : A B ，将 A 看做物体的集合， B 看做盒子的集合，物体 a 放在盒 子 f(a) 中。 如果 | A | | B |，则 f 不是从 A 到 B 的单射（一对一的函数） 。,鸽巢原理应用,从 1, 2, , 200 中任意选出 101 个数，必有两个数其中一个能够整除另一个。 证明 将数表示成形式 2k a，其中 a 是奇数。小于 200 的奇数只有 100 个，即 1, 3, , 199，所以这 101 个数中必有两数表示为 2k a 和 2j a ， 2k a | 2j a 当且仅当 k j,鸽巢原理应用,设 n 是正整数，必存在由数字 0 和 7 组成的正整数能被 n 整除。,中国剩余定理,设 m 和 n 是互素的正整数，即它们的最大公约数是 1，0 a m ，0 b n，必存在正整数 x 使得，m 除 x 余 a，n 除 x 余 b。 证明 考虑 n 个数 a, m + a, , (n 1)m + a 若其中两数 im + a 和 jm + a 被 n 除余数相同，则 n | (i j)m ，n | (i j)，0 | i j | n，矛盾。 a, m + a, , (n 1)m + a 被 n 除余数各不相同，其中有 mk + a 被 n 除余 b，取 x = mk + a 。,卡盟排行榜 www.kadianwl.com 卡盟,Microsoft Office PowerPoint，是微软公司的演示文稿软件。用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中。利用Microsoft Office PowerPoint不仅可以创建演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。 Microsoft Office PowerPoint做出来的东西叫演示文稿，其格式后缀名为：ppt、pptx；或者也可以保存为：pdf、图片格式等,2.2 鸽巢原理：加强形式,定理2.2.1 设 q1, qn 是正整数。将多于 q1 + + qn n 个物体放入 n 个盒子，或者第 1 个盒子中至少有 q1 个物体，或者第 n 个盒子中至少有 qn 个物体。 证明 否则物体总数至多 q1 1 + + qn 1 = q1+ + qn n 取 q1= = qn = 2，就退化为简单形式的鸽巢原理。,例 设 n = 3，考虑如下序列： 7, 3, 4, 6, 3, 4, 2, 0, 1, 2 序列 m1 , m2 , m3 , m4 , m5 , m6 , m7 , m8 , m9 , m10 为： 1, 3, 2, 1, 2, 1, 2, 3, 2, 1 其中 m3 = m5 = m7 = m9 = 2， 4, 3, 2, 1 是递减子序列。 其中 m1 = m4 = m6 = m10 = 1， 7, 6, 4, 2 是递减子序列。,2.3 Ramsey 定理,用 Kn 表示 n 阶完全无向图，用红、蓝两种颜色为Kn 的边染色，若每条边都染成红（蓝）色，则称它为红（蓝） Kn 。 K2 K3 K4 K5,设正整数 p, m, n 2，引进记号 Kp Km , Kn ： 若用红、蓝两种颜色为 Kp 的边任意染色，则总存在红 Km 或蓝 Kn 。 Ramsey 定理 若正整数 m, n 2，则存在正整数 p 使得 Kp Km , Kn。并称使 Kp Km , Kn 成立的最小正整数 p 为 Ramsey数 r(m, n)。 K5 K3 , K3 不成立。 由此可知，r (3, 3) 5。,r (3, 3) = 6,设 K6 的六个顶点分别为 v1, , v6 。 v1 与 v2, , v6 的连边中必有三个是同色的，不妨设 v1 与 v2, v3, v4 的连边都是红色，若三角形 v2v3v4 中某边是红色的，则有红三角形。若三角形 v2v3v4 中边都是蓝色的，则有蓝三角形。 因此， K6 K3 , K3 。 r (3, 3) 6，因此， r (3, 3) = 6。,显然，r(m, n) = r(n, m)。 r(m, 2) = m 。 若 Km 中都是红边，则有红 Km ；若 Km 中有蓝边，则有蓝 K2 。所以 Km Km , K2 。 若 Km1 中都是红边，则既没有红 Km ，也没有蓝 K2 。所以 Km1 Km , K2 不成立。 40 r(3, 10) = r(10, 3) 43，即 K43 K3 , K10 成立且 K39 K3 , K10 不成立。 对于 i = 40, 41, 42，不知 Ki K3 , K10 是否成立。,r (k, l) 表,可以将 Ramsey 定理推广到任意多种颜色的情况。 引进记号 Kp Kn1 , , Knk 表示：用 k 种颜色 c1, ck 为 Kp 的边任意染色，或者有一个被染成 c1 色的 Kn1 ，或者有一个被染成 ck 色的 Knk 。 Ramsey 定理 若 n1, nk 2，则有正整数 p 使得 Kp Kn1 , , Knk 使得 Kp Kn1 , , Knk 成立的最小正整数 p 称为Ramsey 数 r(n1, nk)。 r(3, 3, 3) = 17,Ramsey 定理是加强形式鸽巢原理的推广。 令 t = 1，将 “为 1 元子集 u 染色 ci ” 看作 “将 u 放入第 i 个盒子中”，可以得出 r1(q1, qk) = q1+ + qk k + 1,作业,7，11，14，17,第 3 章 排列与组合,3.1 四个基本的计数原理 3.2 集合的排列 3.3 集合的组合 3.4 多重集的排列 3.5 多重集的组合 作业,3.1 四个基本的计数原理,加法原理 设 S = S1 S2 Sm 是 m 个两两不相交集合之并，即若 i j，则 Si Sj = 。那么， | S | = | S1 | + | S2 | + + | Sm |。 乘法原理 | A1 Am | = | A | | Am | 其中 A1 Am = (a1, am): a1A1, amAm,减法原理 设 A 是有限集合 U 的子集， A 的补集 则 A 的元素个数 | A| 由以下公式给出： 除法原理 如果有限集 S 被分成包含同样多个元素的 k 部分，那么部分的数目 k 由以下公式给出：,相等原理 如果在集合 A 和 B 之间存在一一对应， 则 | A | = | B | 。 例 n 元集 S = 1, , n 的子集个数等于由 0 和 1 组成的长度为 n 的串的个数。 证明 可在 S 的子集的集合与由 0 和 1 组成的长度为 n 的串的集合之间建立一一对应如下： 让 S 的每个子集 A 对应串 a1an ，其中 对于每个 iS ，,例 确定 10! 的正整数因子数,10! = 2 3 10 = 28 34 52 7 m | 10! iff m = 2i 3j 5k 7l , 其中 0 i 8, 0 j 4, 0 k 2, 0 l 1 10! 的正整数因子数 = |(i, j, k, l): 0 i 8, 0 j 4, 0 k 2, 0 l 1| = 9 5 3 2 = 270,恰有一位数字是 5 的 10,000 的正整数有多少个？ 解法1 其中有一个一位数：5。 在二位数中，若十位为 5，则个位有 9 种取法；若个位为 5，则十位有 8 种取法（不能取 0）。 共有 9 + 8 = 17 个二位数。 在三位数中，若百位为 5，则十位和个位各有 9 种取法；若十（个）位为 5，则百位有 8 种取法（不能取 0） ，个（十）位有 9 种取法。共有 9 9 + 2 8 9 = 225 个三位数。,在四位数中，若千位为 5，则百位、十位、个位各有 9 种取法；若百（十、个）位为 5，则千位有 8 种取法（不能取 0），其余各位各有 9 种取法。共有 9 9 9 + 3 8 9 9 = 2,673 个四位数。 总共有 1 + 17 + 225 + 2,673 = 2,916 个数。 解法2 将每个数都看作四位数，例如，将 1 看作 0001，某位数字是 5，其余位有 9 种选择，数字 5可以在个、十、百、千位，所以，满足条件的数总共有 4 9 9 9 = 2,9