(Python)
"""For a chosen "base edge" of a triangulated (n+2)-gon, (ul, ur, u2)
denotes the numbers of labelings where the left, the right, or
both vertices of the base edge have been used as labels.
The number of labelings where none of the basepoints is used is always 1.
tri[n] will contain the possible triplets (ul, ur, u2) for the
triangulations of an (n+2)-gon."""
tri = [{(0, 0, 0)}] # start with single edge (2-gon); no labels
def combine(u, v):
(ul, ur, u2), (vl, vr, v2) = u, v # formula obtained by combining the cases
return (1+vl+ur+ul, 1+vl+ur+vr, vr+ul+(ul+ur)*(vl+vr)+u2+v2 )
for n in range(1, 18): # dynamic programming, requires large memory
tri.append({combine(u, v) for k in range(n)
for u in tri[k] for v in tri[n-k-1]})
print(", ".join(str(1+min(sum(t) for t in tr)) for tr in tri))
|