Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
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


share|cite|improve this answer
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

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}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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