login
A360197
Number of induced cycles in the 4 X n grid graph.
2
0, 3, 9, 24, 58, 125, 251, 490, 948, 1823, 3485, 6636, 12614, 23961, 45495, 86350, 163856, 310899, 589873, 1119144, 2123266, 4028261, 7642379, 14499018, 27507300, 52186343, 99006909, 187833924, 356354718, 676068905, 1282624071, 2433368030, 4616535768
OFFSET
1,2
FORMULA
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.
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)).
EXAMPLE
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.
The a(4) = 24 solutions for the 4 X 4 grid include:
O O O O . O O O O O O O
O . . O O O . O O . . O
O . O O O . O O O . . O
O O O . O O O . O O O O
MATHEMATICA
LinearRecurrence[{4, -6, 5, -2, -1, 1}, {0, 3, 9, 24, 58, 125}, 50] (* Paolo Xausa, Jun 24 2024 *)
PROG
(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)
CROSSREFS
Row 4 of A360196.
Sequence in context: A291706 A089830 A258111 * A109175 A120539 A357718
KEYWORD
nonn,easy
AUTHOR
Andrew Howroyd, Jan 29 2023
STATUS
approved