Dissections and Reversions

More Fun with Polygon Dissections (4dz)

Len Smiley, Univ. of Alaska Anchorage

Odd-gon Tiles

We consider the following variant of the dissection questions of Catalan, Schroeder, [etc.]. In a convex (n+2)-gon with n+2 labeled nodes, what is a(n), the number of ways of drawing non-intersecting diagonals so that no 2m-gons (m>1) appear in the tiling which results?

The generating function for a(n), A(x), satisfies the "rebus" equation

A = 1 + xA2 + x3A4 + ....

derived by interpreting


                            /\ 
                          A/  \A
               /\         /    \
             A/  \A      A\    /A
A = ___  +   /____\   +    \__/    + ....

The idea is that the baseline in each term is edge 1--2 of the (n+2)-gon and sitting above it (or not) is the diagonal-free k-gon of which it is the 'bottom'. We must let A's grow from each other side of this k-gon to assemble all the pictures we're counting. Now because

A = 1 + xA2 (1 + x2A2 + x4A4 + ....)

we may sum the geometric series and get

x2A3 + (x-x2)A2 - A + 1 =0

This is not quite ready for series reversion, so we do a simple trick: we multiply the last equation by x, and, writing F=xA, we find

F3 + F2 - F - x( F2 - 1 ) = 0

which makes it easy to solve for x. Now we bring in some help in the form of basic Maple coding:


> Order:=8;
> solve(series((F-F^2-F^3)/(1-F^2),F)=x,F); #dissections of (n+1)-gon into odd-gons

x + x2 + 2x3 + 6x4 + 20x5 + 71x6 + 264x7 + O(x8)

That was fun, but is it right? Only the first five terms are easy to check: first, the term 1x says that the 2-gon may be diagonalized in 1 way (i.e. by not diagonalizing). Even though 2 is even, we have to allow 2-gons in our pictures - otherwise there'd be no sides! Let's skip to 6x4 : every pair of non-crossing diagonals is given by its vertex of emanation, so there are 5 ways to cut the pentagon into 3 triangles; leaving the pentagon alone makes 6.

The mathematical level of the preceding might seem rather low - the "solve" function in Maple is probably just inverting a triangular matrix. We notice also that the series being reverted is nothing but

S =  F -  F2 -  F4 -  F6 - F8 -... 

It's interesting to note that the reciprocal of this series is 1/F + fib(1) + fib(2)F + fib(3)F2 +... , where fib(n) is the nth number in the Fibonacci sequence 1,1,2,3,5,8,...

So compositional inverse of S counts dissections of the n-gon into odd-gons, and multiplicative inverse counts rabbit-pairs in the n-th generation.


Even-gon Tiles

In a previous E-print, A Nameless Number , we calculated the number of polygon dissections by non-crossing diagonals allowing no triangles in the resultant tiling. This resulted in a "rookie" integer sequence. If we disallow any odd-gons( (2m-1)-gons with m>1 ), we find a "veteran" sequence doing the counting job. Let


                            _B_ 
                          B/   \B
              _B_         /     \
            B|   |B      B\     /B
B = ___  +   |___|   +     \___/     + ....

as usual (B is the power series generating function for our dissections of the (n+2)-gon), leading to

B = 1 + x2B3 + x4B5 + ....

and, as above, to

2x2B3 - x2B2 - B + 1 =0

This time, let G=xB and get

2G3 - G - x( G2 - 1 ) = 0

We rush over to our silicon-based friend for the answers


> Order:=16;
> solve(series((G-2*G^3)/(1-G^2),G)=x,G); #dissections of (n+1)-gon into even-gons

x + x3 + 4x5 + 21x7 + 126x9 + 818x11 + 5594x13 + 39693x15 + O(x16)

That's nice: it's 'verifying' that you can't tile an odd-gon with even-gons using non-crossing diagonals. Let's check the octagon: there are 4 ways to isert two parallel diagonals, forming three quadrilaterals each time. As for single diagonal placements, there are 8 ways to connect a vertex with its third clockwise neighbor and 8 ways counterclockwise (each of the 16 makes a quad and a hex). Placing no diagonals makes 21.

A trip to the On-Line Encyclopedia of Integer Sequences is called for! It indicates (cf. A003168) that the sequence 1,1,4,21,126,... has been well-studied in the past. The name of the sequence indicates that our coefficient g2n+1 is the number of "blobs with 2n+1 edges". It also gives a formula (!) for g2n+1 as sum of products of binomial coefficients. If we use the Lagrange Inversion Formula and some elbow-grease for our reversion instead of plain algebra, we can get the same formula.



We can't resist checking the multiplicative inverse of

T =  G  -  G3 -  G5 -  G7 - G9 -... 

but this time the reciprocal reads 1/G + 20 G + 21 G3 + 22 G5 + 23 G7 + ..., so we have a famous growth sequence, but no rabbits.


Leonard Smiley
Created: Wed Jun 16 14:41:05 AKDT 1999 Last modified: Wed Jun 16 10:26:38 AKDT 1999