[seqfan] Re: polygon triangulation
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).
On Mon, Mar 07, 2011 at 11:20:15AM -0800, Jim Nastos wrote:
> 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:
> (by hand, so these are unconfirmed.)
> Any reference pointers? Thanks,
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan