__T_H_O_R__'s blog

Triangle Counting
By __T_H_O_R__, history, 6 years ago, In English

Question: You are given n sticks of lengths 1 to n unit respectively. Using three different sticks how many different triangles can you form?

I have found a formula on the internet. That is if n is odd triangle=(n-1)*(n-3)*(2n-1)/24 else triangle=n*(n-2)*(2n-5)/24

But I could not prove this or find any proof. Can anyone provide with a proof of this formula? How to derive this? Or share if there are other ways to solve this problem? Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

It can be proved by induction.
For n = 4 the number is 1. For n = n0 + 1, if n0 is odd then the number is ; if n0 is even then the number is ; in both cases the first term is the number of triangles with lengthes  ≤ n0 and the second term is the number of triangles with one length that equal to n. By simplifying expressions, you can get needed formula

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For n = 4 the number is 3.

    So we're assuming degenerate triangles are allowed? Otherwise I think the only valid triples is {2, 3, 4}. In fact, the given formula n(n - 2)(2n - 5) / 24 gives 1 as well.

    → Reply