cp's OEIS Frontend

A333760 Number of self-avoiding closed paths in the 4 X n grid graph which pass through all vertices on four (left, right, upper, lower) sides of the graph.

%I A333760 #18 Apr 04 2020 21:22:37
%S A333760 1,3,11,36,122,408,1371,4599,15437,51804,173860,583476,1958173,
%T A333760 6571695,22054863,74016936,248403622,833651844,2797766831,9389410251,
%U A333760 31511212505,105752809368,354910389192,1191092559048,3997351239929,13415260479675,45022116630931
%N A333760 Number of self-avoiding closed paths in the 4 X n grid graph which pass through all vertices on four (left, right, upper, lower) sides of the graph.
%H A333760 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,2,-3,1).
%F A333760 G.f.: x^2/(1-3*x-2*x^2+3*x^3-x^4).
%F A333760 a(n) = 3*a(n-1) + 2*a(n-2) - 3*(a-3) + a(n-4) for n > 5.
%e A333760 a(2) = 1;
%e A333760    +--+
%e A333760    |  |
%e A333760    +  +
%e A333760    |  |
%e A333760    +  +
%e A333760    |  |
%e A333760    +--+
%e A333760 a(3) = 3;
%e A333760    +--+--+   +--+--+   +--+--+
%e A333760    |     |   |     |   |     |
%e A333760    +--*  +   +  *--+   +     +
%e A333760       |  |   |  |      |     |
%e A333760    +--*  +   +  *--+   +     +
%e A333760    |     |   |     |   |     |
%e A333760    +--+--+   +--+--+   +--+--+
%o A333760 (PARI) N=40; x='x+O('x^N); Vec(x^2/(1-3*x-2*x^2+3*x^3-x^4))
%o A333760 (Python)
%o A333760 # Using graphillion
%o A333760 from graphillion import GraphSet
%o A333760 import graphillion.tutorial as tl
%o A333760 def A333758(n, k):
%o A333760     universe = tl.grid(n - 1, k - 1)
%o A333760     GraphSet.set_universe(universe)
%o A333760     cycles = GraphSet.cycles()
%o A333760     points = [i for i in range(1, k * n + 1) if i % k < 2 or ((i - 1) // k + 1) % n < 2]
%o A333760     for i in points:
%o A333760         cycles = cycles.including(i)
%o A333760     return cycles.len()
%o A333760 def A333760(n):
%o A333760     return A333758(4, n)
%o A333760 print([A333760(n) for n in range(2, 15)])
%Y A333760 Row 4 of A333758.
%K A333760 nonn
%O A333760 2,2
%A A333760 _Seiichi Manyama_, Apr 04 2020