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

0, 1, 8, 62, 532, 4846, 45712, 441458, 4337468, 43187630, 434602280, 4411598154, 45107210436, 464047175770, 4799184825632, 49860914628042, 520109726201420, 5444641096394926, 57176049036449464, 602125661090565914, 6357215467283967404, 67274331104623532042

Offset

1,3

Comments

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.

Links

Table of n, a(n) for n=1..22.

David Eppstein, Counting grid polygonalizations, Jan 12 2020

Prog

(Python)
from math import log
memo = {}
def K(x, y, z):
    """Number of strings of length y from two sorted alphabets of lengths x, z"""
    if (x, y, z) in memo:
        return memo[(x, y, z)]
    if y == 0:
        result = 1
    else:
        # i = length of the last block of equal characters in the string
        # xx or zz = the largest remaining character in its alphabet
        result = (sum(K(xx, y-i, z) for xx in range(x) for i in range(1, y+1)) +
                 sum(K(x, y-i, zz) for zz in range(z) for i in range(1, y+1)))
    memo[(x, y, z)] = result
    return result
def GC(n):
    """Number of polygonalizations of 3xn grid"""
    sum = 0
    for i in range(n-1):    # number of points in K(...) can be up to n-2
        mid = K(n-1, i, n-1)
        for left in range(n-1-i):
            right = n-2-i-left
            contrib = mid
            if left:
                contrib *= 2
            if right:
                contrib *= 2
            sum += contrib
    return sum
def exponent(p):
    return p**(-4*p) * (1-p)**(-2*(1-p)) * (1-2*p)**(-1*(1-2*p))
base = ( (1+5**0.5)/2 )**5
#for n in range(2, 50):
#    print(n, (base**n/(66*n))/GC(n), GC(n))
[GC(n) for n in range(1, 50)]

Crossrefs

Sequence in context: A190975 A287815 A244831 * A053095 A356461 A099335

Adjacent sequences: A331232 A331233 A331234 * A331236 A331237 A331238

Keyword

nonn,easy

Author

David Eppstein, Jan 12 2020

Status

approved