A365641 - OEIS

%I #13 Sep 25 2023 08:56:23

%S 1,3,7,14,25,41,63,92,128,173,228,293,369,458,561,676,807,955,1119,

%T 1300

%N The minimum number of ways to label each triangle of a triangulation of an n-gon with one of its vertices so that different triangles get different labels (minimum taken over all triangulations).

%C Originally proposed by Johan Wästlund, Aug 28 2007, as an equivalent formulation of A089187.

%C The "fan triangulations", where one vertex is connected to all other vertices, is optimal up to a(9). Starting from a(10)=128, other triangulations are better.

%e a(4)=7. Suppose a 4-gon ABCD is triangulated with triangles ABC and ACD. If ABC is labeled B, then ACD can be given 3 possible labels, while if ABC is labeled A or C, only 2 labels are available for ACD and 3+2+2=7. - Johan Wästlund, Aug 28 2007

%o (Python)

%o """For a chosen "base edge" of a triangulated (n+2)-gon, (ul, ur, u2)

%o denotes the numbers of labelings where the left, the right, or

%o both vertices of the base edge have been used as labels.

%o The number of labelings where none of the basepoints is used is always 1.

%o tri[n] will contain the possible triplets (ul,ur,u2) for the

%o triangulations of an (n+2)-gon."""

%o tri = [{(0,0,0)}] # start with single edge (2-gon); no labels

%o def combine(u,v):

%o     (ul,ur,u2),(vl,vr,v2) = u,v # formula obtained by combining the cases

%o     return (1+vl+ur+ul, 1+vl+ur+vr, vr+ul+(ul+ur)*(vl+vr)+u2+v2 )

%o for n in range(1,18): # dynamic programming, requires large memory

%o     tri.append({combine(u,v) for k in range(n)

%o                 for u in tri[k] for v in tri[n-k-1]})

%o print(", ".join(str(1+min(sum(t) for t in tr)) for tr in tri))

%K nonn,more

%O 2,2

%A _Günter Rote_, Sep 14 2023