No. Of possible triangles

Question

If there are n line segments in a plane of lengths (1,2,3,....,N) then find the no. of triangles that can be formed from these.

Attempt: let the sides be X,Y,Z such that X < Y< Z then the cardinality of required set boils down to finding out pairs such that X + Y > Z other two inequalities are automatically satisfied. Then I drew a table for values of X,Y and Z such that the above conditions hold.And now the solution becomes clumsy and lengthy. Is there a better way? And even in this approach for Z = n , I have (n-2)*(n-3)/2 solutions. And now this n can be anything from 4 to N. So I summed this again. But the problem is I am missing many things answer is different for odd and even values of N. What's wrong with my solution. It doesn't match with the correct answer.

Answer 1

If $X<Y<Z$ and $X+Y>Z$,

$$Z+1\le X+Y\le Y-1+Y$$

and hence

$$Y\ge \frac{Z}{2}+1$$

The number of triangles is

\begin{align} \sum_{Z=4}^N\sum_{Y=\lfloor \frac{Z}{2}\rfloor+1}^{Z-1}\sum_{X=Z-Y+1}^{Y-1}1&=\sum_{Z=4}^N\sum_{Y=\lfloor \frac{Z}{2}\rfloor+1}^{Z-1}(Y-1-Z+Y)\\ &=\sum_{Z=4}^N\sum_{Y=\lfloor \frac{Z}{2}\rfloor+1}^{Z-1}(2Y-Z-1)\\ \end{align}

Note that

\begin{align} \sum_{Y=a}^{Z-1}(2Y-Z-1)&=2\left(\frac{Z-a}{2}\right)(a+Z-1)-(Z-a)(Z+1)\\ &=(Z-a)(a-2)\\ \end{align}

So, the number of triangles is

\begin{align} \sum_{Z=4}^N(Z-\lfloor \frac{Z}{2}\rfloor-1)(\lfloor \frac{Z}{2}\rfloor+1-2)=\sum_{Z=4}^N(Z-\lfloor \frac{Z}{2}\rfloor-1)(\lfloor \frac{Z}{2}\rfloor-1)\\ \end{align}

If $N$ is even,

\begin{align} &\;\sum_{Z=4}^N(Z-\lfloor \frac{Z}{2}\rfloor-1)(\lfloor \frac{Z}{2}\rfloor-1)\\ =&\;\sum_{k=2}^{N/2}(2k-\lfloor \frac{2k}{2}\rfloor-1)(\lfloor \frac{2k}{2}\rfloor-1)+\sum_{k=2}^{(N-2)/2}(2k+1-\lfloor \frac{2k+1}{2}\rfloor-1)(\lfloor \frac{2k+1}{2}\rfloor-1)\\ =&\;\sum_{k=2}^{N/2}(k-1)(k-1)+\sum_{k=2}^{(N-2)/2}k(k-1)\\ =&\;\sum_{i=1}^{(N-2)/2}i^2+\sum_{i=1}^{(N-4)/2}i^2+\sum_{i=1}^{(N-4)/2}i\\ =&\;2\left(\frac{1}{6}\right)\left(\frac{N-4}{2}\right)\left(\frac{N-4}{2}+1\right)(N-4+1)+\left(\frac{N-2}{2}\right)^2\\ &\qquad+\frac{1}{2}\left(\frac{N-4}{2}\right)\left(\frac{N-4}{2}+1\right)\\ =&\;\frac{1}{12}(N-2)(N-3)(N-4)+\frac{1}{4}(N-2)^2+\frac{1}{8}(N-2)(N-4)\\ =&\;\frac{1}{24}(N-2)[2(N-3)(N-4)+6(N-2)+3(N-4)]\\ =&\;\frac{1}{24}N(N-2)(2N-5) \end{align}

If $N$ is odd, $N-1$ is even. So,

\begin{align} &\;\sum_{Z=4}^N(Z-\lfloor \frac{Z}{2}\rfloor-1)(\lfloor \frac{Z}{2}\rfloor-1)\\ =&\;\frac{1}{24}(N-1)(N-1-2)[2(N-1)-5]+(N-\lfloor \frac{N}{2}\rfloor-1)(\lfloor \frac{N}{2}\rfloor-1)\\ =&\;\frac{1}{24}(N-1)(N-3)(2N-7)+(N-\frac{N-1}{2}-1)(\frac{N-1}{2}-1)\\ =&\;\frac{1}{24}(N-1)(N-3)(2N-7)+\frac{1}{4}(N-1)(N-3)\\ =&\;\frac{1}{24}(N-1)(N-3)(2N-7+6)\\ =&\;\frac{1}{24}(N-1)(N-3)(2N-1) \end{align}

Answer 2

$$\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{\min(i+j-1,n)}1=\sum_{i=2}^{n-2}\sum_{j=i+1}^{n-1}\min(i-1,n-j)$$

I wrote a program to generate data. Then, using this tool, this approximately sums to:- $$ \lfloor-0.0604688766 n^3+ 0.416618635 n^2 -0.374999769 n + 0.0833333333+0.5\rfloor$$

Explanation: $i$, $j$ and $k$ are the three sides of the triangle, such that $i<j<k$. Since $k\le n$, $j\le n-1$ and $i\le n-2$. Also triangle law mandates $i+j>k\implies k\le i+j-1$