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