1、组合数学组合数学简介 组合数学起源于古老的数学娱乐和游戏。而在当今社会中同样发挥着重要的作用。 组合数学研究一个集合的物体进行满足一些规则的排列。具体的说，组合数学研究的是这些排列的存在性、计数和分类。 在 ACM/ICPC中用到的组合数学知识有：一一对应原理、加法乘法原理、多重集排列和组合、排列生成、递推关系、母函数、鸽巢原理、容斥原理、群和置换群、贝恩塞特引理和波利亚定理一一对应原理 “ 一一对应 ” 概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。 如我们说 A集合有 n个元素 |A|=n， 无非是建立了将 A中元与 1,n元一一对应的关系。 在组合计数时往往借助于一一对应实
2、现模型转换。 比如要对 A集合计数，但直接计数有困难，于是可设法构造一易于计数的 B， 使得A与 B一一对应。 例 在 100名选手之间进行淘汰赛 (即一场的比赛结果，失败者退出比赛 ),最后产生一名冠军，问要举行几场比赛？一一对应例 含有 n个元素的集合的所有子集个数为 2n解 一种常见的思路是按轮计场，费事。另一种思路是 淘汰的选手 与 比赛 (按场计 )集 一一对应 。 99场比赛。一一对应例：求集合 1,2,n 的不含相邻整数的k元子集的个数。分析：每个满足条件的 k元子集都和一个 01有序串对应，且这个有序串没有两 1相邻。这样的串含有 k个 1，每个 1前面的 0的个数是不同，又与
3、 0,1, n-k中选 k个不同的元素对应。所以结果 =c(n-k+1,k) 某机要部门安装了电子锁。 M(M8)工作人员每人发一张磁卡，卡上有开锁的密码特征。为了保证安全，规定至少要有 N(N5)个人同时使用各自的磁卡才能将所打开。现在需要计算一下，电子锁至少要有多少种特征，每个人的磁卡上至少有几个特征。一一对应（下午讨论）加法乘法原理 加法原理 把事情分成 N类，每类有 Ci种做法，则该事情共有 C1+C2+CN 种做法 乘法原理 把事情分成 N步，每步有 Ci种做法，则该事情共有 C1*C2*CN 种做法 例 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18 + 10
4、 = 28 人。 例 北京每天直达上海的客车有 5 次，客机有 3 次， 则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。例 某种字符串由两个字符组成，第一个字符可选自 a， b， c， d， e， 第二个字符可选自 1， 2， 3，则这种字符串共有 5 3 = 15 个。例 从 A到 B有三条道路，从 B到 C有两条道路，则从 A经 B到 C有 32=6 条道路。加法乘法原理的应用 单色三角形（来源于 POI)给定空间里的 n个点，其中没有三个点共线。每两个点用红色或兰色线段连接。如果一个三角形的三条边同色，则称这个三角形是单色三角形。对于给定红色线段的列表，希望能找出单色三角形的个数。
