Q:

A puzzle related to nested loops

For a given input $N$, how many times does the enclosed statement executes?

for $i$ in $1\ldots N$ loop 
  $\quad$for $j$ in $1\ldots i$ loop 
  $\quad$$\quad$for $k$ in $i\ldots j$ loop 
  $\quad$$\quad$$\quad$$sum = sum + i$ ; 
  $\quad$$\quad$end loop; 
  $\quad$end loop; 
  end loop; 

Can anyone figure out an easy way or a formula to do this in general. Please explain.

A:

You need to solve simple formula
$\sum_{i=1}^N\sum_{j=1}^i\sum_{k=i}^j1$
this will give you overall result of
$\frac{1}{6}N(N+1)(N+2)$
Math is easy to do here but I used Wolfram Alpha

A:

What you really count in the variable $\text{sum}$ are triples of the form 
$$\{ (a,b,c) \mid 1\le a<b<c\le N\}.$$
Clearly there are $N(N-1)(N-2)$ triples of different elements. Since you only consider sorted triples, you only count one of the possible $6=3!$ permutations for every triple containing $a,b,c$. Therefore you overcount by a factor of $6$, and this gives you $\text{sum}=N(N-1)(N-2)/6$. 

