cp's OEIS Frontend

A360197 Number of induced cycles in the 4 X n grid graph.

%I A360197 #18 Jun 24 2024 18:06:17
%S A360197 0,3,9,24,58,125,251,490,948,1823,3485,6636,12614,23961,45495,86350,
%T A360197 163856,310899,589873,1119144,2123266,4028261,7642379,14499018,
%U A360197 27507300,52186343,99006909,187833924,356354718,676068905,1282624071,2433368030,4616535768
%N A360197 Number of induced cycles in the 4 X n grid graph.
%H A360197 Andrew Howroyd, <a href="/A360197/b360197.txt">Table of n, a(n) for n = 1..1000</a>
%H A360197 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,5,-2,-1,1).
%F A360197 a(n) = 4*a(n-1) - 6*a(n-2) + 5*a(n-3) - 2*a(n-4) - a(n-5) + a(n-6) for n > 6.
%F A360197 G.f.: x^2*(3 - 3*x + 6*x^2 + x^3 - 2*x^4)/((1 - x)^2*(1 - 2*x + x^2 - x^3 - x^4)).
%e A360197 The a(3) = 9 chordless cycles consist of six 1 X 1 squares (covering 4 vertices), four 2 X 2 squares and one 2 X 3 rectangle.
%e A360197 The a(4) = 24 solutions for the 4 X 4 grid include:
%e A360197     O O O O     . O O O    O O O O
%e A360197     O . . O     O O . O    O . . O
%e A360197     O . O O     O . O O    O . . O
%e A360197     O O O .     O O O .    O O O O
%t A360197 LinearRecurrence[{4, -6, 5, -2, -1, 1}, {0, 3, 9, 24, 58, 125}, 50] (* _Paolo Xausa_, Jun 24 2024 *)
%o A360197 (PARI) seq(n) = Vec(x*(3 - 3*x + 6*x^2 + x^3 - 2*x^4)/((1 - x)^2*(1 - 2*x + x^2 - x^3 - x^4)) + O(x^n), -n)
%Y A360197 Row 4 of A360196.
%K A360197 nonn,easy
%O A360197 1,2
%A A360197 _Andrew Howroyd_, Jan 29 2023