A333514 Number of self-avoiding closed paths on an n X 4 grid which pass through four corners ((0,0), (0,3), (n-1,3), (n-1,0)).

1, 3, 11, 49, 229, 1081, 5123, 24323, 115567, 549253, 2610697, 12409597, 58988239, 280398495, 1332867179, 6335755801, 30116890013, 143160058769, 680508623307, 3234784886251, 15376488953815, 73091850448509, 347440733910081, 1651552982759797, 7850625988903223

Offset

2,2

Comments

Also number of self-avoiding closed paths on a 4 X n grid which pass through four corners ((0,0), (0,n-1), (3,n-1), (3,0)).

Links

Table of n, a(n) for n=2..26.

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

Formula

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

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

Example

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

Prog

(PARI) N=40; x='x+O('x^N); Vec(x^2*(1-4*x+2*x^2+x^3)/(1-7*x+12*x^2-7*x^3+3*x^4+2*x^5))
(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333513(n, k):
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    for i in [1, k, k * (n - 1) + 1, k * n]:
        cycles = cycles.including(i)
    return cycles.len()
def A333514(n):
    return A333513(4, n)
print([A333514(n) for n in range(2, 15)])

Crossrefs

Column k=4 of A333513.

Sequence in context: A025539 A172440 A254536 * A268414 A074528 A246985

Adjacent sequences: A333511 A333512 A333513 * A333515 A333516 A333517

Keyword

nonn

Author

Seiichi Manyama, Mar 25 2020

Status

approved