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