

A141384


Trace of the nth power of a certain 8X8 adjacency matrix.


2



8, 8, 32, 158, 828, 4408, 23564, 126106, 675076, 3614144, 19349432, 103593806, 554625900, 2969386480, 15897666068, 85113810058, 455687062276, 2439682811480, 13061709929936, 69930511268510, 374397872321628
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

a(n) is the trace of the nth power of the adjacency matrix of order 8 whose rows are (up to simultaneous permutations of the rows and columns): 10111010 01111001 01111001 10111010 00111000 11111111 11111111 11111111.
For n>2, this is also the number of ways to mark one edge at every vertex of a regular ngonal prism so that no edge is marked at both extremities.
Remarkably, for n>1, a(n)=A141221(n)+2.
The fourthorder linear recurrence established by Max Alekseyev for A141221, based on the minimal polynomial of the above (singular) matrix, namely x(x1)(x^37x^2+9x1) = x^58*x^4+16*x^310*x^2+x. Since its degree is 5, the corresponding recurrence holds for corresponding elements of the successive powers (or sums thereof, including matrix traces) only for n>=5. The recurrence would be valid down to n=4 if we had a(0)=4, which is not the case.


LINKS

Table of n, a(n) for n=0..20.
Max A. Alekseyev, GĂ©rard P. Michon, Making Walks Count: From Silent Circles to Hamiltonian Cycles, arXiv:1602.01396 [math.CO], 2016.
G. P. Michon, A screaming game for shortsighted people.
G. P. Michon, Silent circles, enumerated by Max Alekseyev.
G. P. Michon, Brocoum's Screaming Circles.
Index entries for linear recurrences with constant coefficients, signature (8,16,10,1).


FORMULA

For n>=5, a(n) = 8*a(n1)16*a(n2)+10*a(n3)a(n4).
For positive values of n: a(n) = (5.3538557854308)^n + (1.5235479602692)^n + 1 + (0.1225962542999)^n. The dominant term in the above is the nth power of (7+2*sqrt(22)*cos(atan(sqrt(5319)/73)/3))/3.
G.f.: 2*(428*x+48*x^225*x^3+2*x^4)/((1x)*(17*x+9*x^2x^3)). [Colin Barker, Jan 20 2012]


EXAMPLE

a(0) = 8 because the trace of the order8 identity matrix is 8.
a(1) = 8 because all diagonal elements of the adjacency matrix are 1 (there's a loop at each vertex).


CROSSREFS

Cf. A141221.
Sequence in context: A122858 A143336 A053596 * A183400 A111218 A188275
Adjacent sequences: A141381 A141382 A141383 * A141385 A141386 A141387


KEYWORD

easy,nonn


AUTHOR

Gerard P. Michon, Jun 29 2008


EXTENSIONS

Edited by Max Alekseyev, Aug 03 2015


STATUS

approved



