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

Wikipedia, Binary decision diagram

Wikipedia, Flower snark

Wikipedia, Line graph

Wikipedia, Maximal independent set

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

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