login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A236549 The number of independent sets in L(J_n), the line graph of the flower snark graph J_n. 2
8, 126, 1052, 11170, 112828, 1159416, 11869768, 121668290, 1246778828, 12777339246, 130942887644, 1341919081864, 13752130924072, 140933387857374, 1444301049348172, 14801358544973954, 151685974693256396, 1554494806744974072, 15930636349271455016 (list; graph; refs; listen; history; text; internal format)
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 * A262732 A220728 A029472

Adjacent sequences:  A236546 A236547 A236548 * A236550 A236551 A236552

KEYWORD

nonn,easy

AUTHOR

Don Knuth, Jan 28 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 21 18:19 EST 2022. Contains 350479 sequences. (Running on oeis4.)