青岛市2022编程市赛 T3结论与简易证明

534 字

3 分钟

2022-08-08

首先，结论与证明来自http://oeis.org/A005732/a005732.pdf，这里给出简单翻译和加工

结论#

给出结论，在一个圆上取 $n$ 个点相连，构成的三角形个数为 $C_{n+3}^6+C_{n+1}^5+C_n^5$

如何证明呢，我们不妨从圆上n个点中的任意个可以构成几个三角形来入手，我们先看7个点的图，来观察一下!

如果你有十足的耐心的话，你可以数出来，这是 $287$ 个三角形

但是，我们要求出一个通项公式，我们可以发现，每一个三角形都是由多个或 $0$ 个圆上的点组成的，让我们通过这个分类讨论

首先tips：认识到圆“上”的概念：就是在圆的边上

由圆上 $3$ 个点构成的三角形有 $C_n^3$ 个。证明：圆上每三个点可以构成一个三角形，反之亦然.（这个不用画图了吧qwq）
只由圆上 $2$ 个点和另外 $1$ 个点构成的三角形个数有 $4 \times C_n^4$ 个。证明：对于圆上的每 $4$ 个点，可以构成 $4$ 个”有 $2$ 个点在圆上” 的三角形
只由圆上 $1$ 个点和另外 $2$ 个点构成的三角形个数有 $5 \times C_n^5$ 个。证明：对于圆上的每 $5$ 点，可以构成 $5$ 个”有 $1$ 个点在圆上” 的三角形
只由圆上 $0$ 个点和另外 $3$ 个点构成的三角形个数有 $C_n^6$ 个。证明：对于圆上的每 $6$ 点，可以构成 $1$ 个”有 $0$ 个点在圆上” 的三角形（当然，这个图里还有别点之间的的连线，只不过我懒得画了emmmm）