A291444 Number of symmetric maximal irredundant sets in the n-path graph.

1, 0, 2, 2, 2, 2, 3, 3, 5, 6, 7, 6, 10, 12, 15, 15, 22, 23, 33, 35, 48, 48, 71, 75, 103, 106, 152, 158, 225, 234, 329, 338, 484, 505, 710, 734, 1044, 1084, 1536, 1594, 2257, 2335, 3317, 3444, 4871, 5047, 7161, 7429, 10528, 10916, 15470, 16033, 22737, 23582

Offset: 1

Author

Andrew Howroyd, Aug 23 2017

Keywords

• nonn

Examples

			Case n=5: maximal irredundant sets represented as binary words are {00110, 01001, 01010, 01100, 10010, 10101}. Of these, only 01010 and 10101 are symmetrical, so a(5) = 2.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Eric Weisstein's World of Mathematics, Maximal Irredundant Set
• Eric Weisstein's World of Mathematics, Path Graph
• Index entries for linear recurrences with constant coefficients, signature (0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, -1, 0, -2, 0, -1, 0, 2, 0, 1, 0, 0, 0, 0, 0, -1).

Crossrefs

Cf. A291055.

Programs

PARI

Vec((1 + 2*x^2 + 2*x^3 + x^4 + 2*x^5 + x^7 + 2*x^9 - x^10 - x^11 - 2*x^12 - x^13 - x^14 - 2*x^15 + x^16 - 2*x^17 + 3*x^18 + 2*x^19 + x^20 + x^21 - x^22 - x^24 - x^26 - x^27)/(1 - x^4 - x^6 - x^8 - x^10 + x^14 + 2*x^16 + x^18 - 2*x^20 - x^22 + x^28) + O(x^50))

Formula

a(n) = a(n-4) + a(n-6) + a(n-8) + a(n-10) - a(n-14) - 2*a(n-16) - a(n-18) + 2*a(n-20) + a(n-22) - a(n-28) for n > 28.

G.f.: x*(1 + 2*x^2 + 2*x^3 + x^4 + 2*x^5 + x^7 + 2*x^9 - x^10 - x^11 - 2*x^12 - x^13 - x^14 - 2*x^15 + x^16 - 2*x^17 + 3*x^18 + 2*x^19 + x^20 + x^21 - x^22 - x^24 - x^26 - x^27)/(1 - x^4 - x^6 - x^8 - x^10 + x^14 + 2*x^16 + x^18 - 2*x^20 - x^22 + x^28).