|
%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
|
