Friezes and Catalan numbers
A Conway–Coxeter frieze is an infinitely wide checkerboard of positive integers, such as the one in the picture above. Conway–Coxeter friezes were introduced in 1973 by John H. Conway (1937–2020) and H.S.M. Coxeter (1907–2003), and the friezes are required to satisfy the following two conditions.
1. There are finitely many rows, and all of the entries in the top and the bottom row must be equal to 1.
2. If a, b, c, and d are four numbers surrounding a particular empty square to its left, top, bottom, and right respectively, then the numbers must satisfy the unimodular law, meaning that ad–bc = 1.
A concept that at first seems unrelated to friezes is that of a triangulation of a convex n-gon. This is a way to slice the n-gon into non-overlapping triangles in such a way that the corners of each triangle are three of the corners of the original n-gon. The picture above shows that there is 1 triangulation of a triangle, 2 triangulations of a square, 5 triangulations of a pentagon, and 14 triangulations of a hexagon. In each case, a triangulation of an n-gon requires n–2 triangles, so that for example one needs 4 triangles to triangulate a hexagon.
Consider the triangulation of the heptagon shown in the picture above. If we count the number of triangles that meet at each vertex of the heptagon, working clockwise from the top vertex, we obtain the sequence 4, 2, 1, 3, 2, 2, 1. The second to bottom row of the frieze (above the bottom row of 1s) also contains the sequence 4, 2, 1, 3, 2, 2, 1, in an infinitely repeating pattern. The same repeating sequence shows up in the second to top row of the frieze, below the top row of 1s.
The width of a Conway–Coxeter frieze is the number of rows in the frieze excluding the top and bottom rows of 1s; for example, the frieze shown in the animation has width 4. Conway and Coxeter proved that, for a fixed n, there is a one to one correspondence between Conway–Coxeter friezes of width n–3 on the one hand, and triangulations of a convex n-gon on the other hand.
Recall from earlier that the number of triangulations of an n-gon for n=3, 4, 5, 6, … is given by a sequence that starts “1, 2, 5, 14”. This is a famous sequence known as the Catalan numbers, whose formula is given above. For example, to calculate the 4th Catalan number, C4, one takes the binomial coefficient (8 choose 4), which is 70, and divides it by 5, to obtain 14. The n-th Catalan number calculates the number of triangulations of an (n+2)-gon, so this proves that there are 14 triangulations of a hexagon.
The Catalan numbers have a huge number of combinatorial interpretations, including the two mentioned above in terms of friezes and triangulations. The n-th Catalan number also counts the number of ways of writing a sequence of n open-parentheses and n close-parentheses in such a way that the parentheses balance. For example, if n is 3, then there are C3=5 ways to write a balanced sequence of parentheses of length 6, namely ()()(), ()(()), (())(), (()()), and ((())). Another more visual example is shown above: the Catalan number Cn counts the number of ways to stack coins in the plane, so that the bottom row consists of n consecutive coins. For example, the picture above shows the 5 ways to stack coins in the plane so that the bottom row consists of 3 coins.
Picture credits and relevant links
The diagram of the stacked coins and the triangulations of the n-gons for n=3, 4, 5, and 6 come from the 2015 book Catalan numbers by Richard P. Stanley. The animation and the other two diagrams are my own work.
Wikipedia has entries on John H. Conway and H.S.M. Coxeter.
The Catalan numbers are named after Eugène Charles Catalan (1814–1894), and are one of the most famous sequences of integers. Stanley’s book gives 214 interpretations of the Catalan numbers, including all the ones mentioned in this post. The entry for the Catalan numbers in the On-Line Encyclopedia of Integer Sequences states that “This is probably the longest entry in the OEIS, and rightly so.”
Despite their recreational appearance, Conway–Coxeter friezes eventually turned out to have connections to other important areas of modern mathematical research, including the cluster algebras of Fomin and Zelevinsky. A good introduction to this topic is the 2013 paper Coxeter Friezes and Triangulations of Polygons by Claire-Soizic Henry.
Substack management by Buzz & Hum.