|
%I #26 Jul 07 2018 15:47:49
%S 8,126,1052,11170,112828,1159416,11869768,121668290,1246778828,
%T 12777339246,130942887644,1341919081864,13752130924072,
%U 140933387857374,1444301049348172,14801358544973954,151685974693256396,1554494806744974072,15930636349271455016
%N The number of independent sets in L(J_n), the line graph of the flower snark graph J_n.
%C 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).
%D The Art of Computer Programming, Volume 4B [in preparation], an exercise in Section 7.2.2.2.
%H Giovanni Resta, <a href="/A236549/b236549.txt">Table of n, a(n) for n = 1..988</a> (terms < 10^1000)
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Flower_snark">Flower snark</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Line_graph">Line graph</a>
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (8,31,-68,-152,128,31,-20,-1)
%F 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).
%F 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...
%F 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
%p a:= proc(n) option remember; `if`(n<9, [8, 126, 1052,
%p 11170, 112828, 1159416, 11869768, 121668290][n],
%p 8*a(n-1) +31*a(n-2) -68*a(n-3) -152*a(n-4)
%p +128*a(n-5) +31*a(n-6) -20*a(n-7) -a(n-8))
%p end:
%p seq(a(n), n=1..25); # _Alois P. Heinz_, Jan 28 2014
%t a=2^5; b=2^4; c=2^3; d=2^2; e=2^1; f=2^0;
%t 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 t[x_,y_]:=Block[{m},
%t m=If[BitAnd[x,a]!=0,a+b,0]+
%t If[BitAnd[x,e]!=0,d+f,0]+
%t If[BitAnd[x,f]!=0,c+e,0];
%t If[BitAnd[m,y]!=0,0,1]];
%t A=Array[t[i[[#1]],i[[#2]]] &, {20,20}];
%t aa[n_]:=Tr[MatrixPower[A,n]]; Array[aa,20]
%t LinearRecurrence[{8,31,-68,-152,128,31,-20,-1},{8,126,1052,11170,112828,1159416,11869768,121668290},20] (* _Harvey P. Dale_, Oct 15 2016 *)
%Y Cf. A236550.
%K nonn,easy
%O 1,1
%A _Don Knuth_, Jan 28 2014
|
