[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
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/
More information about the SeqFan
mailing list