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

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

Author

Andrew Howroyd, Jan 29 2023

Keywords

• nonn
• easy

Examples

			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
		

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).

Crossrefs

Row 4 of A360196.

Programs

Mathematica

LinearRecurrence[{4, -6, 5, -2, -1, 1}, {0, 3, 9, 24, 58, 125}, 50] (* Paolo Xausa, Jun 24 2024 *)

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)

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)).