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

 

Logo

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.

Hints
(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)
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 A099335 A194930

Adjacent sequences:  A331232 A331233 A331234 * A331236 A331237 A331238

KEYWORD

nonn,easy

AUTHOR

David Eppstein, Jan 12 2020

STATUS

approved

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.)