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 + xA^{2}+ x^{3}A^{4}+ ....

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 + xA^{2}(1 + x^{2}A^{2}+ x^{4}A^{4}+ ....)

we may sum the geometric series and get

x^{2}A^{3}+ (x-x^{2})A^{2}- 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

F^{3}+ F^{2}- F - x( F^{2}- 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-gonsx + x^{2}+ 2x^{3}+ 6x^{4}+ 20x^{5}+ 71x^{6}+ 264x^{7}+ O(x^{8})

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 6x^{4} : 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 - F^{2}- F^{4}- F^{6}- F^{8}-...

It's interesting to note that the reciprocal of this series is 1/F + fib(1) + fib(2)F + fib(3)F^{2} +... , where fib(n) is the *n*th 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.

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 + x^{2}B^{3}+ x^{4}B^{5}+ ....

and, as above, to

2x^{2}B^{3}- x^{2}B^{2}- B + 1 =0

This time, let G=xB and get

2G^{3}- G - x( G^{2}- 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-gonsx + x^{3}+ 4x^{5}+ 21x^{7}+ 126x^{9}+ 818x^{11}+ 5594x^{13}+ 39693x^{15}+ O(x^{16})

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 g_{2n+1} is the number of "blobs with 2n+1 edges". It also gives a formula (!) for g_{2n+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 - G^{3}- G^{5}- G^{7}- G^{9}-...

but this time the reciprocal reads 1/G + 2^{0} G + 2^{1} G^{3} + 2^{2} G^{5} + 2^{3} G^{7} + ..., 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