青島市2022編程市賽 T3結論與簡易證明

首先，結論與證明來自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）

最後，就是整理這個式子了（挺複雜的 qwq）（參考this）

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

\therefore C_n^3 + 4 \times C_n^4 + 5 \times C_n^5 + C_n^6

=C_n^3 + 4 \times C_n^4 + 4 \times C_n^5 + C_n^5 + C_n^6

= C_n^3 + 4 \times C_{n+1}^5 + C_{n+1}^6

=C_n^3 + 3 \times C_{n+1}^5 + C_{n+1}^5 + C_{n+1}^6

=C_n^3 + 3 \times C_{n+1}^5 + C_{n+2}^6

=C_n^3 + C_{n+1}^5 + 2 \times C_{n+1}^5 + C_{n+2}^6

=C_n^3 + C_n^4 + C_n^5 + 2 \times C_{n+1}^5 + C_{n+2}^6

=C_{n+1}^4 + C_n^5 + 2 \times C_{n+1}^5 + C_{n+2}^6

=C_{n+2}^5 + C_{n+2}^6+C_n^5+C_{n+1}^5

=C_{n+3}^6 + C_n^5+C_{n+1}^5