青島市2022プログラミング市大会 T3結論と簡易証明

まず、結論と証明はhttp://oeis.org/A005732/a005732.pdfから来ています。ここで簡単な翻訳と加工を示します。

結論#

結論を示します。円上に $n$ 個の点を取り、それをつなげることで構成される三角形の数は $C_{n+3}^6+C_{n+1}^5+C_n^5$ です。

どうやって証明するのでしょうか。円上の n 個の点から任意の個を選んでいくつの三角形を構成できるかを考えてみましょう。まず 7 個の点の図を見て、観察してみましょう！

もし十分な忍耐があれば、これは $287$ 個の三角形であることがわかります。

しかし、一般項の公式を求める必要があります。私たちは、各三角形が複数または $0$ 個の円上の点から構成されていることに気づくことができます。これを分類して考えてみましょう。

まずのヒント：円「上」の概念を理解すること：円の辺にあるということです。

円上の $3$ 個の点から構成される三角形の数は $C_n^3$ です。証明：円上の任意の 3 点は三角形を構成でき、逆もまた然りです。（この図は描く必要はないでしょう qwq）
円上の $2$ 個の点と他の $1$ 個の点から構成される三角形の数は $4 \times C_n^4$ です。証明：円上の任意の $4$ 点からは、$2$ 点が円上にある三角形を $4$ つ構成できます！
円上の $1$ 個の点と他の $2$ 個の点から構成される三角形の数は $5 \times C_n^5$ です。証明：円上の任意の $5$ 点からは、$1$ 点が円上にある三角形を $5$ つ構成できます！
円上の $0$ 個の点と他の $3$ 個の点から構成される三角形の数は $C_n^6$ です。証明：円上の任意の $6$ 点からは、$0$ 点が円上にある三角形を $1$ つ構成できます！（もちろん、この図には他の点同士の連結線もありますが、描くのが面倒でした 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