Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers

up vote 1 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|improve this answer
1  
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
add comment

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

share|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.