1. 1. 结论
  2. 2. 证明
    1. 2.1. 推柿子
    2. 2.2. 整理柿子

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

结论

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

证明

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

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

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

推柿子

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

  1. 由圆上 33 个点构成的三角形有 Cn3C_n^3 个。证明:圆上每三个点可以构成一个三角形,反之亦然.(这个不用画图了吧qwq)
  2. 由圆上 22 个点 和另外 11 个点 构成的三角形个数有 4×Cn44 \times C_n^4 个。证明:对于圆上的每 44 个点,可以构成 44 个"有 22 个点在圆上" 的三角形 p2
  3. 由圆上 11 个点 和另外 22 个点 构成的三角形个数有 5×Cn55 \times C_n^5个。证明:对于圆上的每 55 点,可以构成 55 个"有 11 个点在圆上" 的三角形 p3
  4. 由圆上 00 个点 和另外 33 个点 构成的三角形个数有 Cn6C_n^6个。证明:对于圆上的每 66 点,可以构成 11 个"有 00 个点在圆上" 的三角形 p4(当然,这个图里还有别点之间的的连线,只不过我懒得画了emmmm)

整理柿子

最后,就是整理这个式子了(挺复杂的qwq)(参考this

Cn+1m=Cnm+Cnm1\because C_{n+1}^m = C_{n}^m + C_{n}^{m-1}

Cn3+4×Cn4+5×Cn5+Cn6\therefore C_n^3 + 4 \times C_n^4 + 5 \times C_n^5 + C_n^6

=Cn3+4×Cn4+4×Cn5+Cn5+Cn6=C_n^3 + 4 \times C_n^4 + 4 \times C_n^5 + C_n^5 + C_n^6

=Cn3+4×Cn+15+Cn+16= C_n^3 + 4 \times C_{n+1}^5 + C_{n+1}^6

=Cn3+3×Cn+15+Cn+15+Cn+16=C_n^3 + 3 \times C_{n+1}^5 + C_{n+1}^5 + C_{n+1}^6

=Cn3+3×Cn+15+Cn+26=C_n^3 + 3 \times C_{n+1}^5 + C_{n+2}^6

=Cn3+Cn+15+2×Cn+15+Cn+26=C_n^3 + C_{n+1}^5 + 2 \times C_{n+1}^5 + C_{n+2}^6

=Cn3+Cn4+Cn5+2×Cn+15+Cn+26=C_n^3 + C_n^4 + C_n^5 + 2 \times C_{n+1}^5 + C_{n+2}^6

=Cn+14+Cn5+2×Cn+15+Cn+26=C_{n+1}^4 + C_n^5 + 2 \times C_{n+1}^5 + C_{n+2}^6

=Cn+25+Cn+26+Cn5+Cn+15=C_{n+2}^5 + C_{n+2}^6+C_n^5+C_{n+1}^5

=Cn+36+Cn5+Cn+15=C_{n+3}^6 + C_n^5+C_{n+1}^5