Why is $\binom{n}{2} = \sum_{i=0}^{n} i = \frac{n(n+1)}{2}$?

Question

I can see this easily by definition. But will it have combinatorial meaning of $\binom{n}{2} = \sum_{k=1} ^{n-1} (k)?$

Answer 1

There is a 1-to-1 correspondence between each blue pair, and each yellow circle. With $n$ blue circles there are $\binom{n}{2}$ blue pairs, and the number of yellow circles is $\sum_{i=1}^{n-1}i$.

Answer 2

$\sum_{i=1}^{n}$ is $\binom{n+1}{2}$, not $\binom{n}{2}$.

Consider the set of $n=1$ tokens $\{1,2,\ldots,n-1,n,*\}$. $\binom{n+1}{2}$ is the size of the set of possible pairs $(i,j)$ with $i<j$ (and $*$ greater than all the rest). Each pair $(i,j)$ represents a point on the plane, and each pair $(i,*)$ represents the point $(i,i)$. These points visualize as:

$$\begin{array}{ccccc} \star&\star&\cdots&\star&\star\\ \star&\star&\cdots&\star\\ \vdots&\vdots\\ \star&\star\\ \star \end{array}$$

Counting from the bottom up, you have $1+2+\cdots+(n-1)+n$ points. So $\binom{n+1}{2}=\sum_{i=1}^ni$.

Answer 3

Clearly $\sum\limits_{i=0}^{n-1} i=\sum\limits_{j=1}^{n} (j-1)$ by using the substitution $j=1+1$

A combinatorial demonstration of ${n \choose 2} = \sum\limits_{j=1}^{n} (j-1)$:

• ${n \choose 2}$ is the number of ways of choosing two integers from $\{1,2,\ldots,n\}$
• if the larger of the two integers is $j \in \{1,2,\ldots,n\}$ then there are $j-1$ possibilities for the smaller of the two integers, so in total there are $\sum\limits_{j=1}^{n} (j-1)$ possible pairs
• so these two expressions are equal

A geometric illustration this is $\frac{n(n-1)}{2}$:

Answer 4

Consider $\dbinom{n+1}{2}$. It is the number of ways to choose two items from a set of $n+1$ items.

So, start with a single item (call it item 1). There are $n$ other items that can be picked to pair with it.

Next, suppose we do NOT pick item 1. We start with item 2. Now, there are $n-1$ other items (that are not item 1 nor item 2) that can be picked to pair with it.

...

Suppose we do NOT pick items 1 through $n-1$. We pick item $n$. There is exactly 1 other item (not items 1 through $n$) that can be picked to pair with it.