login
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)).
2
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)).
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
KEYWORD
nonn
AUTHOR
Seiichi Manyama, Mar 25 2020
STATUS
approved