关于 单色三角形 为什么红黑相乘得出♨

题目:

平面上有n个点,每两个点之间都有一条红色或者是黑色的线段,任意三点均不共线。

现在,已知哪些点之间连的线段是红色的,剩下的线段都是黑色的,要求计算这些点组成的三角
形中有多少是同色的(顶点编号从1到n)?

思路:

${R_i}$为第${i}$个点红色边的数量

结果就是 $C_{3}^{n}$${-}$$sum_{i=1}^{n}{R_i*(n-R_i-1)}$${/2}$

很多题解都已经说过,但是看了很久没有人解释下为什么:

异色三角形的数量就是:$sum_{i=1}^{n}{R_i*(n-R_i-1)}$${/2}$

由 ${R_i}$为第${i}$个点红色边的数量,可知第${i}$个点黑色边的数量为${(n-R_i-1)}$,我们设为${B_i}$

于是乎,一条红边+一条黑边+任意边 即可组成一个异色三角形

于是就会出现两种情况:

1. 红边+红边+黑边

2. 红边+黑边+黑边

我们从情况1入手:

按顺时针顺序来:

1号点构成的异色三角形为 bca

2号点构成的异色三角形为 abc

3号点构成的异色三角形为 cab

我们得出了计算出了3个三角形,但是可以看到每条边被重复利用了3次,所以实际上只有1个异色三角形

那么回到公式,每一个点构成的异色三角形数量为:${R_i*B_i}$

那么1号点计算为:0

那么2号点计算为:1

那么3号点计算为:1

如此可以知道,每一个异色三角形中只有2个点是被总计到的,也就是每条边真正被计算的只有2次

于是在最终统计完后,我们只需要将$sum_{i=1}^{n}{R_i*(n-R_i-1)}$除以2即可

原文地址:https://www.cnblogs.com/caibingxu/p/13790058.html