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

%I #9 Oct 15 2017 01:09:43

%S 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,

%T 152,158,225,234,329,338,484,505,710,734,1044,1084,1536,1594,2257,

%U 2335,3317,3444,4871,5047,7161,7429,10528,10916,15470,16033,22737,23582

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

%H Andrew Howroyd, <a href="/A291444/b291444.txt">Table of n, a(n) for n = 1..200</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIrredundantSet.html">Maximal Irredundant Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathGraph.html">Path Graph</a>

%H <a href="/index/Rec#order_28">Index entries for linear recurrences with constant coefficients</a>, 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).

%F 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.

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

%e 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.

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

%Y Cf. A291055.

%K nonn

%O 1,3

%A _Andrew Howroyd_, Aug 23 2017