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
KEYWORD
nonn,easy
AUTHOR
Don Knuth, Jan 28 2014
STATUS
approved