Can you find the number of subarrays of the following array?

$$
\text{[1 2 3 4 5 6 7 8]}
$$

If you’ve even had a rudimentary scuffle with Math or CS, you know how to approach the question; it is almost too easy. The general formula for the count of subarrays, of an array with $n$ elements, is

$$
\frac {n(n+1)} {2}
$$

While the question is pretty simple, the formula isn’t quite as trivially intuitive. Googling `number of subarrays proof`

emits an answer distribution with a more significant variance than I predicted. Consider the best source of reference for a sample:

The total number of subarrays

In the above discussion, there are *five* distinct approaches to prove the same! Considering the apparent triviality of the problem, I was intrigued by the fat-tailed distribution and derived it myself. I came up with two approaches that look intuitive to me (both also offered in the reference above).

Consider an array $A$ with $n$ elements. The indices of the above array fall within the range $[1…n]$ (1-indexed).

$$
A: int[n] \\
i\in \text{[1 2 3 ... n]}\ (i \rightarrow \text{index of A})
$$

To slice a subarray, we need the start & end indices of the subarray, termed $s$ & $e$ respectively, such that $s \le e\ (s, e \in i)$.

### Proof 1: Counting

So consider the following chain of logic:

- If the subarray starts from the first index ($s=1$), there are $n$ possibilities for the end index ($e \sub [1…n]$).
- If $s=2$, $e \sub [2…n]$ (n-1 possibilities).
- If $s=3$, $e \sub [3…n]$ (n-2 possibilities).

and so on…

s |
e (range of possibilities) |
possibilities |

1 |
[1…n] |
n |

2 |
[2…n] |
n-1 |

3 |
[3…n] |
n-2 |

k |
[k…n] |
n-(k-1) |

n-2 |
[n-2…n] |
n-((n-2)-1) = 3 |

n-1 |
[n-1….n] |
2 |

n |
[n] |
1 |

**Hence, the total choices (total count of subarrays) are** $\sum \text{(possibilities)}$ **=**

$$
1 + 2 + 3 + ... + (n-(k-1)) + ... + (n-1) + n = \\
\bold{\frac {n(n+1)}{2}}
$$

### Proof 2: Selecting

Alternatively, you can frame the above approach as *selecting* any two indices from $[1…n]$, essentially:

$$
n \choose 2
$$

Which is the total number of ways to select two elements out of $n$. However, this only includes subarrays with at least two elements; distinct start & end index ($s\ != e$). We also need to factor in all the singleton subarrays ($s == e$), which are:

$$
n \choose 1
$$

**Hence, the total count of subarrays**