[seqfan] Re: polygon triangulation

Roland Bacher Roland.Bacher at ujf-grenoble.fr
Tue Mar 8 08:40:10 CET 2011

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 


and A,B are defined recursively by


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/

More information about the SeqFan mailing list