组合数学1

概述

组合数学在生活中处处可见。计算单循环、双循环赛制下比赛的场数、构造幻方、一笔画、计算扑克牌游戏中满堂红牌的手数，概率等。

扎根于数学游戏和娱乐中，计算机技术的发展促进了其发展。

解决两类问题：

排列的存在性问题（这是根本性问题。排列集合中的某些元素使其满足某些条件，其排列的存在性并非总是显而易见的，若不存在，那么什么条件下会存在）；

排列的计数和分类问题。（若存在，则会有多种方法实现，需要计数，并将其分类）。

一、棋盘的完美覆盖问题

二、切割立方体

三、幻方：

3阶幻方（15） 4阶幻方（34）

8 1 6 16 3 2 13

3 5 7 5 10 11 8

4 9 2 9 6 7 12

4 15 14 1

四、四色问题

五、36军官问题

来自6个军团的6个军衔的军官，排成方阵，要求每行每列都有各种军衔的军官1名，并且每行每列的军官都是来自不同的军团。

六、最短路径问题

组合优化的问题。（路由选择）

七、Nim取子游戏

鸽笼原理（抽屉原则）

一、简单形式

：把n+1个物体放入n个盒子中，有一个盒子中至少有2个物体。

证明方法：反证法。

鸽笼原理与反证法的关系，类似于不完全归纳法与数学归纳法的关系。

例1 13个人中至少有两个人的生日在同一个月。

例2 有n对夫妇，至少选择多少个人，才能保证至少有一对夫妇被选出？

变化形式：

把n个物体放入n个盒子中，每一个盒子中至少有1个物体，那么每一个盒子恰好有1个物体。

把n个物体放入n个盒子中，每一个盒子中至多有1个物体，那么每一个盒子恰好有1个物体。

例3 整数列a1，a2，〃〃〃〃〃〃，am中，一定有若干个连续的数的和能被m整除。

构造ijjiab1，构造所有被m除所得余数的鸽笼，共有m个

若两个bi被m除的余数相同，则其差能被m整除，现在笼子多一个，不用考虑余数为0的情况（此时已经满足要求）

例4 大师11周训练，每天至少下一盘，每周不超过12盘，证明：有连续的若干天，刚好下了21盘棋。

第一部分：组合数学

第一章 计数的基本原则

一． 组合数学的历史和内容

1. 历史：组合数学最早起源于中世纪的印度，在漫长的历史中，一

直发展缓慢。随着上一世纪计算机的出现，组合数学开始快速地

发展。近几年，由于计算机安全领域受到重视以及组合数学在计

算机安全领域的应用，组合数学受到越来越多的重视。

2. 内容：组合数学主要包括以下几个内容：

(1) 组合分析（也称为组合计数理论）

(2) 组合优化（包括线性规划，整数规划等）

(3) 组合设计（包括区组设计等）

(4) 组合算法（例如：搜索算法，DFS算法与分支定界法，动态规

划等）

*图论本是组合数学这个家族的一个主要成员，但它已成长壮大，独

立成一门学科。

3. 本课程介绍的主要内容：组合计数理论

二．加法原则与乘法原则

1. 加法原则：

设事件A有m种产生方式，事件B有n种产生方式，则“事件A

或事件B”有m+n种产生方式。

例子：大于0而小于10的偶数有4个，即：{2，4，6，8}，大于0

而小于10的奇数有5个，即：{1，3，5，7，9}。则大于0而小于10的整数有：4+5=9个，即：{1，2，3，4，5，6，7，8，9}。

*如果A1,A2,⋯,An是互不相交的有穷集，那么 |A1∪A2∪⋯∪An|=|A1|+|A2|+⋯+|An| 2.乘法原则：

若事件A有m种产生方式，事件B有n种产生方式，则“事件A

与事件B”有mn种产生方式。

例1：设一个符号由两个字符组成，第一个字符有a,b,c,d,e五种方式，

第二个字符有1,2,3三种方式。则根据乘法原则，该符号具有5×3=

15种方式，即 a1,b1,c1,d1,e1;a2,b2,c2,d2,e2;a3,b3,c3,d3,e3.

例2：从A到B有3条不同的道路，从B到C有2条不同的道路，从

A经B到C共有n=3×2=6条不同的道路。

例3：求比10000小的正整数中含有数字1的数的个数。

解：先求所有4位数中不含有数字1的个数，即求由{0，2，3，4，5，

1 第一章 排列组合

1、 在小于2000的数中，有多少个正整数含有数字2？

解：千位数为1或0，百位数为2的正整数个数为：2*1*10*10；

千位数为1或0，百位数不为2，十位数为2的正整数个数为：2*9*1*10；

千位数为1或0，百位数和十位数皆不为2，个位数为2的正整数个数为：2*9*9*1；

故满足题意的整数个数为：2*1*10*10+2*9*1*10+2*9*9*1＝542。

2、 在所有7位01串中，同时含有“101”串和“11”串的有多少个？

解：（1） 串中有6个1：1个0有5个位置可以插入：5种。

（2） 串中有5个1，除去0111110，个数为62-1＝14。

（或：4142*2＝14）

（3）串中有4个1：分两种情况：①3个0单独插入，出去1010101，共53-1种；②其中两个0一组，另外一个单独，则有2*)2,2(4152P种。

（4）串中有3个1：串只能为**1101**或**1011**，故共4*2种。

所以满足条件的串共48个。

3、一学生在搜索2004年1月份某领域的论文时，共找到中文的10篇，英文的12篇，德文的5篇，法文的6篇，且所有的都不相同。如果他只需要2篇，但必须是不同语言的，那么他共有多少种选择？

解：10*12+10*5+10*6+12*5+12*6+5*6

4、设由1，2，3，4，5，6组成的各位数字互异的4位偶数共有n个，其和为m。求n和m。

解：由1，2，3，4，5，6组成的各位数字互异，且个位数字为2，4，6的偶数均有P(5,3)=60个，于是：n = 60*3 = 180。

以a1,a2,a3,a4分别表示这180个偶数的个位、十位、百位、千位数字之和，则

m = a1+10a2+100a3+1000a4。

因为个位数字为2，4，6的偶数各有60个，故 a1 = (2+4+6)*60=720。

组合数学排列组合（1）格路模型，范德蒙德恒等式

1.排列(permutation)： 从n个不同的元素中，取出r个不重复的元素，按次序排列，称为从n个中取r个的⽆重排列。

排列的个数⽤P(n,r)表⽰或Prn n>=r //⾼中的时候教材教我们Arn ，跟这⾥的⼀样。 P(n,r) = n!/r! 排列的基本问题是“n个不同球放r个不同盒”问题。2.组合(conmutation)： 从n个不同的元素中，取出r个不重复的元素组成⼀个⼦集⽽不考虑其元素的顺序，称为从n个中取r个的⽆重组合。

组合的个数⽤C(n,r)表⽰或Crn n>=r

C(n,r)=n! / [r!*(n-r)!] 组合的基本问题是“n个不同球放r个相同盒”问题。 两个性质： |—— C(n,r) = C(n,n-r) //C(8,3)=C(8,5) |—— C(n,l)*C(l,r) = C(n,r)*C(n-r,l-r) //C(9,5)*C(5,2)=C(9,2)*C(7,3) 3.格路模型与组合恒等式：组合数学有⼀个研究⽅向就是研究组合恒等式。 格路模型

我们把从（0，0）到（m，n）的路径⽤⼀个形如“xxyxyyxy...xyy”的字符串表⽰。则字符串长度为m+n，有m个‘x’，n个‘y’。 杨辉三⾓⽤于格路模型

在杨辉三⾓中，第n⾏对应着(a+b)n的系数，第n⾏第r列的数值是C(n,r)

范德蒙德恒等式