# Thread: Number of possible triangles

1. Originally Posted by jashansinghal
Guys,
I didnt get this formula and how to use it. Secondly , the series which you gave , I cannot make head or tail out of it. Can you tell me this thing in a simpler way because I need to solve this question urgently. Please help guys.
I guess by series you meant sequence(s). Also, you didn't bother to address how your question should be interpreted. The elements are side lengths I suppose? Is 1-1-1 a valid option, or do the side lengths have to be distinct?

simplependulum's formula was gotten through pretty advanced means and you're probably better off just seeing how to list them out, like Wilmer demonstrated. There's really no need to use the formula since the values are already given by Wilmer. But if you want to know what the symbols mean, google binomial coefficient and floor function.

2. Originally Posted by jashansinghal
Guys,
I didnt get this formula and how to use it. Secondly , the series which you gave , I cannot make head or tail out of it. Can you tell me this thing in a simpler way because I need to solve this question urgently. Please help guys.
First, did you look at the suggested link by SPendulum: id:A002623 - OEIS Search Results

Next, you were asked to CLARIFY your problem; what does "3 elements" mean?
like, can 1,1,1 be used for a triangle? Or must all sides be different?

3. 1-1-1 cannot be use cause we can only use one element only once. And the 3 elements should be distinct and should form a valid geometrical triangle.

4. Originally Posted by jashansinghal
1-1-1 cannot be use cause we can only use one element only once. And the 3 elements should be distinct and should form a valid geometrical triangle.
Well, SPendulum gave you the CORRECT formula; it can also be written like this (C means Choose):
[2 * nC3 - nC2 + INT(n/2)] / 4 where n > 2

If n=10, substitute that in equation and answer will be 50
If n=20, substitute that in equation and answer will be 525

So answer to your problem is 525 - 50 = 475

If you can't follow that formula, not much can be done here.

5. what does INT (n/2) mean?
And does nC3 mean combination?

6. Originally Posted by jashansinghal
what does INT (n/2) mean?
And does nC3 mean combination?
INT means integer portion; like INT(22/5) = 4 (not 4.4)

nC3 = combination : example: 10C3 = 120

7. Can you please provide me with an easy proof to this formula?

8. Originally Posted by jashansinghal
Can you please provide me with an easy proof to this formula?
I wrote:

Originally Posted by undefined
simplependulum's formula was gotten through pretty advanced means and you're probably better off just seeing how to list them out, like Wilmer demonstrated.
Of course sometimes theorems with difficult derivations have easy proofs, but in this case I don't see one.

9. Originally Posted by jashansinghal
Can you please provide me with an easy proof to this formula?
I believe the formula is correct and my proof is briefly described in post#12 , for any z not exceeding n , count the possible lattice points (x<z,y<z) with contraints provided . If you have learnt Linear Programming , you will be familiar with this , but anyway i believe there is another easy proof as you desire ,I guess the technique is using bijection ?

10. Originally Posted by simplependulum
I believe the formula is correct and my proof is briefly described in post#12 , for any z not exceeding n , count the possible lattice points (x<z,y<z) with contraints provided . If you have learnt Linear Programming , you will be familiar with this , but anyway i believe there is another easy proof as you desire ,I guess the technique is using bijection ?
Well simplependulum makes it sound easy, but I don't think I'm up for that; I'll try a different approach.

We can look for a recurrence relation; we will express T(n) in terms of T(n-1).

It is easy to verify that T(1)=T(2)=T(3)=0 and T(4)=1. So let's find the recurrence for n>4.

We will reason this way: T(n) - T(n-1) is going to count precisely those triangles that have n as the longest side. Why? Because if the longest side is less than n, then it is already counted in T(n-1). So let's count the triangles that have n as longest side, starting with n=5.

S(5)={1,2,3,4,5}

Let's call the shortest side a and the middle side b. Fix b=4=n-1. Then the triangle inequality tells us that $a+b>n \Rightarrow a>n-b = n-(n-1) = 1$. So possible a are {2,3}. What if we try to fix b=3? Then the inequality becomes $a>n-(n-2)=2$ and there are no possible a. So T(5) - T(4) = 2, as expected. (It's expected because we already listed out all the values earlier in this thread.)

Examine S(6)={1,2,3,4,5,6}. Fix b=5. Then a is in {2,3,4}. Fix b=4. Then a is in {3}. So T(6) - T(5) = 4, as expected.

If you continue the pattern you will notice we either have a sum of the form 2 + 4 + ... + (n-3) if n is odd or 1 + 3 + ... + (n-3) if n is even. So

if n odd, write n=2k+1, and we have

$\displaystyle T(n) - T(n-1) = \sum_{i=1}^{k-1}2i= 2\sum_{k=i}^{k-1}i=2\cdot\frac{k(k-1)}{2}=k(k-1)$

and if n even, write n=2k, and we have

$\displaystyle T(n) - T(n-1) = \sum_{i=1}^{k-1}2i-1= 2\sum_{i=1}^{k-1}i- \sum_{i=1}^{k-1}1=k(k-1)-(k-1)=(k-1)^2$

So altogether we have

$T(1)=T(2)=T(3)=0$

$T(4)=1$
$T(n)=T(n-1)+\begin{cases}k(k-1)\quad \text{if}\ n=2k+1\\(k-1)^2\quad\text{if}\ n=2k\end{cases}n>4, k\in\mathbb{Z}$

You could type this into PARI/GP as

Code:
T(n)=if(n<4,0,if(n==4,1,if(n%2==1,T(n-1)+floor(n/2)*(floor(n/2)-1),T(n-1)+(n/2-1)^2)))
Possibly this result could be used for an inductive proof of simplependulum's formula.

11. Let's try it , the first few terms should be true ( intuitively !! ) , then assume $n= k$ is odd , and $T(k) = \frac{1}{4} [ 2 \binom{k}{3} - \binom{k}{2} - \frac{k-1}{2} ]$

which we have , by the recurrence relation $T(k+1) = \frac{1}{4} [ 2 \binom{k}{3} - \binom{k}{2} - \frac{k-1}{2} ] + ( \frac{k-1}{2} )^2$

$= \frac{1}{4} [ 2 ( \binom{k+1}{3} - \binom{k}{2} ) - ( \binom{k+1}{2} - \binom{k}{1} ) - \frac{k-1}{2} + (k-1)^2 ]$

$= \frac{1}{4} [ 2 \binom{k+1}{3} - \binom{k+1}{2} - k(k-1) + k + \frac{k-1}{2} + (k-1)^2]$

$= \frac{1}{4} [ 2 \binom{k+1}{3} - \binom{k+1}{2} + ( -k^2 + k + k + k^2 - 2k + 1 ) + \frac{k-1}{2} ]$

$= \frac{1}{4} [ 2 \binom{k+1}{3} - \binom{k+1}{2} + 1 + \frac{k-1}{2} ]$

$= \frac{1}{4} [ 2 \binom{k+1}{3} - \binom{k+1}{2} + \frac{k+1}{2} ]$

$= \frac{1}{4} [ 2 \binom{k+1}{3} - \binom{k+1}{2} + \lfloor{ \frac{k+1}{2} \rfloor } ]$ because $k+1$ is even . Therefore , we conclude if $k$ is odd and $T(k)$ is true , so is $T(k+1)$

I am confident it is also true for $k$ is even .

This method is rather clear and trustable comparied with mine because it is analytical while my method is geometrical , which makes ( i am sure ) everybody dizzy including me . I had to imagine a plane in my mind and only guessed the numbers in terms of $z$ to be summed up , I am confident to write this formula out just because i could make contrast to Wilmer's answer ...

12. I sure agree that Jashan should be satisfied with a listing of the possible triangles,
the number which then can be supported by the formula...

Quite easy to program a listing (sides a < b < c):

GET n
LOOP a FROM 1 TO n-2
LOOP b FROM a+1 TO n-1
LOOP c FROM b+1 TO n

IF a+b > c THEN count = count + 1

ENDLOOPS.

If n=6, you'd get these 7:
2,3,4
2,4,5
2,5,6
3,4,5
3,4,6
3,5,6
4,5,6

13. Originally Posted by Wilmer
I sure agree that Jashan should be satisfied with a listing of the possible triangles,
the number which then can be supported by the formula...

Quite easy to program a listing (sides a < b < c):

GET n
LOOP a FROM 1 TO n-2
LOOP b FROM a+1 TO n-1
LOOP c FROM b+1 TO n

IF a+b > c THEN count = count + 1

ENDLOOPS.

If n=6, you'd get these 7:
2,3,4
2,4,5
2,5,6
3,4,5
3,4,6
3,5,6
4,5,6
Agreed. It didn't occur to me to explain to the OP how to write a program. Practically speaking, if all we care about are the numbers and not how we get there, and if we care about minimizing the time/effort we spend to get the answer, then finding a recursive or closed-form solution is only really useful for calculating large values like T(100000).

14. Originally Posted by undefined
Well simplependulum makes it sound easy, but I don't think I'm up for that; I'll try a different approach.

We can look for a recurrence relation; we will express T(n) in terms of T(n-1).

It is easy to verify that T(1)=T(2)=T(3)=0 and T(4)=1. So let's find the recurrence for n>4.

We will reason this way: T(n) - T(n-1) is going to count precisely those triangles that have n as the longest side. Why? Because if the longest side is less than n, then it is already counted in T(n-1). So let's count the triangles that have n as longest side, starting with n=5.

thanks man
thanks mate
S(5)={1,2,3,4,5}

Let's call the shortest side a and the middle side b. Fix b=4=n-1. Then the triangle inequality tells us that $a+b>n \Rightarrow a>n-b = n-(n-1) = 1$. So possible a are {2,3}. What if we try to fix b=3? Then the inequality becomes $a>n-(n-2)=2$ and there are no possible a. So T(5) - T(4) = 2, as expected. (It's expected because we already listed out all the values earlier in this thread.)

Examine S(6)={1,2,3,4,5,6}. Fix b=5. Then a is in {2,3,4}. Fix b=4. Then a is in {3}. So T(6) - T(5) = 4, as expected.

If you continue the pattern you will notice we either have a sum of the form 2 + 4 + ... + (n-3) if n is odd or 1 + 3 + ... + (n-3) if n is even. So

if n odd, write n=2k+1, and we have

$\displaystyle T(n) - T(n-1) = \sum_{i=1}^{k-1}2i= 2\sum_{k=i}^{k-1}i=2\cdot\frac{k(k-1)}{2}=k(k-1)$

and if n even, write n=2k, and we have

$\displaystyle T(n) - T(n-1) = \sum_{i=1}^{k-1}2i-1= 2\sum_{i=1}^{k-1}i- \sum_{i=1}^{k-1}1=k(k-1)-(k-1)=(k-1)^2$

So altogether we have

$T(1)=T(2)=T(3)=0$

$T(4)=1$
$T(n)=T(n-1)+\begin{cases}k(k-1)\quad \text{if}\ n=2k+1\\(k-1)^2\quad\text{if}\ n=2k\end{cases}n>4, k\in\mathbb{Z}$

You could type this into PARI/GP as

Code:
T(n)=if(n<4,0,if(n==4,1,if(n%2==1,T(n-1)+floor(n/2)*(floor(n/2)-1),T(n-1)+(n/2-1)^2)))
Possibly this result could be used for an inductive proof of simplependulum's formula.
thanks man

Page 2 of 2 First 12