# Is there a combinatorial interpretation of the triangular numbers?

The triangular numbers count the number of items in a triangle with $n$ items on a side, like this: This can be calculated exactly by the formula $T_n = \sum_{k=1}^n k = \frac{n(n+1)}{2} = {n+1 \choose 2} = {n+1 \choose n-1}$.

Is there any combinatorial interpretation to that formula, as in some way to interpret arranging objects in a triangle with $n$ on a side as the number of ways to choose 2 or $n-1$ objects out of a collection of $n+1$ objects?

• OEIS is a good resource for helping with questions like this. Link to triangle numbers Oct 18, 2017 at 17:45
• A related question: Combinatorial argument for the sum of the first $n$ integers. (Admittedly, that question is stated in a somewhat unclear way; from the formulation it is not obvious whether the question in the title is the same as the question in the body.) Oct 19, 2017 at 14:08

Imagine a row of $n{+}1$ buttons underneath the triangle (as an extra row). Then for any two of those buttons you select they will designate a point of the triangle, and every point of the triangle can be identified with a pair of buttons: Edit: David K notes in comments that a route distance triangle is a practical application of this idea. Pick two locations, read off the distance at the intersecting point of the triangle. Adapted slightly from the image given: • A practical application of this principle has long been used to construct tables of distances between cities on road maps, for example like this: i2.wp.com/www.canadianrockies.net/wp-content/uploads/2009/02/… Oct 18, 2017 at 18:18
• This was previously mentioned in this answer which is, in turn, based on an answer on MO. (It is the top voted answer in the question about Proofs without words.) Oct 19, 2017 at 14:05
• @MartinSleziak Neat, although I had never seen those. And I can't compete with animations:-). Oct 19, 2017 at 14:08

Consider a set of $n$ people, each shaking hands with one another. How many handshakes are there? There are $\binom{n}{2}$ pairs of people, so there are $\binom{n}{2}$ handshakes.

Now imagine person $1$ goes down the line of other people and shakes hands with everyone. Then person $2$ goes down the line, shaking hands with everyone but person $1$ (since they've already shaken hands). Repeat until every person has shaken hands with every other.

Then person $1$ shook hands with $n$ people, person $2$ shook hands with $n - 1$ people, and so on, for a total of $\sum_{k=1}^{n-1}k$ handshakes.

Thus, $\binom{n}{2} = \sum_{k=1}^{n-1}k$.

Here is a combinatorial proof of the identity $$1+2+\dotsb+n=\binom{n+1}{2}.$$ The RHS counts the number of two-element subsets of $\{0,1,\dotsc,n\}$. Let $S _k$ be those two-element subsets of the preceding set with larger element $k$ for $k=1,\dotsb, n$. Then the $S _k$ partition the set of two element subsets of $\{0,1,\dotsc,n\}$. Further, $|S _k|=k$. Counting in this way yields the LHS.

This argument can be generalized to obtain the identity $$\sum_{i=0}^n \binom{i}{k}=\binom{n+1}{k+1}$$ by classifying $k+1$-element subsets of $\{0,1,\dotsc, n\}$ based on their largest element.

Align all rows in a triangle to the rightmost column.
Mark $(n+1)$-items row below the triangle, similary aligned to the right margin.

All pairs from $(n+1)$-items set are built by:

• pairing the first item with each of remaining $n$ items (those are marked with dots in the bottom-most row),
• then pairing the second item with all remaining $n-1$ items with the first one already excluded (that's what the second-bottommost row shows),
• next pairing the third item with all remainig $(n-2)$ items
• ...and so on,
• till the topmost row, which represents a pair of last two items of the set.

This maps bijectively dots in each $n$-triangle onto two-elements subsets of an $(n+1)$-elements set.

Here's another (clunkier) bijective proof. First, note that we can represent each circle in the triangle as a tuple $(a, b)$, where $a$ is the row number and $b$ is the index of the circle in row $a$. A tuple $(a, b)$ has a corresponding circle in the triangle if $a \in [n]=\{1, 2, ..., n\}$ and $b \leq a$.

In other words, there is a bijection between the set of circles in your triangle and tuples (a, b), where $a, b \in \mathbb{N}^+$ and $b \leq a \leq n$. We'll call the set of such tuples $T$.

Now consider the mappings \begin{align} \varphi&: \{\text{2 element subsets of [n+1]}\} \rightarrow T;\\ \{p, q\} &\mapsto \begin{cases} (\max(p, q), \min(p, q)) & \text{if }p\neq n+1 \text{ and } q \neq n+1 \\ (\min(p, q), \min(p, q)) & \text{if } p=n+1 \text{ or } q=n+1 \end{cases}. \\ \\ \varphi^{-1}&: T \rightarrow \{\text{2 element subsets of [n+1]}\};\\ (a, b) &\mapsto \begin{cases}\{a, b\} & \text{if }a \neq b\\ \{a, n+1\} &\text{if } a=b \end{cases}. \end{align} What does $\varphi$ do?

When $p, q \in [n]$, $\varphi$ takes the greater of the two numbers to indicate the row of the circle, and the smaller of the two to indicate the index. This ensures that the tuple $(a, b)$ to which $\{p, q\}$ is mapped satisfies $b \leq a \leq n$, and so our mapping actually maps things to the intended codomain. This takes care of the circles where the row number is not equal to the index (i.e. the circles that are not at the far right of their rows).

When one of $p, q$ is $n+1$, we know that the other one is not $n+1$, as the subsets that we are dealing with consist of 2 unique elements. Without loss of generality, let $q=n+1$, so that $p \in [n]$. $\varphi$ maps such a subset to the $p$th circle of the $p$th row. So the image of $\{p, q\}$ is $(a, b)$=$(p, p)$, and we have $b=a=p\leq n$, so again this lies in our intended codomain. This takes care of the circles that do lie at the far right of their rows.

It's not too difficult to check that $\varphi$ and $\varphi^{-1}$ are well-defined and mutual inverses, and hence bijections. Since we have a bijection from the set of 2-element subsets of $n+1$ to $T$, and a bijection from $T$ to the set of circles in the triangle, composing these two bijections gives a map from the set of 2-element subsets of $[n+1]$ to our set of circles, and \begin{align}\binom{n+1}{2}&=\text{# of 2-element subsets of [n+1]}\\ &=\left|\{\text{2-element subsets of }[n+1]\}\right| \\ &=\left|\{\text{circles in the triangle}\} \right|\\ &=\text{# of circles in the triangle}. \end{align}