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

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).

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).

Example

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.

Prog

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

Crossrefs

Cf. A291055.

Sequence in context: A005858 A285798 A321346 * A219795 A082602 A216644

Adjacent sequences: A291441 A291442 A291443 * A291445 A291446 A291447

Keyword

nonn

Author

Andrew Howroyd, Aug 23 2017

Status

approved