3
$\begingroup$

On a circle there are $n$ evenly spaced points (i.e., they form a regular polygon). How many triangles can be formed when congruent triangles are considered the same?

This question is closely related to How many triangles can be formed by the vertices of a regular polygon of $n$ sides?, but here congruent triangles are considered to be the same.

$\endgroup$
3
  • $\begingroup$ Have you attempted any examples for small $n$? Do you see a pattern? For each triangle type, can you find a standard form for that triangle? $\endgroup$ Jun 16 at 23:10
  • $\begingroup$ for n=3,4, clearly 1; for n=5, should be 2; for n=6, should be 3; etc. I think n=12 (clock), it should be 12, but I am not sure $\endgroup$
    – maomao
    Jun 16 at 23:31
  • $\begingroup$ oeis.org/A001399 $\endgroup$
    – bof
    Jun 17 at 0:13
3
$\begingroup$

For each triangle $A_iA_jA_k$, the angles $\angle A_iOA_j$, $\angle A_jOA_k$ and $\angle A_kOA_i$ are respectively equal to $|j-i|\frac{2\pi}{n}$, $|j-k|\frac{2\pi}{n}$ and $|k-i|\frac{2\pi}{n}$ with $1\le i\ne j\ne k \le (n-1)$.

Let denote $$ \begin{cases} x=|j-i|\\ y=|k-j|\\ z=|k-i| \end{cases} $$

Then $$ \begin{cases} x+y+z = n \\ x,y,z \in \Bbb N^* \\ \end{cases} \tag{1} $$

The number of triangles when congruent triangles are considered the same is equal to the number of solutions of $(1)$ (Two solutions that differ only in the order of their summands are considered the same, for example, with $n = 4$: $1+1+2$ is the same as $2 +1 +1$).

The problem $(1)$ is solved here and the number of solutions of $(1)$ is the number of partitions $p(3,n)$ of $n$ into $3$ non-zero parts. The number of partitions $p(k,n)$ satisfies $$ \begin{cases} p(0,0) &= 0 \\ p(k,n) &= p(k,n-k)+ p(k-1,n-1) & \text{otherwise}. \\ \end{cases} \tag{2} $$ Remark: It seems that the recurrent formula in the answer is not correct, the recurrent formula $(2)$ is taken from the wikipedia here. From $(2)$, we can deduce the general formula of $p(3,n)$ as follows

  • For $k = 1$, it's obvious that $$p(1,n) = 1$$
  • For $k =1$, we have $$p(2,n) = p(2,n-2)+1 =... \implies p(2,n) = \left\lfloor \frac{n}{2} \right\rfloor$$
  • For $k = 3$, we have $$p(3,n) =p(3,n-3)+\left\lfloor \frac{n-1}{2} \right\rfloor=...$$

$$ \begin{align} \implies p(3,n) &=\left\lfloor \frac{n-1}{2} \right\rfloor+\left\lfloor \frac{n-4}{2} \right\rfloor+...+\left\lfloor \frac{n-1-3i}{2} \right\rfloor+... \\ & =\sum_{0 \le i \le \left\lfloor \frac{n-1}{3}\right\rfloor}\left\lfloor \frac{n-1-3i}{2} \right\rfloor \end{align} $$

Hence, the number of triangles is equal to $$p(3,n)=\sum_{0 \le i \le \left\lfloor \frac{n-1}{3} \right\rfloor}\left\lfloor \frac{n-1-3i}{2} \right\rfloor$$

Remark: The last steps have a lot of calculation, please feel free to correct if you find any mistake.

$\endgroup$
3
  • $\begingroup$ $$\left\lfloor\frac{n^2+3}{12}\right\rfloor$$ $\endgroup$
    – bof
    Jun 17 at 0:54
  • $\begingroup$ @bof: does your formula come from oeis.org/A001399 ? If yes, perhaps, there is a way to simplify my formula to yours and a proof by recurrence will work. $\endgroup$
    – NN2
    Jun 17 at 0:58
  • $\begingroup$ The formula in my comment is from my notebook from a combinatorics class I took many years ago. It was homework and I think I proved it by cases: $n\equiv0\pmod6$, $n\equiv1\pmod6$, etc. $\endgroup$
    – bof
    Jun 17 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.