OFFSET
1,2
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (4,-6,5,-2,-1,1).
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
KEYWORD
nonn,easy
AUTHOR
Andrew Howroyd, Jan 29 2023
STATUS
approved