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个点,其中没有三个点共线。每两个点用红色或兰色线段连接。如果一个三角形的三条边同色,则称这个三角形是单色三角形。对于给定红色线段的列表,希望能找出单色三角形的个数。