OFFSET
1,1
COMMENTS
Original name: the number of independent sets in L(J_n), the line graph of the flower snark graph J_n.
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).
Sequence extended to a(1) using the formula/recurrence. - Eric W. Weisstein, Sep 02 2025
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)
Eric Weisstein's World of Mathematics, Flower Graph.
Eric Weisstein's World of Mathematics, Independent Edge Set.
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
a(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). - Eric W. Weisstein, Sep 02 2025
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 *)
Table[(1 + (-1)^n) LucasL[n, 2] + RootSum[1 + 20 # - 25 #^2 - 8 #^3 + #^4 &, #^n &], {n, 20}] (* Eric W. Weisstein, Sep 02 2025 *)
CoefficientList[Series[-2 (-4 - 31 x + 102 x^2 + 304 x^3 - 320 x^4 - 93 x^5 + 70 x^6 + 4 x^7)/((-1 - 2 x + x^2) (-1 + 2 x + x^2) (1 - 8 x - 25 x^2 + 20 x^3 + x^4)), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 02 2025 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Don Knuth, Jan 28 2014
EXTENSIONS
Simpler name from Eric W. Weisstein, Sep 02 2025
STATUS
approved