histcat

histcat

Qingdao City 2022 Programming Municipal Competition T3 Conclusion and Simple Proof

First, the conclusion and proof come from http://oeis.org/A005732/a005732.pdf, here is a simple translation and processing

Conclusion#

The conclusion is that the number of triangles formed by connecting $n$ points on a circle is $C_{n+3}^6+C_{n+1}^5+C_n^5$

Proof#

How do we prove this? Let's start by considering how many triangles can be formed from any number of points among the $n$ points on the circle. We first look at the diagram with 7 points to observe! pic1

If you have plenty of patience, you can count that there are $287$ triangles.

However, we want to derive a general formula. We can observe that each triangle is composed of multiple or $0$ points on the circle, so let's categorize this discussion.

Classifying Cases#

First, a tip: recognize the concept of "on the circle": it means on the edge of the circle.

  1. The number of triangles formed by $3$ points on the circle is $C_n^3$. Proof: Any three points on the circle can form a triangle, and vice versa. (No need to draw a diagram for this, right? qwq)
  2. The number of triangles formed only by $2$ points on the circle and $1$ other point is $4 \times C_n^4$. Proof: For every $4$ points on the circle, $4$ triangles can be formed "with $2$ points on the circle" p2
  3. The number of triangles formed only by $1$ point on the circle and $2$ other points is $5 \times C_n^5$. Proof: For every $5$ points on the circle, $5$ triangles can be formed "with $1$ point on the circle" p3
  4. The number of triangles formed only by $0$ points on the circle and $3$ other points is $C_n^6$. Proof: For every $6$ points on the circle, $1$ triangle can be formed "with $0$ points on the circle" p4 (Of course, this diagram also includes connections between other points, but I was too lazy to draw them emmmm)

Organizing Cases#

Finally, we need to organize this expression (it's quite complex qwq) (reference 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
Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.