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