A combinatorial proof of $\forall n\in\mathbb{N},\,\binom{n}{2}=\frac{n(n-1)}{2}$

Question

The property $\forall n\in\mathbb N,\,\binom{n}{2}=\frac{n(n-1)}{2}$ was given in our first chapter on probability theory among binomial coefficients' properties. It is really easy to prove with the formula $\binom{n}{k}=\frac{n!}{k!(n-k)!}$, yet it is mentioned in other course notes, so I thought it has other combinatorial meanings and that it may even be quite special (like the fact that the property doesn't hold only for positive integers but for all real numbers). So could you please tell me if that's is the case? I'll also be grateful if you shared your combinatorial interpretations of it. Personally, the one above is mine. I'm not accurate at combinatorics so please verify if it is correct.

The case $n=1$ is trivial since $\frac{n(n-1)}{2}=0$ and, combinatorially, we know that $\binom{n}{k}=0$ when $n<k$ because we can't take a number of elements which is higher than the one of available elements.

So suppose that $n\ge 2$. Notice that $\sum\limits_{i=1}^{n-1}i=\frac{n(n-1)}{2}$. This remark is the idea behind the proof.

Suppose we have an urn that contains $n$ red balls numbered $1,2,\dots,n$. There are two ways to count the number of ways of drawing $2$ balls without taking order in consideration:

• We know that this number of ways is given by $\binom{n}{2}$.

• (This second way of counting is what makes me doubt about the veracity of the proof) Let us fix $i\in\{1,\dots,n\}$. By the fundamental principle of counting, the number of combinations that contains balls one with the number $i$ and the other one with no number less than $i$ is $n-i$ (this fits with the case $i=n$ because in this case no such a combination is possible since all balls' numbers are less than or equal $n$). On the other hand, it is easy to show that any combination of two balls among $n$ can be counted only once like this (Take $i$ the minimum of the two numbers given by the ball. We can't take the maximum because the other number given by the balls is smaller and it's for this reason that the condition "no number less than $i$" exists). Therefore the number of ways is:$\sum_{i=1}^nn-i=\sum_{i=1}^{n-1}n-i=\sum_{i=1}^{n-1}i=\frac{n(n-1)}{2}$.

As a conclusion: $\forall n\in\mathbb N,\,\binom{n}{2}=\frac{n(n-1)}{2}$.

Answer 1

Turning my comment into an answer by request.

There is a nice geometric-combinatoric way to do this via polygons. Consider an $n$-gon, then the number of line segments between any two vertices is (by definition) $\binom{n}{2}$. If you number the vertices $1$ through $n$, then vertex $1$ connects with $n-1$ vertices, vertex $2$ connects with $n-2$ vertices (since it's already connected to vertex $1$), etc. Adding all of these up, you get

$$\sum_{i=1}^n (n-i) = n^2 - \frac{n(n+1)}{2} = \frac{n(n-1)}{2}.$$

Answer 2

What you have works.

Alternatively, if you draw two balls with replacement, there are $n^2$ possible outcomes. In $n$ of these you’ve drawn the same ball twice, so there are $n^2-n=n(n-1)$ possible outcomes in which you get two different balls. Each pair of balls can occur in either of two orders, so $n(n-1)$ counts each unordered pair of balls twice. Thus, there are therefore $\frac{n(n-1)}2$ different unordered pairs of balls, and $\binom{n}2=\frac{n(n-1)}2$.

Answer 3

To make a subset of $\{1,...,n\}$ of 2 elements, you have $n$ choice for the first element, $n-1$ choice for the seconde, and since the order is not important, you divide by $2$ (since $\{1,2\}$ and $\{2,1\}$ is the same). Therefore you get $$\binom{n}{2}=\frac{n(n-1)}{2}.$$

Answer 4

I cannot think of a really nice way, the issue is the division by $2$. But doing the closely related $2\binom{n}{2}=n(n-1)$ is easy.

There are $n$ teams in a league, and each team plays every other team twice, at home and away. So the number of games is $2\binom{n}{2}$. But every game is a home game for somebody, and every one of the $n$ teams plays $n-1$ home games, for a total of $n(n-1)$.

Answer 5

There are $\binom n2$ ways of selecting two integers $i$ and $j$ such that $1\le i<j\le n$, almost by definition. That means:

\begin{align} \binom n2&=\sum_{1\le i<j\le n}1\\ &=\sum_{1\le j\le n\text{ and }1\le i<j}1\\ &=\sum_{j=1}^n\sum_{i=1}^{j-1}1\\ &=\sum_{j=1}^n(j-1)\\ &\qquad(j':=j-1)\\ &=\sum_{j'=0}^{n-1}j'\\ &=\frac{n(n-1)}2 \end{align}