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

8, 126, 1052, 11170, 112828, 1159416, 11869768, 121668290, 1246778828, 12777339246, 130942887644, 1341919081864, 13752130924072, 140933387857374, 1444301049348172, 14801358544973954, 151685974693256396, 1554494806744974072, 15930636349271455016

Offset

1,1

Comments

The graph L(J_n) has 6n vertices a_j,b_j,c_j,d_j,e_j,f_j for j=0,...,n-1; the edges are a_jb_j, e_jc_j, f_jd_j, b_jc_j, c_jd_j, d_jb_j, a_ja_k, a_jb_k, e_jd_k, e_jf_k, f_jc_k, f_je_k, where k=j+1 (mod n).

References

The Art of Computer Programming, Volume 4B [in preparation], an exercise in Section 7.2.2.2.

Links

Giovanni Resta, Table of n, a(n) for n = 1..988 (terms < 10^1000)

Wikipedia, Flower snark

Wikipedia, Line graph

Index entries for linear recurrences with constant coefficients, signature (8,31,-68,-152,128,31,-20,-1)

Formula

a(n) is tr(A^n), where A is a 20 X 20 matrix relating independent sets of {a_j,...,f_j} to independent sets of {a_k,...,f_k}, k=j+1 (mod n).

The characteristic polynomial of A is x^12(x^2-2x-1)(x^2+2x-1)(x^4-8x^3-25x^2+20x+1); hence a(n) is asymptotically c r^n where r=10.248111658695...

G.f.: -2*x*(4*x^7 +70*x^6 -93*x^5 -320*x^4 +304*x^3 +102*x^2 -31*x -4) / ((x^2 -2*x -1)*(x^2 +2*x -1)*(x^4 +20*x^3 -25*x^2 -8*x +1)). - Alois P. Heinz, Jan 28 2014

Maple

a:= proc(n) option remember; `if`(n<9, [8, 126, 1052,
      11170, 112828, 1159416, 11869768, 121668290][n],
      8*a(n-1) +31*a(n-2) -68*a(n-3) -152*a(n-4)
      +128*a(n-5) +31*a(n-6) -20*a(n-7) -a(n-8))
    end:
seq(a(n), n=1..25);  # Alois P. Heinz, Jan 28 2014

Mathematica

a=2^5; b=2^4; c=2^3; d=2^2; e=2^1; f=2^0;
i={0, a, b, c, d, e, f, a+e, a+f, e+f, b+e, b+f, c+a, c+f, d+a, d+e, a+e+f, b+e+f, c+a+f, d+a+e};
t[x_, y_]:=Block[{m},
         m=If[BitAnd[x, a]!=0, a+b, 0]+
           If[BitAnd[x, e]!=0, d+f, 0]+
           If[BitAnd[x, f]!=0, c+e, 0];
         If[BitAnd[m, y]!=0, 0, 1]];
A=Array[t[i[[#1]], i[[#2]]] &, {20, 20}];
aa[n_]:=Tr[MatrixPower[A, n]]; Array[aa, 20]
LinearRecurrence[{8, 31, -68, -152, 128, 31, -20, -1}, {8, 126, 1052, 11170, 112828, 1159416, 11869768, 121668290}, 20] (* Harvey P. Dale, Oct 15 2016 *)

Crossrefs

Cf. A236550.

Sequence in context: A035130 A055762 A281714 * A360852 A262732 A220728

Adjacent sequences: A236546 A236547 A236548 * A236550 A236551 A236552

Keyword

nonn,easy

Author

Don Knuth, Jan 28 2014

Status

approved