Tuesday, December 15, 2009

a Catalan number triangle fractal

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845...
                                                     the Catalan Numbers, OEIS: A000108

Catalan numbers occur in a surprising number of counting scenarios, such as counting the ways convex polygons can be cut into triangles, or counting how many ways you can write down a  legal list of brackets (a legal list of brackets is something like this: {{}{}}). In The Book of Numbers, Conway and Guy present at least eight different scenarios that the Catalans count, and Richard Stanley has listed 173 combinatorial interpretations for them (see the chapter and addendum on his Enumerative Combinatorics website). What unites these seemingly different scenarios is their recursive character (polygons contain smaller polygons, and lists of brackets contain smaller lists).

The Catalan numbers can be found in Pascal's Triangle  in a few ways. If you take each 'middle' element and subtract its adjacent entry, you get a Catalan number. Also, if you take a middle element and divide it by its position in the list of middle terms (e.g. divide the 5th middle term by 5), you will get a Catalan number. But Catalans have their very own number triangle too.

Starting, as with Pascal's Triangle, with a 1, the Catalan Triangle is generated using the rule that each element is equal to the one above (in this picture, above on the right slanting diagonal) plus the one to its left (where 'missing' numbers are zero).  The Catalan numbers show up both as row sums and as the last entry in each row.

The rule for creating the Catalan Triangle sounds like a 'slanted' version of the generating rule for the Pascal Triangle (where to produce a number you take the sum of the two above its position), and if you look at the fractal that is created by looking at the Catalan Triangle's values mod 2 (so that even numbers are replaced with 0 and odd numbers are replaced with 1), you get a slanted version of the Sierpinski fractal that you get from doing the same with Pascal's Triangle.

The fractals that sometimes arise from looking at modular values in a number triangle provide a visual clue to the divisibility properties of the numbers in the triangle, and also illustrate some aspects of the generating rule that is used to create the triangle. The Catalan fractal above was made with this Tinkerplots file using this data. The Pascal Traiangle was drawn with Tinkerplots using this file as described here.