[seqfan] Re: polygon triangulation

[Roland Bacher]

Denote by A the generating series (with respect to the number of vertices
n) of all such "cutted" polygons which
have a marked boundary edge incident in a triangle. A=t^3+....

Similarly, let B be the series with a marked edge incident in  
a quadrilateral: B=t^4+...

The solution is then 

t^2+A+B

and A,B are defined recursively by
 
A=1/t(t^2+B)^2

B=1/t^2(t^2+A+B)^3

In particular, the solution is algebraic (and can be found 
using Groebner bases).

Roland Bacher

On Mon, Mar 07, 2011 at 11:20:15AM -0800, Jim Nastos wrote:
> Hi,
>   It is well-known that the number of ways of adding diagonals to a polygon
> in order to cut it into triangles is the Catalan numbers, and a recurrence
> is easy to derive for this sort of counting problem.
>   Does anyone know of a relaxation to the problem which would ask to find
> the number of ways of adding diagonals to a (simple) n-sided polygon in
> order to cut it into regions that are either triangles or quadrilaterals?
> Building a recurrence for this does not seem as simple.
> 
>   I would be interested in any related study. Ideally, I would like to count
> the number of *minimal* diagonal sets (a partitioning would not be minimal
> if, for instance, there were two triangles created that share a diagonal as
> an edge... that shared diagonal could be removed to turn the two triangles
> to a 4-gon, giving a smaller diagonal set size.)
> 
>   The sequence of such *minimal* diagonal-set sizes would start:
> a(4)=1
> a(5)=5
> a(6)=12(?)
> a(7)=28(?)
> (by hand, so these are unconfirmed.)
> 
>   Any reference pointers? Thanks,
> JN
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/