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.
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.