# Intuition on the sum of first (n-1) numbers is equal to the number of ways of picking 2 items out of n.

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?

-

## migrated from stackoverflow.comAug 23 '12 at 6:02

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

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

-
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

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!

-

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

-