cp's OEIS Frontend

A365641 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).

%I A365641 #13 Sep 25 2023 08:56:23
%S A365641 1,3,7,14,25,41,63,92,128,173,228,293,369,458,561,676,807,955,1119,
%T A365641 1300
%N A365641 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 A365641 Originally proposed by Johan Wästlund, Aug 28 2007, as an equivalent formulation of A089187.
%C A365641 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 A365641 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 A365641 (Python)
%o A365641 """For a chosen "base edge" of a triangulated (n+2)-gon, (ul, ur, u2)
%o A365641 denotes the numbers of labelings where the left, the right, or
%o A365641 both vertices of the base edge have been used as labels.
%o A365641 The number of labelings where none of the basepoints is used is always 1.
%o A365641 tri[n] will contain the possible triplets (ul,ur,u2) for the
%o A365641 triangulations of an (n+2)-gon."""
%o A365641 tri = [{(0,0,0)}] # start with single edge (2-gon); no labels
%o A365641 def combine(u,v):
%o A365641     (ul,ur,u2),(vl,vr,v2) = u,v # formula obtained by combining the cases
%o A365641     return (1+vl+ur+ul, 1+vl+ur+vr, vr+ul+(ul+ur)*(vl+vr)+u2+v2 )
%o A365641 for n in range(1,18): # dynamic programming, requires large memory
%o A365641     tri.append({combine(u,v) for k in range(n)
%o A365641                 for u in tri[k] for v in tri[n-k-1]})
%o A365641 print(", ".join(str(1+min(sum(t) for t in tr)) for tr in tri))
%K A365641 nonn,more
%O A365641 2,2
%A A365641 _Günter Rote_, Sep 14 2023