|
%I #46 Mar 28 2020 05:19:33
%S 1,3,11,49,229,1081,5123,24323,115567,549253,2610697,12409597,
%T 58988239,280398495,1332867179,6335755801,30116890013,143160058769,
%U 680508623307,3234784886251,15376488953815,73091850448509,347440733910081,1651552982759797,7850625988903223
%N 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)).
%C 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)).
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (7,-12,7,-3,-2).
%F 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).
%F 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.
%e a(2) = 1;
%e +--*--*--+
%e | |
%e +--*--*--+
%e a(3) = 3;
%e +--*--*--+ +--*--*--+ +--* *--+
%e | | | | | | | |
%e * *--* * * * * *--* *
%e | | | | | | | |
%e +--* *--+ +--*--*--+ +--*--*--+
%e a(4) = 11;
%e +--*--*--+ +--*--*--+ +--*--*--+
%e | | | | | |
%e *--*--* * *--* *--* *--* *
%e | | | | | |
%e *--*--* * *--* *--* *--* *
%e | | | | | |
%e +--*--*--+ +--*--*--+ +--*--*--+
%e +--*--*--+ +--*--*--+ +--*--*--+
%e | | | | | |
%e * *--*--* * *--* * * *--*
%e | | | | | | | |
%e * *--*--* * * * * * *--*
%e | | | | | | | |
%e +--*--*--+ +--* *--+ +--*--*--+
%e +--*--*--+ +--*--*--+ +--* *--+
%e | | | | | | | |
%e * * * * * *--* *
%e | | | | | |
%e * *--* * * * * *--* *
%e | | | | | | | | | |
%e +--* *--+ +--*--*--+ +--* *--+
%e +--* *--+ +--* *--+
%e | | | | | | | |
%e * *--* * * * * *
%e | | | | | |
%e * * * *--* *
%e | | | |
%e +--*--*--+ +--*--*--+
%o (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))
%o (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o import graphillion.tutorial as tl
%o def A333513(n, k):
%o universe = tl.grid(n - 1, k - 1)
%o GraphSet.set_universe(universe)
%o cycles = GraphSet.cycles()
%o for i in [1, k, k * (n - 1) + 1, k * n]:
%o cycles = cycles.including(i)
%o return cycles.len()
%o def A333514(n):
%o return A333513(4, n)
%o print([A333514(n) for n in range(2, 15)])
%Y Column k=4 of A333513.
%K nonn
%O 2,2
%A _Seiichi Manyama_, Mar 25 2020
| 