3

In Knuth's book "The art of computer programming" Vol 1, p.52, there is a picture with the caption "Geometric interpretation of $\binom{n+2}{3}$, $n=4$" (see attached photo).

picture from Knuth's book

I cannot figure out what it is. I did notice that there are $\binom{4+2}{3}=20$ dots and each dot is at the intersection of exactly 3 straight lines (and I don't know why some are dotted). Any suggestions?

Math101
  • 1,106
  • DIdn't it occur to you to think why is it presented adjacent to a discussion about "Pascal's triangle"? – uniquesolution Jul 06 '19 at 20:55
  • Yes it did, but at most the picture illustrates that a certain sum along a column of Pascal's triangle is equal to $\binom{n+2}{3}$ (and this formula is only discussed two pages later). The picture doesn't give a geometric interpretation of $\binom{n+2}{3}$ itself. – Math101 Jul 06 '19 at 23:14

3 Answers3

3

The $n$th triangle number is the sum of the first $n$ positive integers. Therefore the $n$th triangle number is $$ \sum_{k=1}^n k = \frac{n(n+1)}{2} = \binom{n+1}{2}. $$ See this Wikipedia page for more information on triangle numbers.

The $n$th tetrahedral number is the sum of the first $n$ triangular numbers. The picture in Knuth's book is of the $4$th tetrahedral number: notice how each layer represents a triangle number. The $n$th tetrahedral number is $$ \sum_{k=1}^n \binom{k+1}{2} = \binom{n+2}{3}. $$ See this Wikipedia page for more information on tetrahedral numbers.

Travis Dillon
  • 153
  • Yes, this is clearly what the picture refers to. But I am still unhappy with the caption. It should say "geometric interpretation of $\sum_{k=1}^n\binom{k+1}{2}=\binom{n+2}{3}, n=4$". That is what the picture illustrates. To illustrate the binomial coefficient $\binom{4+2}{3}$ itself, I would look for its combinatorial meaning of choosing $3$ objects out of $4+2$ (and the reason for splitting $6$ into $4+2$ would still be unclear). Also, the summation formula in question is only presented two pages later. – Math101 Jul 06 '19 at 23:08
1

There is a song called The Twelve Days of Christmas. If you go through it carefully, the total number of gifts accumulated at day number $n$ is your $$ \binom{n+2}{3} = \frac{(n+2)(n+1)n}{6}$$ In particular, at the end of the song, we have completed $n=12$ days, total gifts $$ \frac{14 \cdot 13 \cdot 12}{6} = 364 $$

Wikipedia says it probably began as a memory game for children, each child would try to recite part of it...

The exact origins and the meaning of the song are unknown, but it is highly probable that it originated from a children's memory and forfeit game.

LYRICS

Will Jagy
  • 139,541
  • That is interesting. But I note that the book says "[binomial coefficients] appeared in Greek and Roman writings with a geometric interpretation (cf Fig. 8)" and Fig. 8 is the picture in question. Ancient Greek and Roman writers could not have the 12 days of Christmas in mind. – Math101 Jul 06 '19 at 23:22
  • @Math101 If you are in the US, you ought to be able to find a pool table, with a rack. Fifteen balls go in the layer directly on the table. If you have a supply of extras, you can then pile an additional twenty on that, making a triangular pyramid of thirty five. Again, $7 \cdot 6 \cdot 5 / 6 = 35.$ At the same time, i have no real idea what you were asking. – Will Jagy Jul 07 '19 at 00:17
  • Yes, if we sum the first $n$ triangular numbers $\binom{k+1}{2}$ we get $\binom{n+2}{3}$, and the picture in the book is a clear geometric illustration of that. But I was wondering why the author wrote that it is a geometric illustration of the binomial coefficient $\binom{n+2}{3}, n=4$. It is instead a geometric illustration of the formula that you describe with the billiard balls, that is not done until two pages later in the book. – Math101 Jul 07 '19 at 01:25
0

I believe this is called the Pascal Pyramid of monomials. It has a base of n = 4, and the 3 refers to the dimension. See this image of Labeled Coefficents . It counts the number of terms that are possible of a degree $\leq$ n-1.

There are 20 combinations of 3 variables that are of a degree $\leq 4-1$.

Conrad Crowley
  • 387