A333760 Number of self-avoiding closed paths in the 4 X n grid graph which pass through all vertices on four (left, right, upper, lower) sides of the graph.

1, 3, 11, 36, 122, 408, 1371, 4599, 15437, 51804, 173860, 583476, 1958173, 6571695, 22054863, 74016936, 248403622, 833651844, 2797766831, 9389410251, 31511212505, 105752809368, 354910389192, 1191092559048, 3997351239929, 13415260479675, 45022116630931

Offset: 2

Author

Seiichi Manyama, Apr 04 2020

Keywords

• nonn

Examples

			a(2) = 1;
   +--+
   |  |
   +  +
   |  |
   +  +
   |  |
   +--+
a(3) = 3;
   +--+--+   +--+--+   +--+--+
   |     |   |     |   |     |
   +--*  +   +  *--+   +     +
      |  |   |  |      |     |
   +--*  +   +  *--+   +     +
   |     |   |     |   |     |
   +--+--+   +--+--+   +--+--+
		

Links

• Index entries for linear recurrences with constant coefficients, signature (3,2,-3,1).

Crossrefs

Row 4 of A333758.

Programs

PARI

N=40; x='x+O('x^N); Vec(x^2/(1-3*x-2*x^2+3*x^3-x^4))

Python

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333758(n, k):
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    points = [i for i in range(1, k * n + 1) if i % k < 2 or ((i - 1) // k + 1) % n < 2]
    for i in points:
        cycles = cycles.including(i)
    return cycles.len()
def A333760(n):
    return A333758(4, n)
print([A333760(n) for n in range(2, 15)])

Formula

G.f.: x^2/(1-3*x-2*x^2+3*x^3-x^4).

a(n) = 3*a(n-1) + 2*a(n-2) - 3*(a-3) + a(n-4) for n > 5.