Triangular Numbers and Combinatorics

Consider the sequence of triangles in Figure 1. Each is a stack of discs forming an equilateral triangle. If we index the sequence by integer \({\color{black}{i}}\), the \({\color{black}{i^{th}}}\) triangle has \({\color{black}{i}}\) discs to a side.

Fig. 1 Geometric representation of the first few triangular numbers -- the \({\color{black}{i^{th}}}\) number is equal to the number of discs needed to form an equilateral triangle of side \({\color{black}{i}}\). Not stacks of cannon balls.

This sequence has a clearly recognizable pattern: to build the \({\color{black}{i^{th}}}\) figure we add \({\color{black}{i}}\) discs as a new bottom row to the \({\color{black}{(i-1)^{th}}}\) figure. We are interested in computing the number of discs in the \({\color{black}{i^{th}}}\) triangle -- these are the triangular numbers. The \({\color{black}{i^{th}}}\) triangular number, \({\color{black}{T^2_i}}\), is evidently the sum \({\color{black}{1 + 2 + 3 + }}\cdots + (i-1) + i\). For large \({\color{black}{i}}\), this sum is long and tedious to compute, so we'd like to find a simple expression for the \({\color{black}{T^2_i}}\). These kinds of numbers -- ones that can be represented as a geometrical arrangement of packed discs -- are broadly known as figurate numbers, and the trianglular numbers are but one kind. Most familiar are the square numbers, which are the numbers of discs that appear in squares of increasing size; the well-known sequence is \({\color{black}{}}\{1,4,9,16,25,36,49,\cdots\}\). But square numbers are easy: the \({\color{black}{i^{th}}}\) number in the sequence is just \({\color{black}{i^2}}\). How do we go about finding the corresponding expression for the triangular numbers?

As with most things in mathematics, sometimes it's easier to consider a different problem. Instead of triangles, lets think about discs of different colors. Suppose we have discs of four different colors:

How many different two-color combinations can we make out of the four colors? Consider the arrangement in Figure 2. Starting with the red disc, we can pair it with each of the three other colors (the pairings are represented by the three red lines.) The next disc can be paired with the green and purple discs, but not the red one -- it's already been paired with the red in the previous round. Continuing on, the green can pair with the purple. And that's all -- there are \({\color{black}{3 + 2+ 1}}\) possible pairings.

Fig. 2 (a) Equivalent combinatoric problem as summing the discs in the \({\color{black}{i=3}}\) equilateral triangle of Fig. 1. (b) The \({\color{black}{i=3}}\) equilateral triangle built out of the unique partners of the red disc (bottom row), blue disc (middle row) and green disc (top).

This series of numbers should look familiar -- it's the number of discs in an equilateral triangle of base \({\color{black}{3}}\). The base of the triangle is formed by the red disc's partners, the next row by the blue disc's partners, and the final disc is paired with the green disc (see Figure 2 (b)). We could do a few more examples to convince ourselves, but I'll cut to the chase: the number of discs in a triangle of base \({\color{black}{i}}\) is equal to the number of two-color combinations that can be made out of \({\color{black}{i+1}}\) colors. This actually might not seem like an easier problem, and maybe it isn't! But, it's probably more familiar because it's a standard combinatorics problem: the number of combinations of 2 objects that can be made out of \({\color{black}{n}}\) objects is given by the binomial coefficient, \begin{equation}{\color{black}{ {n \choose 2} = \frac{n!}{(n-2)!2!}. }}\end{equation} For the \({\color{black}{i^{th}}}\) triangular number, \({\color{black}{T^2_i}}\), we then have \begin{equation} \label{gauss} {\color{black}{ T^2_i = \sum_{j=0}^i j = \binom{i+1}{2} = \frac{i(i+1)}{2}. }}\end{equation} Written in this form, the \({\color{black}{T^2_i}}\) should look familiar; they are just the Gauss sums of the integers \({\color{black}{i}}\). But Gauss wasn't doing combinatorics when he determined that the sum of the integers from 1 to \({\color{black}{i}}\) could be written neatly as \({\color{black}{i(i+1)/2}}\). How did he do it?

First off, he was something like 7 years old when he found this result. The story, the accuracy of which I am totally unsure about, goes like this. When Gauss was in grade school, as punishment for some odd thing he was told he couldn't join the other children for recess until he added up all the numbers between 1 and 100. This was meant to be busy work, something to keep the young Gauss immersed in tedium. As the story goes, within minutes Gauss leapt up with the answer: 5050! There are several ways he could have done this, and I've heard different versions of the story. One way is geometric, and is closely related to the triangular numbers1
The other way is that Gauss recognized that the pairs of sums \({\color{black}{1+100=101}}\), \({\color{black}{2+99=101}}\), \({\color{black}{3+98=101}}\), \({\color{black}{}}\cdots\) were all equal, and with 50 such unique sums, this gives \({\color{black}{50}}\times101 = 5050\).

Instead of the numbers from 1 to 100, let's sum the numbers between 1 and 5 for this example. Take the \({\color{black}{5^{th}}}\) triangle in the sequence of Fig. 1, but left-align all the discs as in Figure 3 (a).

Fig. 3 Geometric proof of the expression \({\color{black}{}}\sum_{j=0}^i j = i(i+1)/2\) for the example case \({\color{black}{i=5}}\). (a) Start with the equilateral triangle with side 5 and left-align all the discs. (b) Form a rectangle by reflecting the triangle over the diagonal. Compute the area and divide by 2.

Then, reflect the triangle over its diagonal (the hypotenuse) to obtain the rectangle in Figure 3 (b). Now, instead of separately summing all the numbers from 1 to \({\color{black}{i}}\), it's enough to simply compute the area of the rectangle: \({\color{black}{i(i+1)}}\), and divide by 2. This way we arrive at the result Eq. (\ref{gauss}) without using the binomial coefficient.

In any case, the first few triangular numbers are \begin{equation*}{\color{black}{ \{T^2_i\} = \{0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,\cdots\}. }}\end{equation*} Perhaps just as interesting as the sequence itself is the set of numbers that take us from one element of the sequence to next. These are the gnomons: geometrically, they are the pieces that must be added to a figure to form a larger figure of the same shape. In our formulation, the gnomon is the number of discs that must be added to the \({\color{black}{i^{th}}}\) triangle to form the \({\color{black}{(i+1)^{th}}}\) triangle. The gnomons of the triangular numbers form the set \begin{equation*}{\color{black}{ \{g_i\} = \{T^2_{i+1}-T^2_i\} = \{1,2,3,4,5,6,7,8,9,10,\cdots\}, }}\end{equation*} which is the set of natural numbers, \({\color{black}{}}\mathbb{N}\). Besides just being a fun word to say, the set of gnomons has some interesting implications for the triangular numbers' higher-dimensional cousins. So, let's set the gnomons aside from a moment while we introduce the three-dimensional version of the triangle.

Higher-dimensional cousins

There is nothing special about triangles when it comes to figurate numbers. They happen to be the lowest dimensional form in the illustrious family of \({\color{black}{k}}\)-dimensional simplexes -- the generalizations of triangles to higher-dimensional spaces. The 3-dimensional cousin of the triangle is the tetrahedron (Figure 4 (a)), a 4 faced pyramid. We can go ahead and define the general \({\color{black}{k}}\)-simplex, but our brains fail to picture them in their full glory. For now, we'll content ourselves with the tetrahedron, and in particular, the set of numbers they inspire -- the tetrahedral numbers.

Fig. 4 (a) Tetrahedron. (b) Tetrahedron made of cannon balls.

As suggested in Figure 4 (b), we can build tetrahedrons out of stacks of balls. We can imagine constructing a sequence of such forms analogous to the triangular numbers: a single ball, a tetrahedron with three balls as a base, one with six, and so on. In fact, the base of \({\color{black}{i^{th}}}\) tetrahedron is formed by the \({\color{black}{i^{th}}}\) triangle of the series in Figure 1. To build the \({\color{black}{i^{th}}}\) tetrahedral number (which I'll reluctantly denote \({\color{black}{T^3_i}}\)), start with the \({\color{black}{i^{th}}}\) triangular number, \({\color{black}{T^2_i}}\), (as the base), then add the triangular number \({\color{black}{T^2_{i-1}}}\) as the next layer, then \({\color{black}{T^2_{i-2}}}\), and so on. Equivalently, it should be clear that one can dissect the tetrahedron of Figure 4 (b) into its constituent triangles from Figure 1 (the first four.) This observation yields a ready expression for the \({\color{black}{j^{th}}}\) tetrahedral number in terms of the triangular numbers, \begin{equation} \label{tetratri} {\color{black}{ T^3_j = \sum_{i=1}^j T^2_i. }}\end{equation} But like the triangular numbers, rather than deal with long sums we'd prefer a nice expression for \({\color{black}{T^3_j}}\) as a function of \({\color{black}{j}}\). And like the triangular numbers, we'll find it using combinatorics.

Consider a collection of five different color discs:

(Recall that for the triangular numbers we dealt with four different colors.) Instead of forming all the different pairs, this time we'll count the number of ways that we can select three discs (without replacement) from the set. We could graphically represent the 3-disc groupings like we did for the triangular numbers in Figure 2 (a), but it's messy. Instead, in Figure 5 the different 3-disc combinations are shown diagramatically: the first column includes the pairs of discs (as rows) that when grouped with the blue disc form the complete set of three-disc groupings with a blue disc, the next column the set of unique such groupings involving a green disc, and the last column, that for the red disc.

Fig. 5 The number of pairs of discs gives a representation of the tetrahedral number \({\color{black}{T^3_3}}\). Each column gives one of the component triangular numbers; the rows are the summands in the gnomon relation.

Notice that the number of pairs in the first column is \({\color{black}{}}\binom{4}{2}\) -- the triangular number \({\color{black}{T^2_3}}\), and so with the rest of the columns: \({\color{black}{}}\binom{3}{2} = T^2_2\), and \({\color{black}{}}\binom{2}{2} = T^2_1\). This agrees with the relation Eq. (\ref{tetratri}). So Figure 5, which was formed by examining the combinatorial problem of selecting three discs from among five, is a representation of \({\color{black}{T^3_3}}\); the general expression for the \({\color{black}{i^{th}}}\) tetrahedral number is then \begin{equation} \label{tetrabinom} {\color{black}{ T^3_i = \binom {i+2}{3}. }}\end{equation} With Eq. (\ref{tetratri}), we find a perhaps fortuitous route to the identify \begin{equation*}{\color{black}{ \sum_{i=0}^j \binom{i}{k} = \binom{j+1}{k+1}. }}\end{equation*} Now we're ready to revisit the triangular gnomons from last section. They provide an alternative and curious way to write the sums forming the tetrahedral numbers. Instead of building tetrahedra out of layers of equilateral triangles, we're going to use the triangular gnomons. Let's build the \({\color{black}{i=3}}\) tetrahedron from Figure 4 (b) using the gnomons of Figure 6:

Fig. 6 First three triangular gnomons.

Now, all three gnomons appear in the base (\({\color{black}{i=3}}\)) triangle of the tetrahedron, the first two form the next layer (\({\color{black}{i=2}}\)) triangle, and the first gnomon is the single ball on top. So there are three copies of \({\color{black}{g_1}}\), two of \({\color{black}{g_2}}\), and one of \({\color{black}{g_3}}\), or, \begin{equation*}{\color{black}{ T^3_3 = 3 \times g_1 + 2\times g_2 + 1\times g_3. }}\end{equation*} With \({\color{black}{g_3 = 3}}\), \({\color{black}{g_2 = 2}}\), and \({\color{black}{g_1 = 1}}\), this becomes, \begin{equation} \label{gnomonsum} {\color{black}{ T^3_3 = 3 \times 1 + 2\times 2 + 1 \times 3. }}\end{equation} These summands appear along the left in Figure 5. The first row has \({\color{black}{3}}\times 1\) pairs: 3 copies of 1 unique pair. The next two rows contain 2 copies each of 2 unique pairs, and the last three rows have 1 copy each of 3 unique pairs. So rather than think in terms of the triangular numbers, we can understand the tetrahedral numbers in terms of triangular gnomons, which can be written more generally as the expression \begin{equation} \label{gnomdef} {\color{black}{ T^3_j = \sum_{i=1}^j (j-i+1)i. }}\end{equation} Eq. (\ref{gnomdef}) has an interesting property: each product \({\color{black}{(j-1+1)i}}\) sums to \({\color{black}{j-1}}\), so the number of terms in the \({\color{black}{T^3_j}}\) summation is equal to the number of ways that one can write \({\color{black}{j+1}}\) as the sum of two integers. Writing out the first few tetrahedral numbers in this way reveals the remarkable triangle of summands:

Fig. 7 Triangle generated by Eq. (\ref{gnomdef}). Row \({\color{black}{j}}\) sums to \({\color{black}{T^3_j}}\).

The tetrahedral number, \({\color{black}{T^3_i}}\), is the sum of row \({\color{black}{i}}\); the triangular number \({\color{black}{T_i}}\) is the sum along the outer diagonal down to row \({\color{black}{i}}\); the \({\color{black}{2^{nd}}}\) number in each row is a multiple of 2, the \({\color{black}{3^{rd}}}\) a multiple of 3, and so on. But there's more: to generate a row, write down the first number of the row and then add it to each of the numbers in the row 2 before it to generate the rest of the numbers in the row. What's cool is that this triangle is directly connected to the combinatorial problem of selecting three objects from among five, but not in any obvious way.

There's another interesting thing about the expression Eq. (\ref{gnomonsum}). If we imagine that the gnomons form a vector, \({\color{black}{\bf{g}} = (g_1,g_2,\cdots,g_k)}\), then the expression Eq. (\ref{gnomonsum}) is evidently the scalar product of \({\color{black}{\bf{g}}}\) with its "reverse'', \({\color{black}{\bf{\bar{g}}} = (g_k,g_{k-1},\cdots,g_1)}\), \begin{equation} \label{gnomdot} {\color{black}{ T^3_k = {\bf{g}}\cdot{\bf{\bar{g}}} = g_1 g_k + g_2 g_{k-1} + \cdots + g_kg_1. }} \end{equation} In order to visualize this, we will consider \({\color{black}{T^3_2}}\) as an example so that we can work in two dimensional space. In this case \({\color{black}{\bf{g}} = (1,2)}\) and \({\color{black}{\bf{\bar{g}}} = (2,1)}\) is the reflection of \({\color{black}{\bf{g}}}\) about the line \({\color{black}{y=x}}\).

Fig. 8 Trigonometric representation of the tetrahedral number, \({\color{black}{T^3_2}}\), as proportional to the projection of the gnomon vector onto its reflection over \({\color{black}{y=x}}\).

In general, Eq. (\ref{gnomdot}) shows that the tetrahedral numbers are proportional to the projections of the gnomon vector, \({\color{black}{\bf{g}}}\), onto the vector \({\color{black}{\bf{\bar{g}}}}\) (see Figure 6), where the projections take place in \({\color{black}{k}}\)-dimensional space. This can be written \begin{equation*}{\color{black}{ \cos \theta_j = \frac{T^3_j}{|\bar{g}|^2}= \frac{T^3_j}{\sum_{i=1}^j i^2}. }}\end{equation*} The sum of the squares up to the number \({\color{black}{j}}\) is \({\color{black}{j(j+1)(2j+1)/6}}\), and from Eq. (\ref{tetrabinom}), \({\color{black}{T^3_j = j(j+1)(j+2)/6}}\), giving \begin{equation*}{\color{black}{ \cos \theta_j = \frac{j+2}{2j+1} }}\end{equation*} which, in the limit that \({\color{black}{j }}\rightarrow \infty\), gives \({\color{black}{}}\cos \theta_j = \frac{1}{2}\). This result tells us that the \({\color{black}{T^3_i}}\) grow more slowly than \({\color{black}{i^2}}\), while providing us with a new way to think about the tetrahedral numbers.

Lastly, the combinatoric expressions for the triangular and tetrahedral numbers suggest the following generalization, \begin{equation} \label{series} {\color{black}{ T^m = \binom {n + m -1}{m}, }}\end{equation} where \({\color{black}{m=2}}\) and \({\color{black}{m=3}}\) for triangular and tetrahedral numbers, respectively. The value of \({\color{black}{m}}\) is the number of dimensions needed to define the figures -- the \({\color{black}{m}}\)-simplexes. For \({\color{black}{m=4}}\), Eq. (\ref{series}) gives the pentatopic numbers, those based on the 4-simplex. Each of these sequences has a home in Pascal's triangle, for which the \({\color{black}{i^{th}}}\) element of row \({\color{black}{j}}\) is \({\color{black}{}}\binom{j}{i}\), where both indices start from zero. This means that the \({\color{black}{2^{nd}}}\) element of each row is a triangular number, the \({\color{black}{3^{rd}}}\) is a tetrahedral number, and so on. Seeing the sequences as part of the triangle gives you a good sense of just how fast they grow.

Fig. 9 Pascal's triangle. The third integer in each row is a triangular number (red); the fourth is a tetrahedral number (purple). The sequences formed by the digits beyond the fourth correspond to higher dimensional simplexes.

Download as PDF