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.

While going through an equation today i realized that sum of first (n-1) numbers is [n*(n-1)/2] which is equal to combinations of two items out of n i.e [n!/((n-2)! * 2!)]. I need some intuition on how these two things are related?

share|improve this question

migrated from stackoverflow.com Aug 23 '12 at 6:02

This question came from our site for professional and enthusiast programmers.

add comment

3 Answers 3

up vote 3 down vote accepted

Wolfram proof without words. Note that this uses Pascal's Triangle.

share|improve this answer
2  
I don't think that the math helps at all here. That just gives a proof that they're equal, rather than providing an intuition for why they're equal. –  templatetypedef Aug 23 '12 at 3:58
    
Yes the math does not help here as your proof is something on which the question is based. The question is "Why are these two completely different equations related?" –  Shashank Tomar Aug 23 '12 at 4:59
    
This answer is perfectly fine! The number of dots is the arithmetic sum of the rows: (n-1)+(n-2)+(n-3)+...+2+1. –  ninjagecko Aug 23 '12 at 5:13
    
@Shashank, I think the linked "proof without words" gives good intuition. –  Rahul Aug 23 '12 at 6:15
    
Sorry guys, the link to wolfram gives a good intuition but the explanation above is a bit misleading, so i have removed it and selected this as the accepted answer. –  Shashank Tomar Aug 23 '12 at 6:48
add comment

One way to think of this is to map it to an intermediary representation - namely, a triangle made of boxes:

 *****
 ****
 ***
 **
 *

Let's suppose that this triangle has width and height n. Its area is equal to 1 + 2 + 3 + ... + n = n(n+1) / 2.

We can interpret this triangle as every way of choosing two elements out of (n + 1) by expanding it out into a 0/1 matrix:

    | 1   2  ... n-1  n
----+------------------
n+1 | 1   1   1   1   1
n   | 1   1   1   1   0
n-1 | 1   1   1   0   0
... | 1   1   0   0   0
2   | 1   0   0   0   0
1   | 0   0   0   0   0

If we take all unordered pairs of two numbers, then we can always sort the pair by putting the bigger number first. Each possible way to do this corresponds to a 1 entry in this matrix. For example, the pairing (n+1, n) corresponds to the upper-right corner, since n+1 > n. Similarly, (n+1, 1) corresponds to the top-left corner. If you count up the number of 1s in this matrix, you'll note that it's half the area of the matrix. There are n + 1 rows and n columns, so the area is n(n + 1) / 2. We can also arrive here by noting that there are n 1s in the first row, then n - 1, then n - 2, ..., then 1. Thus 1 + 2 + ... + n is equal to the number of unordered pairs drawn from (n + 1) numbers.

Hope this helps!

share|improve this answer
add comment

You're asking why the number of ways to pick 2 cards out of a deck of n is the same as the sum 1 + 2 + ... + (n-1).

The reason is that there are (n-1) ways to pair the first card with another card, plus (n-2) ways to pair the second card with one of the remaining cards, plus (n-3) ways to pair the third card...

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.