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,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

Row 4 of A360196.

Sequence in context: A291706 A089830 A258111 * A109175 A120539 A357718

Adjacent sequences: A360194 A360195 A360196 * A360198 A360199 A360200

Keyword

nonn,easy

Author

Andrew Howroyd, Jan 29 2023

Status

approved