cp's OEIS Frontend

A331235 The number of simple polygons having all points of a 3 X n grid as vertices.

%I A331235 #13 Jan 14 2020 05:55:10
%S A331235 0,1,8,62,532,4846,45712,441458,4337468,43187630,434602280,4411598154,
%T A331235 45107210436,464047175770,4799184825632,49860914628042,
%U A331235 520109726201420,5444641096394926,57176049036449464,602125661090565914,6357215467283967404,67274331104623532042
%N A331235 The number of simple polygons having all points of a 3 X n grid as vertices.
%C A331235 The polygons are allowed to have flat angles (angles of exactly Pi) at some of the grid points. Empirically this sequence appears to be asymptotic to phi^(5n)/(66n), where phi is the golden ratio.
%H A331235 David Eppstein, <a href="https://11011110.github.io/blog/2020/01/12/counting-grid-polygonalizations.html">Counting grid polygonalizations</a>, Jan 12 2020
%o A331235 (Python)
%o A331235 from math import log
%o A331235 memo = {}
%o A331235 def K(x,y,z):
%o A331235     """Number of strings of length y from two sorted alphabets of lengths x,z"""
%o A331235     if (x,y,z) in memo:
%o A331235         return memo[(x,y,z)]
%o A331235     if y == 0:
%o A331235         result = 1
%o A331235     else:
%o A331235         # i = length of the last block of equal characters in the string
%o A331235         # xx or zz = the largest remaining character in its alphabet
%o A331235         result = (sum(K(xx,y-i,z) for xx in range(x) for i in range(1,y+1)) +
%o A331235                  sum(K(x,y-i,zz) for zz in range(z) for i in range(1,y+1)))
%o A331235     memo[(x,y,z)] = result
%o A331235     return result
%o A331235 def GC(n):
%o A331235     """Number of polygonalizations of 3xn grid"""
%o A331235     sum = 0
%o A331235     for i in range(n-1):    # number of points in K(...) can be up to n-2
%o A331235         mid = K(n-1,i,n-1)
%o A331235         for left in range(n-1-i):
%o A331235             right = n-2-i-left
%o A331235             contrib = mid
%o A331235             if left:
%o A331235                 contrib *= 2
%o A331235             if right:
%o A331235                 contrib *= 2
%o A331235             sum += contrib
%o A331235     return sum
%o A331235 def exponent(p):
%o A331235     return p**(-4*p) * (1-p)**(-2*(1-p)) * (1-2*p)**(-1*(1-2*p))
%o A331235 base = ( (1+5**0.5)/2 )**5
%o A331235 #for n in range(2,50):
%o A331235 #    print(n,(base**n/(66*n))/GC(n),GC(n))
%o A331235 [GC(n) for n in range(1,50)]
%K A331235 nonn,easy
%O A331235 1,3
%A A331235 _David Eppstein_, Jan 12 2020