A332349 Number of maximal independent sets in the 4 X n king graph.

1, 3, 12, 22, 79, 194, 537, 1519, 4011, 11258, 30506, 83661, 229754, 627171, 1721547, 4710045, 12901630, 35342272, 96764537, 265067580, 725878627, 1988023833, 5444771405, 14911382924, 40839083772, 111846316151, 306317816028, 838924085421, 2297583803229, 6292480053823

Offset: 0

Author

Andrew Howroyd, Feb 10 2020

Keywords

• nonn
• easy

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..500
• Index entries for linear recurrences with constant coefficients, signature (1,4,3,-4,6,-3,-6).

Crossrefs

Row n=4 of A332347.

Programs

PARI

Vec((1 + 2*x + 5*x^2 - 5*x^3 + 4*x^4 - 3*x^5 - 6*x^6)/((1 - x)*(1 - 4*x^2 - 7*x^3 - 3*x^4 - 9*x^5 - 6*x^6)) + O(x^40))

Formula

a(n) = a(n-1) + 4*a(n-2) + 3*a(n-3) - 4*a(n-4) + 6*a(n-5) - 3*a(n-6) - 6*a(n-7) for n >= 7.

G.f.: (1 + 2*x + 5*x^2 - 5*x^3 + 4*x^4 - 3*x^5 - 6*x^6)/((1 - x)*(1 - 4*x^2 - 7*x^3 - 3*x^4 - 9*x^5 - 6*x^6)).