-2
$\begingroup$

Suppose $a,b,c \in\mathbb N$, and the value of $c$ is known and fixed, while $a$ and $b$ are unknown and are both smaller than $c$. What is the total number of unique triangles possible with $a, b$ and $c$ as its sides?

$\endgroup$

closed as off-topic by user21820, Arnaud D., Did, Isaac Browne, Taroccoesbrocco Jul 26 '18 at 7:41

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, Arnaud D., Did, Isaac Browne, Taroccoesbrocco
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Do you mean the natural numbers? Does "known" mean "fixed" and "unknown" mean "variable" (in which case you should not mention $a,b$ in the final question)? And can there be more than one triangle with given sides $a,b,c$? (Under the usual definition there can, for instance realted by translation or rotation, but the 'combinatorics' tag suggests you do not mean that.) In short, please reformulate the question more carefully so people can figure out what you are asking. $\endgroup$ – Marc van Leeuwen Aug 15 '12 at 15:20
  • 1
    $\begingroup$ Unless there are some other conditions, there are an infinite number of possible triangles (assuming $n>1$): just take the sides to be n, n+k and n+k+1 for any positive integer k. $\endgroup$ – Old John Aug 15 '12 at 15:20
  • $\begingroup$ @Old John : Apologies. $\endgroup$ – Swapnanil Saha Aug 15 '12 at 15:25
  • $\begingroup$ No problems! - The question looks more interesting now. $\endgroup$ – Old John Aug 15 '12 at 15:27
  • $\begingroup$ Should degenerate triangles be counted as well? $\endgroup$ – celtschk Aug 15 '12 at 15:28
6
$\begingroup$

What is the total number of unique triangles possible with $a$, $b$ and $c$ as its sides?

The formula you need is $$\left\lfloor\frac{(c-1)^2}{4}\right\rfloor$$

As noted here, it counts "the number of noncongruent integer-sided triangles with largest side $c$". See this article as well.

$\endgroup$
  • $\begingroup$ Won't this overcount because it allows $a,b$ to equal $c$, while the poster asks for $a,b$ smaller than $c$? Not that it would be hard to exclude those cases... $\endgroup$ – hardmath Aug 15 '12 at 16:07
  • 1
    $\begingroup$ No, it does not. $c=1$ and $c=2$ are $0$ for obvious reasons. For $c=3$, you only have $1$ triangle ($(2,2,3)$), which matches with the formula's result. For $c=4$, you have $(2,3,4)$ and $(3,3,4)$, which gives $2$ triangles... you can go on and check. The article I linked to gives a derivation for an alternative formula. $\endgroup$ – J. M. is a poor mathematician Aug 15 '12 at 16:10
  • 1
    $\begingroup$ Anyway, I suppose I should have said my point: OP should have tried out a few cases and then checked out the OEIS. $\endgroup$ – J. M. is a poor mathematician Aug 15 '12 at 16:17
  • $\begingroup$ Your formula is correct, as is the OEIS comment about "triangles with largest side $c$". The extra triangles, allowing $b=c$, number $c$, corresponding to $a = 1,\ldots,c$. But this is precisely the difference between your $\lfloor \frac{(c-1)^2}{4} \rfloor$ and the quantity $\lfloor \frac{(c+1)^2}{4} \rfloor$ commented on in the OEIS. $\endgroup$ – hardmath Aug 17 '12 at 13:28
3
$\begingroup$

For a non-degenerate triangle, we need $$ c\lt a+b\quad\text{and}\quad1\le a,b\le c $$


Generating Function Approach

The generating function for the number of pairs $(a,b)$ where $a+b=k$ and $1\le a,b\le c$ is $$ \left(x+x^2+\cdots+x^c\right)^2=\left(x\frac{x^c-1}{x-1}\right)^2 $$ Now, $$ \begin{align} \sum_{k\gt c}\left[x^k\right]\left(x\frac{x^c-1}{x-1}\right)^2 &=\sum_{k\gt c}\left[x^k\right]\left(\color{#C00}{x^2}\color{#090}{-2x^{c+2}}\color{#00F}{+x^{2c+2}}\right)\sum_{j=0}^\infty(j+1)x^j\\ &=\sum_{k\gt c}\left[\color{#C00}{(k-1)_+}\color{#090}{-2(k-c-1)_+}\color{#00F}{+(k-2c-1)_+}\right]\\ &=\sum_{k\ge0}\left[(k+c)_+-2k_++(k-c)_+\right]\\ &=\sum_{k\ge0}\left[(c-k)+(k-c)_+\right]\\ &=\frac{c(c+1)}2 \end{align} $$ Since we want $a\le b$, we need to add the number of ways $a=b$, which is the number of even numbers in $[c+1,2c]$, that is $\left\lfloor\frac{c+1}2\right\rfloor$, and divide by $2$: $$ \bbox[5px,border:2px solid #C0A000]{\frac12\left(\frac{c(c+1)}2+\left\lfloor\frac{c+1}2\right\rfloor\right)} $$


Brute Force Counting Approach

The possible choices for $a+b=k\ge c+1$ and $1\le a,b\le c$, are $$ (j,k-j) $$ where $k-c\le j\le c$. There are $2c-k+1$ cases for each $k$. This gives the total number of cases to be $$ \begin{align} \sum_{k=c+1}^{2c}(2c-k+1) &=\sum_{k=1}^c(c-k+1)\\ &=\sum_{k=1}^ck\\[3pt] &=\frac{c(c+1)}2 \end{align} $$ Since we want $a\le b$, we need to add the number of ways $a=b$, which is the number of even numbers in $[c+1,2c]$, that is $\left\lfloor\frac{c+1}2\right\rfloor$, and divide by $2$: $$ \bbox[5px,border:2px solid #C0A000]{\frac12\left(\frac{c(c+1)}2+\left\lfloor\frac{c+1}2\right\rfloor\right)} $$


Alternate Forms of the Answer

Form 2:

Since $c-2\left\lfloor\frac c2\right\rfloor=\frac{1-(-1)^c}2$, we get $$ \begin{align} \frac12\left(\frac{c(c+1)}2+\left\lfloor\frac{c+1}2\right\rfloor\right) &=\frac12\left(\frac{c(c+1)}2+\frac{2c+1+(-1)^{c+1}}4\right)\\ &=\bbox[5px,border:2px solid #C0A000]{\frac{2c(c+2)+1-(-1)^c}8} \end{align} $$ Form 3:

Since $\frac{c(c+1)}2$ is an integer, it can pass inside the floor. Since a square is either $0$ or $1$ mod $4$, $\left\lfloor\frac{(c+1)^2}2\right\rfloor$ is even. Therefore, $$ \begin{align} \frac12\left(\frac{c(c+1)}2+\left\lfloor\frac{c+1}2\right\rfloor\right) &=\frac12\left\lfloor\frac{(c+1)^2}2\right\rfloor\\ &=\bbox[5px,border:2px solid #C0A000]{\left\lfloor\frac{(c+1)^2}4\right\rfloor} \end{align} $$

$\endgroup$
  • $\begingroup$ U mean in half of the cases a will lead b and in other half b will lead a..excluding the cases where a=b.. $\endgroup$ – Akul sharma Nov 20 '17 at 9:29
  • $\begingroup$ @Akulsharma: Yes. So the number of cases where $a\le b$, is $\frac12$ the number of total cases plus the number of cases where $a=b$. $\endgroup$ – robjohn Nov 20 '17 at 12:03
  • $\begingroup$ in fuction generating approach why u considered x^(2c+2)? Coz the maximum sum of a+b possible is 2c $\endgroup$ – Akul sharma Nov 20 '17 at 15:44
  • $\begingroup$ @Akulsharma: because $x^{2c+2}$ is part of the generating function. It comes from $x^2\left(1-x^c\right)^2=x^2-2x^{c+2}+x^{2c+2}$. That then needs to be multiplied by $\frac1{(1-x)^2}=\sum\limits_{j=0}^\infty(j+1)x^j$. $\endgroup$ – robjohn Nov 20 '17 at 17:50
  • $\begingroup$ I did it in a different first I find the number of triangles possible (considering a<=b) for c+1 and so on till 2c..but I ignored the term x^(2c+2) because it can not yield ( c+1,2c).. $\endgroup$ – Akul sharma Nov 22 '17 at 16:42
2
$\begingroup$

Depending on whether you consider $(a,b,c)=(3,4,5)$ to give a different triangle from $(a,b,c)=(4,3,5)$, you seem to be either asking for the number of elements in $$ \{\,(a,b)\in\mathbb N^2\mid 0<a< n \text{ and } 0<b, n \text{ and } a+b>n\,\} $$ or for the number of elements in $$ \{\,(a,b)\in\mathbb N^2\mid 0<a\leq b< n \text{ and } a+b>n\,\}. $$ Surely you can find the answers to these easy questions? Make a drawing of dots inside a square if you need to.

$\endgroup$
0
$\begingroup$

Hint: Use the triangle inequality. If $a\leq b\leq c$, it is only required that $a+b>c$, so we need to count the number of pairs $(a,b)$ such that $a\leq b\leq c$ and $c<a+b$. Can you go from here?

$\endgroup$
  • $\begingroup$ I tried but wasn't able to solve the question properly $\endgroup$ – Akul sharma Nov 19 '17 at 17:37
  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review $\endgroup$ – Guy Fsone Nov 19 '17 at 18:01
  • $\begingroup$ @GuyFsone I'm happy to add more to the answer (as I have), but it was decided in this meta question that hints should be posted as answers. Given that the asker stated that he/she did not know where to start, I thought such a hint would be appropriate and could be helpful. $\endgroup$ – Carl Schildkraut Nov 19 '17 at 18:08
  • $\begingroup$ @Akulsharma I'll add a little more to my answer. $\endgroup$ – Carl Schildkraut Nov 19 '17 at 18:08
0
$\begingroup$

Triangle inequality reduces to $c<a+b$ (the other two are obvious), so you need to count the pairs $(a,b)$ with $a\le b\le c$ satisfying $c<a+b\le 2c$. These are: $$(1,c), (2,c-1), (2,c) \ldots (c,c)$$

$\endgroup$
0
$\begingroup$

I wrote a little program who gave me the results in the table, but I can't find a closed formula to get numbers of triangles $n$ directly from $c$

Hope this can be useful

Edit

I found it! Thanks to Mathematica, which means I don't know exactly how to explain

$$n=\frac{1}{8} \left[2 c (c+2)+(-1)^{c+1}+1\right]$$ $$...$$

$ \begin{array}{r|r} c & n\\ \hline 5 & 9 \\ 10 & 30 \\ 15 & 64 \\ 20 & 110 \\ 25 & 169 \\ 30 & 240 \\ 35 & 324 \\ 40 & 420 \\ 45 & 529 \\ 50 & 650 \\ 55 & 784 \\ 60 & 930 \\ 65 & 1089 \\ 70 & 1260 \\ 75 & 1444 \\ 80 & 1640 \\ 85 & 1849 \\ 90 & 2070 \\ 95 & 2304 \\ 100 & 2550 \\ \end{array} $

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.