Page 2 of 2 FirstFirst 12
Results 16 to 29 of 29

Math Help - Number of possible triangles

  1. #16
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by jashansinghal View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  2. #17
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,110
    Thanks
    68
    Quote Originally Posted by jashansinghal View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Member
    Joined
    Jun 2009
    Posts
    77
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,110
    Thanks
    68
    Quote Originally Posted by jashansinghal View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Member
    Joined
    Jun 2009
    Posts
    77
    what does INT (n/2) mean?
    And does nC3 mean combination?
    Follow Math Help Forum on Facebook and Google+

  6. #21
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,110
    Thanks
    68
    Quote Originally Posted by jashansinghal View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #22
    Member
    Joined
    Jun 2009
    Posts
    77
    Can you please provide me with an easy proof to this formula?
    Follow Math Help Forum on Facebook and Google+

  8. #23
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by jashansinghal View Post
    Can you please provide me with an easy proof to this formula?
    I wrote:

    Quote Originally Posted by undefined View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #24
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Quote Originally Posted by jashansinghal View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  10. #25
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by simplependulum View Post
    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.
    Last edited by undefined; June 22nd 2010 at 05:26 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  11. #26
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 ...
    Last edited by simplependulum; June 21st 2010 at 11:25 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #27
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,110
    Thanks
    68
    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
    Follow Math Help Forum on Facebook and Google+

  13. #28
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Wilmer View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  14. #29
    Senior Member
    Joined
    Feb 2010
    Posts
    456
    Thanks
    34
    Quote Originally Posted by undefined View Post
    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
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 13th 2011, 02:32 PM
  2. Replies: 0
    Last Post: November 13th 2011, 02:18 PM
  3. Replies: 3
    Last Post: January 25th 2011, 11:34 PM
  4. Find number of different triangles possible?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 26th 2009, 06:25 AM
  5. help with number of triangles
    Posted in the Geometry Forum
    Replies: 1
    Last Post: October 2nd 2006, 11:47 AM

Search Tags


/mathhelpforum @mathhelpforum