# 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?

• Welcoming the Math.SE! Here we have a culture of showing what you've tried, as it helps both the responders to give better answers and you to get a better understanding! :) – frogeyedpeas Mar 17 '15 at 22:08
• Looks you forgot to list $\{3, 1\}$ – AgentS Mar 17 '15 at 22:13
• No! I didn't forget {3,1}. A subarray has to have contiguous elements – user72708 Mar 18 '15 at 13:56

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\;.$$

• I am confused why you use the index of the element that immediately follows its last element instead of just the last element. I was thinking the answer should be n C 2, instead of n+ 1 C 2 that you mentioned. Please correct me wherever I am wrong. – Abhishek Bhatia Jul 7 '18 at 19:33
• @Abhishek , You are right, It is n C 2 where we did not calculate the single character substrings. There can be n single character substring . So the result is (n C 2 + n C 1) = (n+1) C 2 . – shuva Oct 31 '18 at 20:15

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)$$

then

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

We verify:

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

So you're formula does indeed work! Now we verify that for N = 1

$$\frac{1*(1+1)}{2} = 1$$

And therefore we can use the above logic to show that for any and ALL whole numbers N the formula works!

This calculation can be seen as an arithmetic series (i.e. the sum of the terms of an arithmetic sequence).

Assuming the input sequence: $$(a_0, a_1, \ldots, a_n)$$, we can count all subarrays as follows:

\begin{align} \; 1 & \; \text{subarray from} \; a_0 \; \text{to} \; a_{n-1}\\ + \; 1 &\; \text{subarray from} \; a_1 \; \text{to} \; a_{n-1}\\ & \; \ldots \\ + \; 1 & \; \text{subarray from} \; a_{n-1}\; \text{to} \; a_{n-1}\\ = & \; n \end{align}

$$+$$

\begin{align} \; 1 & \; \text{subarray from} \; a_0 \; \text{to} \; a_{n-2}\\ + \; 1 &\; \text{subarray from} \; a_1 \; \text{to} \; a_{n-2}\\ & \; \ldots \\ + \; 1 & \; \text{subarray from} \; a_{n-2}\; \text{to} \; a_{n-2}\\ = & \; n-1\\ \end{align}

$$+ \; \ldots$$

\begin{align} \; \; \; 1 & \; \text{subarray only containing} \; a_0\\ = & \; 1\\ \end{align}

which results in the arithmetic series: $$n + n-1 + … + 1$$.

The above can also be represented as $$\sum_{i=1}^{n}i\;$$ and adds up to $$n (n+1)/2$$.

Elaborating on Brian's answer, lets assume we count all the single character sub-strings. There can be n such single character sub-string. By using the Binomial Coefficient, $$\binom{n}{r}$$ notation, we can say n = $$\binom{n}{1}$$ .

$$total_1 = n = \binom{n}{1}$$

Now let's assume we count all the sub-string that are not single character. Because we have to choose the beginning and end of the sub-string regardless of the order, the count should be $$\binom{n}{2}$$.

$$total_* = \binom{n}{2}$$

Now the total number of sub-string,

$$total = total_1 + total_* = \binom{n}{1} + \binom{n}{2}$$

Now recall Pascal triangle and recurrence relation $$\binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1}$$. So we can write,

$$total = total_1 + total_* = \binom{n}{1} + \binom{n}{2} = \binom{n+1}{2} = n(n+1)/2$$

There we have the mathematical deduction. (I kind of feel we do not need the fancy recurrence relation to get the final answer though).

• Use LaTeX please. – Michael Rozenberg Oct 31 '18 at 20:31

Trying to explain in layman terms.

Let's say f(0) = 0

f(1) = 1
f(2) = 3
f(3) = 6
f(4) = 10
f(5) = 15

By observation, you can see that each result is just an addition of previous result and current number.

f(n) = n + f(n-1)

So with this formula let's expand f(5).

f(5)
=> 5 + f(4)
=> 5 + 4 + f(3)
=> 5 + 4 + 3 + f(2)
=> 5 + 4 + 3 + 2 + f(1)
=> 5 + 4 + 3 + 2 + 1 + f(0)
=> 5 + 4 + 3 + 2 + 1 + 0
===> This is equal to sum of n numbers = n(n+1)/2