|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
| |
|
|
