[seqfan] polygon triangulation
Jim Nastos
nastos at gmail.com
Mon Mar 7 20:20:15 CET 2011
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
More information about the SeqFan
mailing list