For an equilateral triangle with $n$ dots on a side, how many lines are needed to connect each dot to every other dot?

Question

For an equilateral triangle of side length $n$ dots, as shown in this diagram below, construct a function, $f(n)$, which outputs the number of lines needed to connect up every dot to every other dot. A straight line through three or more dots counts as only one line! E.g. $f(3) = 9$ and $f(4) = 24$.

Can anyone point me in the right direction with this problem? Perhaps tell me what area of mathematics or what concepts would help me solve this? If this is a trivial problem don't give the answer but tell let me know. Thanks.

Answer 1

For a side of $m$ dots there are a total of $n=\frac 12m(m+1)$ dots. There are then $\frac 12n(n-1)$ pairs of dots. If you have a line with $k \gt 2$ dots on it, it accounts for $\frac 12k(k-1)$ of the pairs of dots, so it reduces the count by $\frac 12k(k-1)-1$

We can see this for the order $4$ triangle. There are $10$ points, three lines with four points (the sides) and three lines with three points. The number of lines is then $\frac 12\cdot 10 \cdot 9 - 3(\frac 12\cdot 4 \cdot 3-1)-3(\frac 12 \cdot 3 \cdot 2 -1)=45-3\cdot 5 -3 \cdot 2=24$

If we do the order $5$ triangle we have $15$ dots, three lines with five dots, three with four dots, and six with three dots. The new ones with three dots run from a corner through the center to the middle of the other side. This gives $\frac 12\cdot 15\cdot 14-3\cdot 9-3\cdot 5 -6\cdot 2=51$ lines

This gives sequence A244504 which begins $$3, 9, 24, 51, 102, 177, 294, 459, 690, 987, 1380, 1875, 2508, 3279, 4212, 5319, 6648, 8199, 10026, 12141, 14580, 17343, 20496, 24051, 28068, 32547, 37542, 43071, 49218, 55983, 63456, 71661, 80658, 90447, 101100, 112635, 125160, 138675, 153252, 168915, 185784$$

No closed formula is given.

Answer 2

Here's a solution for the problem described, i.e. if the shape is an equilateral triangle whose sides are $n$ equally spaced dots. This is assuming the dots along the sides of the triangle are the only dots.

First, count the number of dots. There are $n$ dots along one edge, with one of those dots being shared with the other two edged. Then, there are $n-1$ new dots along a second edge, with one of those shared with the final edge. Finally, there are $n-2$ dots remaining on the third edge. This gives a total of $n+(n-1)+(n-2) = 3(n-1)$ dots.

The number of edges connecting two dots is then $\binom{3(n-1)}{2} = \frac{3(n-1)(3n-4)}{2}$. However, along each side of the triangle, there are $\binom{n}{2} = \frac{n(n-1)}{2}$ edges along the same line. So, we need to subtract all but one of these (the edge connecting the corners) for each side, totaling $3[\binom{n}{2}-1] = \frac{3(n+1)(n-2)}{2}$.

Thus, the total number of necessary lines is $$ f(n) = \binom{3(n-1)}{2}-3\left[\binom{n}{2}-1\right] = 3(n^2-3n+3) $$

This gives $f(2) = 3, f(3) = 9, f(4) = 21, f(5) = 39$ and so on.