Is there a combinatorial interpretation of the triangular numbers?

Question

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?

Answer 1

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:

Answer 2

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-1$ people, person $2$ shook hands with $n - 2$ people, and so on, until we reach the last person who has already shaken the hand off all people, for a total of $\sum_{k=1}^{n-1}k$ handshakes.

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

Answer 3

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.

Answer 4

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.

Answer 5

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}