The total number of subarrays

I want to count the number of subarrays for a vector (not combinations of elements).
Ex.

 A[1,2,3]

It has 6 subarrays :

{1}, {2}, {3}, {1,2}, {2,3}, {1,2,3}

I think that for a vector of N elements the total number of subarrays is N*(N+1)/2.
I am not able to prove it, can someone do it?

Solution 1:

Suppose that your vector is $\langle a_1,a_2,\ldots,a_n\rangle$. Imagine a virtual element $a_{n+1}$ at the end; it doesn’t matter what its value is. A subarray is completely determined by the index of its first element and the index of the element that immediately follows its last element. For example, the subarray $\langle a_3,\ldots,a_{n-2}\rangle$ is determined by the indices $3$ and $n-1$, the subarray $\langle a_k\rangle$ is determined by the indices $k$ and $k+1$, and the subarray $\langle a_2,\ldots,a_n\rangle$ is determined by the indices $2$ and $n+1$. Moreover, each pair of distinct indices from the set $\{1,2,\ldots,n+1\}$ uniquely determines a subarray. Thus, the number of subarrays is the number of pairs of distinct indices from the set $\{1,2,\ldots,n+1\}$, which is

$$\binom{n+1}2=\frac{n(n+1)}2\;.$$

Solution 2:

Consider an arbitrary array of N DISTINCT ELEMENTS (if the elements are the same then I am afraid the formula you are seeking to prove no longer works!).

Naturally there exists 1 array consisting of all the elements (indexed from 0 to N-1)

There exist 2 arrays consisting of N-1 consecutive elements (indexed from 0 to N-2)

and in general there are k arrays consisting of N-k+1 consecutive elements (indexed from 0 to N-k-1)

Proof:

We can access elements 0 ... N-k-1 as the first array, then 1 ... N-k+2 is the second array, and this goes on for all N-k+r until N-k+r = N-1 (ie until we have hit the end). The r that does us is can be solved for :

$$ N-k+r = N-1 \rightarrow r -k = -1 \rightarrow r = k-1 $$

And the list $$0 ... k-1$$ contains k elements within it

Thus we note that the total count of subarrays is

1 for N elements

2 for N-1 elements

3 for N-2 elements

N for 1 element

And the total sum must be:

$$ 1 + 2 + 3 ... N$$

Let us see if your formula works

if:

$$ 1 + 2 +3 ... N = \frac{1}{2}N(N+1)$$