竞赛数学 排列组合 讲义-北京清北学堂.pdf

排列组合 几种特殊的排列 组合 圆排列 定义 1 从几个元素中任取r个不同元素仅按元素之间的相对位置而不分首尾排成一个 圆圈 这种排列称为n个不同元素的r 圆排列 r 圆排列数记为 r n K 定理定理 1 r P K r nr n 证 对n个不同元素取r个的任一圆排列 均有 r 种不同的方式展开成r个不同的直线 排列 且不同的圆排列展开的直线排列也彼此不同 故有 r r n P r n K 得正 重复排列重复排列 定义定义 2 从n个不同元素中允许重复的任取r个元素排成一列 称为n个不同元素的 r 可重复排列 定理定理 2 n个不同元素的r 可重排列数为 r n 证证 在按顺序选取的r个元素中 每个元素都有n种不同的选法 故由乘法原理有 其 排列数为 r n 不全相异元素的全排列不全相异元素的全排列 定义定义 3 设n个元素可分为 k 组 每一组中的元素是相同的 不同组间的元素是不同的 其中第i组的元素个数为 i n i 1 2 k 12k n n n n 则这n个元素的全排列 称为不全相异元素的全排列 定理定理 3 n个元素的不全相异元素的全排列个数为 21k nnn n 证证 先把每组中的元素看做是不相同的 则n个不同元素的全排列数为 n 然后分别 将每个组的元素还其本来面目看成是相同的 则在这n 个全排列中 每个排列都重复出现 了 12 n n k n 次 所以不全相异元素的全排列数 21k nnn n 多组组合多组组合 定义定义 4 将n个不同的元素分成 k 组的组合称为n个不同元素的 k 组合 定理定理 4 对于一个n个不同元素的 k 组合 若第i组有 i n个元素 i 1 2 k 则不同的分组方法数为 21k nnn n 重重组合重重组合 定义定义 5 从n个不同元素中任取r个允许元素重复出现的组合称为n个不同元素的 r 可重组合 枚举法枚举法 所谓枚举法就是把集合 A 中的元素一一列举出来 从而计算出集体 A 的元素个数 它 是最基本 也是最简单的计算数方法 应用枚举法计数的关键在于一一列举集合中的元素时 必须做到既不重又不漏 分类计数原理与分步计数原理分类计数原理与分步计数原理 分类计算原理 完成一件事 有几种方式 第一种方式有m种方法 第二种方式有n种 方法 最后一种方式有r种方法 不管采取哪一种方法都能完成这件事 则完成这件事的 方法总数为m n r 分步计数原理 完成一件事 有几个步骤 第一步有m种方法 第二步有n种方法 最后一步有r种方法 要完成这件事 必须通过每一步 则完成这件事的方法总数为 m n r 应用分类计数原理的关键在于分划 即把一个所要计数的集合S分划成一些两两不交的 小集合 且使每个小集合都便于计数 应用分步计数原理的关键在于分解 即把一个所要计数的集合S分解成若干个集合的乘 积 对一个集合S 的分划或分解 没有一般方法 应由具体问题而定 而这正是应用两个 原理解题的难点与技巧所在 递推方法递推方法 将与正整数有关的数字问题 通过寻求递推公式 或通过递推公式 而使问题得到解 决的方法 叫做递推方法 递推方法几乎对所有数学分支都具有重要的作用 当然对组合计数就更不例外了 它 是组合计数的常用方法 组合恒等式组合恒等式 0 1 2 3210 210 1 1 11 1 n n n nnnn nn nnnn mr mn m n m n r n r n r n r n r n r n rn n r n CCCCC CCCC CCCC C r n C CCC CC 组合恒等式的证明方法有 恒等变形 变换求和指标 建立递推关系 数学归纳法 考虑组合意义 母函数 组合不等式组合不等式 组合不等式以前我们见的不多 在其他一些书籍中组合不等式的著述也很少 设 A 是一个有n个元素的集合 A 的m个子集 12m A A A两两互不包含 试证 1 m i A n I C 1 1 1 2 m i A n mC I 1 2 其中 Ai 表示 Ai所含元素的个数 I A n C表示 n 个不同元素取 Ai 的组合数 我们有必要研究组合不等式的证明方法 组合不等式的证明方法有 在集合间建立单射 利用集合阶的不等关系在集合间建立单射 利用集合阶的不等关系 定理 设X和Y都是有限集 f为从 X 到 Y 的一个映射 1 若f为单射 则 X Y 2 若f为满射 则 X Y 利用容斥原理利用容斥原理 例如 设元素 a 属于集族 12 k A AA 的k个不同集合 k iii AAA 21 则在 n i i A 1 中 a 被计算了k次 当k 2 时 集合 k iii AAA 21 两两的交集共有 2 k C个 由于 1 2 1 1 2 j nji ik AAak kk C 在故中至少少被计算了k 1 次 这样我们得到下 面的不等式 11 1 j nji ii n i i n i AAAA 组合不等式 可由容斥公式 1 1 1 11 1 i n i n j nji ii n i i n i AAAAA 删去右边第三个和式起的所有 和式得到 采用这种办法 我们可以从容斥公式得到另外一些组合不等式 只是要注意这些不等式 的方向的变化 利用抽屉原则利用抽屉原则 由于抽屉原则的结论本身就是组合不等式关系 所以我们利用抽屉原则 巧妙构造抽屉 的方法证明组合不等式 利用组合分析利用组合分析 在复杂的组合计数问题 离散极值问题等问题中 会出现一些组合不等式 这时可运用 组合分析方法证明之 经典例题 1 数 1447 1005 和 1231 有某些共同点 即每个数都是首位为 1 的四位数 且每个四位 数中恰有两个数字相同 这样的四位数共有多少个 解 符合条件的四位数必含有一个 1 或者两个 1 1 含有两个 1 的情形 从除 1 之外的其余 9 个数字中任取两个 有 2 9 C种取法 再与其中的一个 1 组成任意排 列的三位数 有 3 3 P种 这样构成的首位为 1 的四位数共有 2 19 NC 3 3 P 个 2 只含有一个 1 的情形 从其余的 9 个数字中任取两个 有 2 9 C 种取法 其中一个数字被重复选出 有 1 2 C种 这样的三 个数字组 成的三位 数共有 2 3 3 P 这样构成 的首位为 1 的 四 位 数 共 有 2 3 3 1 2 2 9 2 PCC N 个 因此 符合题意的四位数共有 12 432NNN 个 2 证明 n k nk n nn n C 0 12 2 2 2 2 分析 把 n nk k n n nk k n n k k n n k k n CCCC 2 1 2 2 1 2 2 0 2 0 2 而对于变形为 变换求和指标 证明 knjCCCCC n nk k n n nk k n n n nk k n n k k n n k k n 2 2 2 1 2 2 1 2 2 2 1 2 2 0 2 0 2 令对于和式 则 2 0 2 0 22 1 0 2 2 1 2 n n n k k n n j n n j n n j j n n nk k n CCCCCC 所以 2 2 0 2 2 0 2 n n n k k n n n k k n CCC 即 n n n n k k n CC 2 2 0 2 22 从而有 n k nk n nn n C 0 12 2 2 2 2 3 2003 年上海交大冬令营 求证 1 1 1 1 1 3 1 2 1 1 1 210 Nn Cnm C nm C m C m C m n nm n n n nnn 其中 证明证明 设 n n n nnnn C nm C m C m C m a 1 1 1 3 1 2 1 1 1 210 则由基本 恒等式 r n r n r n r n r n C n r CCCC 11 11 及得 1 1 1 3 1 2 1 1 1 1 1 1 2 2 1 1 1 1 1 2 1 0 1 1 1 0 n n n n n n n n nnnnnn C nm CC nm CC m CC m C m a 1 1 1 2 1 1 2 1 2 1 1 1 3 1 1 1 1 1 1 1 1 21 11 n nm n nnn nnnnnn Cnmmmnmnm n a mmmm a a mnmnm n a nmnm nn a nm n a aa n m aa n m aa 从而有 而 所以 即故 说明 注意到 an中各项的系数均与 n 无关 且符号正负相同 由此想到 an与 an 1 之间必定存在着某些联系 且是递推关系 4 设 212211nn BBBDAAAD 是集合 M 的两个划分 又对任何两 个不变的子集 1 njiBA ji 有 nBA ji 求证 2 2 1 nM 并说明等号能否成 立 证明 令 1 min njiBAk ji 不妨设 kAi 因 n BBB 21 两两不 交 故 n BBB 21 中至多有k个 j B使 1j AB 1j AB 2 1 knmj 由k的选取知 2 1 mjkBj 从而 1 mkB m j j 又因 1j AB 1 nmi 故 11 nBABA ii 即 knBi 所以 111 knmnmkBBBM n mj j m j j n j j 2 knmknn 若 2 n k 因 km 故 2 2 2 2 2 2 2 2 2 2 n k nn knkknnknmknnM 若 2 n k 则 2 1 2 ni n Ai 从而 2 2 11 n AAM n i i n i i 下面说明 2 2 n M 是可以取到的 显然这时n为偶数 取 4 n则8 M 令 8 7 6 5 4 3 2 1 M易验证 M 的两个划分 1 1 2 3 4 5 6 7 8 2 1 2 3 5 4 6 7 8 DD 满足题目条 件 5 某市有n所中学 第 I 所中学派出 i C名学生 niCi 1 391 来到体育馆观看球 赛 全部学生总数为 n i i C 1 1990 看台上每一横排有199个座位 要求同一学校 的学生必须坐在同一横排 问体育馆最少要安排多少横排才能保证全部学生都能坐 下 解 让学生按学校顺次入坐 每排坐满后再转入下一排 共用10排 这时有的学校学生 已坐在同一排 有的学校学生坐在两排 后一种学校至多9个 再增加两排座位 每 排可容纳5个学校 将上述 至多 9个学校移到这两排 则每个学校的学生都坐在 同一排 因此 12排足够 另一方面 1990 34 58 18 如果58个学校各有34名学生 1个学校18名学生 那么每排至多安排34名学生的学校5所 34 6 199 11排至多安排34名学生的 学校55所 所以11排是不够的 6 对 n n n Cn42 2 2 2 求证 证明 构造集合 2 22121 nnnn CaaaaaA则 表示从A中取n个元素的组合数 即由n个元素组成的 A 的真子集有 n n C2个 而 A 的所有子集数是 nnn nnnn CCCC422 2 2 2 2 1 2 0 2 个 故有 nn n C4 2 又设集合 211n aaaB 2212nnn aaaB 对于集合 B1的一个子集 设其有r个元素 若nr 则从集合 B2中任取rn 个元素 再连同取出 B1的全部元素 这种取法实际上是从集合 A 中取出n个元素的一种方式 注意到 若1rn 则从集合 B2中取出nr 个元素的方式不是惟一的 因此 集合 B1的全部子集数少于从集合 A 中取出n个元素组成的子集数 即 n n n C22 故不等式 成立 7 证明 k m C 12 是奇数 k 1 证 明 k m C 12 k k k k mmmmmm 2 2 22 1 12 21 112 22 12 令 2 it i pi 1 i k pi为奇数 则 i i tm i t i tm p p p pm i i i i i 2 2 222 它的分子 分母 均为奇数 因 k m C 12 是整数 所以它只能是若干奇数的积 即为奇数 8 对 n 2 证明 42 2 nn n n C 证明 1 当 n 2 时 2 22 4 C 6 4 2 2 假设 n k 时 有 2k k k C2 4 k 当 n k 1 时 因为 1 12 2 1 12 2 1 1 1 2 2 1 1 2 k k k k C k k kk k kk k C 又 1 12 2 2 k k 4 所以 2 k 1 1 2 1 1 22 442 kk k k k k k CCC 所以结论对一切 n 2 成立 9 若nN n 2 求证 3 1 12 n n 证 明 首 先 2 1111 1 2 210 n n nnnn n n C n C n CC n 其 次 因 为 2 1 1 1 1 1 1 1 1 1 k kkkkkkn knnn n C kk k n 所以 n n 1 1 2 3 1 3 1 1 1 3 1 2 1 2 1 1 1 2 11 2 2 nnnn C n C n n nn 得证 10 2008 年复旦 设 S 1 2