

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


LINKS



FORMULA

a(n) = 4*a(n1)  6*a(n2) + 5*a(n3)  2*a(n4)  a(n5) + a(n6) 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


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



STATUS

approved



