quick way to count Suppose we have 10 sticks with length 1-10, respectively. Pick three from them, how many triangles can we form?
I counted one by one and got 50. Is there a quick way? Any help would be appreciated.
 A: Call the three sticks $a < b < c$. Pick $c$ first. The other two must sum to more than $c$. Pick $a$ second. So we have $$\sum_{c=1}^{10} \sum_{a=1}^{c-1} \sum_{b=a+1}^{c-1} [a+b > c]$$
Working from the inside out you should be able to tighten the bound on $b$ to remove that Iverson bracket and replace the inner sum with a $\max$ of $0$ and a linear expression in $a$ and $c$; then adjust the bounds on $a$ to remove the $\max$ and leave just the linear expression; then replace the sum over $a$ with a quadratic expression, and finally reduce the outer sum to a cubic expression in the largest stick length.

Ok, I was overly optimistic. The innermost sum is piecewise linear, and it gets more complicated from there.
$$\sum_{b=a+1}^{c-1} [a+b > c] = \sum_b [c-a < b][a < b][b < c] \\
= \sum_b [\max(c-a, a) < b < c] = \max(0, c - 1 - \max(c-a, a)) \\
= \begin{cases}
    \max(0, a- 1) & \textrm{if } c-a > a \\
    \max(0, c - a - 1) & \textrm{if } c-a \le a \\
  \end{cases} \\
= \begin{cases}
    a - 1 & \textrm{if } 2 < 2a < c \\
    c - a - 1 & \textrm{if } c \le 2a < 2c-2 \\
    0 & \textrm{otherwise}
  \end{cases} \\
$$
Then $$\sum_{a=1}^{c-1} \sum_{b=a+1}^{c-1} [a+b > c] = \sum_{a=1}^{c-1} \begin{cases}
    a - 1 & \textrm{if } 2 < 2a < c \\
    c - a - 1 & \textrm{if } c \le 2a < 2c-2 \\
    0 & \textrm{otherwise}
  \end{cases} \\
= \left(\sum_{a=2}^{\frac {c-1}2} a-1\right) + \left(\sum_{a=\frac c2}^{c-2} c-a-1\right) \\
= \begin{cases}
    \left(\sum_{a=2}^{\frac c2-1} a-1\right) + \left(\sum_{a=\frac c2}^{c-2} c-a-1\right) & \textrm{if } c \textrm{ is even} \\
    \left(\sum_{a=2}^{\frac {c-1}2} a-1\right) + \left(\sum_{a=\frac {c+1}2}^{c-2} c-a-1\right) & \textrm{if } c \textrm{ is odd} \\
  \end{cases} \\
% subst i:=a-1 / a=i+1, j:=c-a-1 / a=c-j-1
= \begin{cases}
    \left(\sum_{i=1}^{\frac c2-2} i\right) + \left(\sum_{j=1}^{\frac c2-1} j\right) & \textrm{if } c \textrm{ is even} \\
    \left(\sum_{i=1}^{\frac {c-3}2} i\right) + \left(\sum_{j=1}^{\frac {c-3}2} j\right) & \textrm{if } c \textrm{ is odd} \\
  \end{cases} \\
= \begin{cases}
    \frac{(c-2)^2}{4} & \textrm{if } c \textrm{ is even} \\
    \frac {(c-1)(c-3)}4 & \textrm{if } c \textrm{ is odd} \\
  \end{cases} \\
$$
Finally,
$$\sum_{c=1}^N \sum_{a=1}^{c-1} \sum_{b=a+1}^{c-1} [a+b > c]
= \sum_{c=1}^N \frac14 \begin{cases}
    (c-2)^2 & \textrm{if } c \textrm{ is even} \\
    (c-1)(c-3) & \textrm{if } c \textrm{ is odd} \\
  \end{cases} \\
= \left(\sum_{k=1}^{\left\lfloor \frac N2\right\rfloor} \frac{(2k-2)^2}{4}\right) + \left(\sum_{m=0}^{\left\lfloor \frac{N-1}2\right\rfloor} \frac{(2m+1-1)(2m+1-3)}{4} \right) \\
% subst k'=k-1 / k=k'+1
= \left(\sum_{k'=0}^{\left\lfloor \frac{N-2}2\right\rfloor} k'^2\right) +
  \left(\sum_{m=0}^{\left\lfloor \frac{N-1}2\right\rfloor} m(m-1) \right) \\
% PLAN A
= \left(\sum_{k=0}^{\left\lfloor \frac{N-2}2\right\rfloor} 2k^2 - k\right) + \left[\left\lfloor \frac{N-1}2\right\rfloor > \left\lfloor \frac{N-2}2\right\rfloor\right] \left\lfloor \frac{N-1}2\right\rfloor \left(\left\lfloor \frac{N-1}2\right\rfloor - 1\right)\\
= \frac{\left\lfloor \frac{N-2}2\right\rfloor \left(\left\lfloor \frac{N-2}2\right\rfloor + 1\right) \left(4\left\lfloor \frac{N-2}2\right\rfloor - 1\right)}{6} 
+ [N\textrm{ is odd}] \frac{(N-1)(N-3)}4 \\
= \begin{cases}
   \frac{(N-1)(N-3)(2N-7)}{24} + \frac{(N-1)(N-3)}4 & \textrm{if } N \textrm{ is odd} \\
   \frac{N(N-2)(2N-5)}{24} & \textrm{if } N \textrm{ is even}
  \end{cases} \\
= \begin{cases}
   \frac{(N-1)(N-3)(2N-1)}{24} & \textrm{if } N \textrm{ is odd} \\
   \frac{N(N-2)(2N-5)}{24} & \textrm{if } N \textrm{ is even}
  \end{cases} \\
$$
A: While bruteforcing you can notice a pattern.
$$\begin{array}{c|c}
Odd&Even\\
\hline
4=3+1<3+\{2\}&5=4+1<4+\{2,3\}\\
\hline
6=5+1<5+\{2,3,4\},&7=6+1<6+\{2,3,4,5\},\\ \qquad \quad \ 4+\{3\}&
\qquad \quad \ 5+\{3,4\}\\
\hline
8=7+1<7+\{2,3,4,5,6\},&9=8+1<8+\{2,3,4,5,6,7\}, \\
\qquad \quad \ \ 6+\{3,4,5\},&\qquad \quad \ 7+\{3,4,5,6\}\\
\quad \ 5+\{4\}&\quad \ 6+\{4,5\}\\
\hline
10=9+1<9+\{2,3,4,5,6,7,8\}, \\
\qquad \quad \ \ 8+\{3,4,5,6,7\}\\
\quad \ \ 7+\{4,5,6\}\\
6+\{5\}\\
\end{array}$$
Hence, the cardinalities of the sets:
$$\sum_{i=1}^{4}\sum_{j=1}^i (2j-1)+\sum_{i=1}^3\sum_{j=1}^i (2j)=\\
\sum_{i=1}^4 (2\cdot \frac{1+i}{2}\cdot i-i)+\sum_{i=1}^3 (2\cdot \frac{1+i}{2}\cdot i)=\\
\sum_{i=1}^4 i^2+\sum_{i=1}^3 (i^2+i)=\\
\frac{4\cdot 5\cdot 9}{6}+\frac{3\cdot 4\cdot 7}{6}+\frac{1+3}{2}\cdot 3=\\
30+14+6=50.$$
The general formula for $n$:
$$\large{\sum_{i=1}^{\lfloor \frac{n}{2}-1\rfloor}\sum_{j=1}^{i} (2j-1)+\sum_{i=1}^{\lfloor \frac{n}{2}-1\rfloor}\sum_{j=1}^i (2j)}$$
