22
$\begingroup$

The triangular numbers count the number of items in a triangle with $n$ items on a side, like this:

enter image description here

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?

$\endgroup$
42
$\begingroup$

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:

enter image description here

enter image description here


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:

enter image description here

$\endgroup$
18
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.