My last post ended with the strong hint that I may not have been finished with this topic.
In part 4, triangular numbers were used as a first simplification to computing the total number of gifts for the 12 days of Christmas by eliminating some additions.
It turns out that the polynomial from part 5 is the equation for the class of tetrahedral numbers.
I wanted to determine the optimal solution from first principles and experimentation. The triangular numbers link was found through serendipity (listening to an unrelated podcast). I learned about tetrahedral numbers through further reading after finishing part 7.
In a Wikipedia article about the 12 days of Christmas song, Donald Knuth’s analysis of computational complexity is mentioned and then as an afterthought:
Incidentally, it is also observed that the total number of gifts after m days equals m3 / 6 + m2 / 2 + m / 3.
which is the polynomial we saw from part 5.
One thing led to another and I came across another Wikipedia page about tetrahedral numbers that are computed with this function. The name of the class of numbers arises from the fact that such numbers can be modelled by stacking spherical balls into a tetrahedron, as illustrated with this nice 3D graphic:
The number of balls in each layer is a triangular number. The number of balls in the tetrahedron is the nth tetrahedral number, and also the number of gifts for the nth day of Christmas.
gifts-for-day-of-xmasn = 1 ball in layer1 + 3 balls in layer2 + 6 balls in layer3 + … + n(n+1)/2 balls in layern
There is also a relationship to the problem of finding the optimal way to stack canon balls worked on by Johannes Kepler (one of my heroes, who realised that planetary orbits are elliptical, not circular), but that’s a different post.
Here are some other interesting things I found along the way:
- The year that most of the thought went into my posts was 2024, which turns out to be the 22nd tetrahedral number.
- Ian Phillipps won an Obfuscated C competition in 1988 with a C program that generates the text of the 12 days of Christmas song. The code was described by the judges as “…like what you would get by pounding on the keys of an old typewriter at random”, and as the same Wikipedia article goes on to say: “…takes advantage of the recursive structure of the song to print its lyrics with code that is shorter than the lyrics themselves.”
- There’s a proof by induction for the tetrahedral numbers for all n that uses the equation for triangular numbers in the inductive step. This deserves further discussion, and perhaps I will return to this from another viewpoint in future.
- The nth tetrahedral number is represented by the 3rd rising factorial of n divided by the factorial of 3. This yields a slightly more compact equation than the polynomial, but is just another way of expressing it, so is no better computationally. The equality-related expressions below partially recapitulate the explorations throughout this series of posts, with the rising factorial form at right (source: Wikipedia).
- The 4th diagonal of Pascal’s triangle (built from binomial coefficients) contains the tetrahedral numbers (from left or right). The triangular numbers are in the 3rd diagonal, and the counting numbers are in the 2nd diagonal.
source: https://sahilmohnani.wordpress.com/2013/02/23/pascals-triangle-cubic-quartic-and-sextic-numbers/
It seems that the avenues down which one could stroll in relation to this topic are never-ending.
I can’t promise not to ever return to it, but it’s time to move on I think, at least for now.