The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A331235 The number of simple polygons having all points of a 3 X n grid as vertices. 0
0, 1, 8, 62, 532, 4846, 45712, 441458, 4337468, 43187630, 434602280, 4411598154, 45107210436, 464047175770, 4799184825632, 49860914628042, 520109726201420, 5444641096394926, 57176049036449464, 602125661090565914, 6357215467283967404, 67274331104623532042 (list; graph; refs; listen; history; text; internal format)



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.


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

David Eppstein, Counting grid polygonalizations, Jan 12 2020



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


        # 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)]


Sequence in context: A190975 A287815 A244831 * A053095 A099335 A194930

Adjacent sequences:  A331232 A331233 A331234 * A331236 A331237 A331238




David Eppstein, Jan 12 2020



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 16:16 EST 2021. Contains 340270 sequences. (Running on oeis4.)