11
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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! :) $\endgroup$ – frogeyedpeas Mar 17 '15 at 22:08
  • $\begingroup$ Looks you forgot to list $\{3, 1\}$ $\endgroup$ – ganeshie8 Mar 17 '15 at 22:13
  • 1
    $\begingroup$ No! I didn't forget {3,1}. A subarray has to have contiguous elements $\endgroup$ – user72708 Mar 18 '15 at 13:56
11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Abhishek Bhatia Jul 7 '18 at 19:33
  • 1
    $\begingroup$ @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 . $\endgroup$ – shuva Oct 31 '18 at 20:15
4
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Use LaTeX please. $\endgroup$ – Michael Rozenberg Oct 31 '18 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.