# What is the number of distinct combinations for choosing a pair of numbers between a sorted sequence?

What is the total number of ways in which we can choose pairs of $a_i$ and $a_j$ between a sequence of increasing sorted numbers numbers $a_1,a_2,a_3,\ldots,a_n$ such that $a_1\le a_i\le a_j\le a_n$.

-

In fact, any pair of elements you choose will always fulfill the condition (as there will always be one greater than the other one, and both between the smallest and the greatest, including these two!), thus you have to calculate the number of sets with two elements out of a set with $\,n\,$ elements, i.e. $$\binom{n}{2}=\frac{n!}{2!(n-2)!}=\frac{(n-1)n}{2}$$ ADDED: as Binn points out in the comment below, the condition $\,a_1\leq a_i\leq a_j\leq a_n\,$ implies that we can choose the same element twice, even if the wording "...choose pairs.." can be misleading.

This being the case, we must add $\,n\,$ cases to the above number, each for every element chosen twice, and we thus get the number $$\frac{(n-1)n}{2}+n=\frac{n(n+1)}{2}$$

-
this is wrong because OP wants to allow $a_i = a_j$ – binn Sep 3 '12 at 11:56
Point taken and you are right, though the wording can be misleading, as he writes "...choose pairs of...", which could be interpreted as different elements. Thanks and I shall add a note to my answer – DonAntonio Sep 3 '12 at 11:59

It is the number of ways to choose two different elements from a set of $n$ elements plus the number of ways to choose one element from a set of $n$ elements. $$\binom{n}{2}+\binom{n}{1}=\frac{n(n-1)}{2}+n=\frac{n(n+1)}{2}.$$

-

${}{}{}{}{}{}{}n(n+1)/2{}{}{}{}{}{}$

-
this is the sum of the arithmetic series ${1+2+3+4+..n}$. How is it true in this case ? – Geek Sep 3 '12 at 11:53