1、第五章 组合数学简介概述u组合数学是计算机出现以后迅速发展起来的一门数学分支u介绍一下组合数学在比赛中的一些应用u解组合数学题目的一般步骤 建立组合数学模型应用相关的组合数学知识，得出计算公式（经常是递推公式）。问题解决了？N考虑能否解出递推公式中的递归关系，降低时间复杂度；考虑能否得出新的公式，使得计算过程简便，计算精度提高；或做出其他的一些思考和改进。结束Y 解题方法 补集转化 v 逆向思维方法 ，应用于组合数学问题中往往有着很好的效果 v 下面通过单色三角形问题的解题探讨补集转化思想单色三角形问题v 空间里有 n个点，任意三点不共线。每两点之间都用红色或黑色线段（只有一条，非红即黑！）连
2、接。如果一个三角形的三条边同色，则称这个三角形是单色三角形。对于给定的红色线段的列表，找出单色三角形的个数v 输入点数 n、红色边数 m以及这 m条红色的边所连接的顶点标号，输出单色三角形个数 R。 3=n=1000， 0=m=25万例如右图中有 5个点， 10条边，形成 3个单色三角形单色三角形问题v 很自然想到了然后枚举所有的三角形（这是通过枚举三个顶点实现的），判断它的三条边是否同色 ，时间复杂度已经高达 O( ) v 单纯枚举不可以，组合计数是否可行？利用组合公式进行计算是非常高效的。 v 从总体上进行组合计数很难想到，尝试枚举每一个点，设法找到一个组合公式来计算以这个点为顶点的单色三
3、角形的个数 单色三角形问题v 对于枚举确定的点 A，以 A为一个顶点的单色三角形 ABC不仅要满足边 AB和边 AC同色，而且边 BC也要和 AB、 AC边同色，不可能仅仅通过枚举一个顶点 A就可以确定单色三角形v 枚举组合计数中组合公式的构造上我们遇到了障碍 v 障碍的本质是： 从一个顶点 A出发的两条同色的边 AB、 AC并不能确定一个单色三角形ABC，因为 BC边有可能不同色 单色三角形问题v 也就是说，无法在从同一个顶点出发的某两条边与所有的单色三角形之间建立一种确定的对应关系 v 换一个角度，从反面来看问题 v 三角形数 S=C(n,3) v 单色三角形数 R加上非单色三角形数 T就
4、等于S，如果可以求出 T，那么显然 R = S Tv 原问题就等价于： 怎样高效地求出 T ACB单色三角形问题v 上面分析中夭折的枚举组合计数的算法的障碍是无法在 “某两条边 ”与 “单色三角形 ”之间建立确定的对应关系 v 那么有公共顶点的某两条边与非单色三角形之间是否有着确定的关系呢？ACB非单色三角形的三条边，共有红黑两种颜色，也就是说，只能是两条边同色，另一条边异色。假设同色的两条边顶点为 A，另外两个顶点为 B和 C，则从 B点一定引出两条不同色的边 BA和 BC，同样，从 C点引出两条不同色的边 CA和 CB 单色三角形问题v 一 个非单色三角形对应着 两 对 “有公共顶点的异色边 ”v 很明显要求的非单色三角形数 T就等于所有 “有公共顶点的异色边 ”的总对数 Q的一半v ACBACB单色三角形问题v 总对数：每个顶点有 n-1条边，根据输入的信息可以知道每个顶点 i的红边数 Ei，那么其黑边数就是 n-1-Ei。枚举顶点 A，则根据乘法原理，以 A为公共顶点的异色边的对数就是Ei*(n-1-Ei)。所以 v 答案 R=S T=n*(n-1)*(n-2)/6-Q/2
