A236550 The number of maximal independent sets in L(J_n), the line graph of the flower snark graph J_n.

2, 32, 140, 536, 2957, 14336, 70093, 348872, 1715054, 8450987, 41686977, 205360652, 1012222733, 4988885171, 24586626155, 121177096088, 597218222596, 2943376144478, 14506420142318, 71494667792051, 352360599502366, 1736605136729759, 8558836520137456, 42182122105754084

Offset

1,1

Comments

a(n) satisfies a complicated linear recurrence, but the values given were generated using BDDs.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100

Eric Weisstein's World of Mathematics, Flower Snark.

Eric Weisstein's World of Mathematics, Maximal Independent Edge Set.

Wikipedia, Binary decision diagram

Wikipedia, Flower snark

Wikipedia, Line graph

Wikipedia, Maximal independent set

Index entries for linear recurrences with constant coefficients, signature (2,14,16,-56,-95,110,301,-17,-206,-123,185,182,6,-180,-52,56,8).

Formula

Empirical g.f.: x*(2 + 28*x + 48*x^2 - 224*x^3 - 475*x^4 + 660*x^5 + 2107*x^6 - 136*x^7 - 1854*x^8 - 1230*x^9 + 2035*x^10 + 2184*x^11 + 78*x^12 - 2520*x^13 - 780*x^14 + 896*x^15 + 136*x^16) / ((1 + x - 2*x^2 - x^3 + 4*x^4 - 2*x^5)*(1 - x - 2*x^2 + x^3 + 4*x^4 + 2*x^5)*(1 - 2*x - 9*x^2 - 26*x^3 - 3*x^4 - 7*x^5 + 14*x^6 + 2*x^7)). - Colin Barker, May 17 2017

a(n) = 2*a(n-1)+14*a(n-2)+16*a(n-3)-56*a(n-4)-95*a(n-5)+110*a(n-6)+301*a(n-7)-17*a(n-8)-206*a(n-9)-123*a(n-10)+185*a(n-11)+182*a(n-12)+6*a(n-13)-180*a(n-14)-52*a(n-15)+56*a(n-16)+8*a(n-17). - Eric W. Weisstein, Jul 11 2024

Mathematica

LinearRecurrence[{2, 14, 16, -56, -95, 110, 301, -17, -206, -123, 185, 182, 6, -180, -52, 56, 8}, {2, 32, 140, 536, 2957, 14336, 70093, 348872, 1715054, 8450987, 41686977, 205360652, 1012222733, 4988885171, 24586626155, 121177096088, 597218222596}, 20] (* Eric W. Weisstein, Jul 11 2024 *)
CoefficientList[Series[(2 + 28 x + 48 x^2 - 224 x^3 - 475 x^4 + 660 x^5 + 2107 x^6 - 136 x^7 - 1854 x^8 - 1230 x^9 + 2035 x^10 + 2184 x^11 + 78 x^12 - 2520 x^13 - 780 x^14 + 896 x^15 + 136 x^16)/((1 + x - 2 x^2 - x^3 + 4 x^4 - 2 x^5) (1 - x - 2 x^2 + x^3 + 4 x^4 + 2 x^5) (1 - 2 x - 9 x^2 - 26 x^3 - 3 x^4 - 7 x^5 + 14 x^6 + 2 x^7)), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 11 2024 *)

Crossrefs

A236549 enumerates _all_ independent sets and gives further explanation.

Sequence in context: A112850 A123105 A123287 * A012642 A244730 A169833

Adjacent sequences: A236547 A236548 A236549 * A236551 A236552 A236553

Keyword

nonn

Author

Don Knuth, Jan 28 2014

Extensions

a(14)-a(24) from Andrew Howroyd, May 17 2017

Status

approved