A141384 Trace of the n-th power of a certain 8X8 adjacency matrix.

8, 8, 32, 158, 828, 4408, 23564, 126106, 675076, 3614144, 19349432, 103593806, 554625900, 2969386480, 15897666068, 85113810058, 455687062276, 2439682811480, 13061709929936, 69930511268510, 374397872321628

Offset

0,1

Comments

a(n) is the trace of the n-th 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 n-gonal prism so that no edge is marked at both extremities.

Remarkably, for n>1, a(n)=A141221(n)+2.

The fourth-order linear recurrence established by Max Alekseyev for A141221, based on the minimal polynomial of the above (singular) matrix, namely x(x-1)(x^3-7x^2+9x-1) = x^5-8*x^4+16*x^3-10*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 short-sighted 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(n-1)-16*a(n-2)+10*a(n-3)-a(n-4).

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 n-th power of (7+2*sqrt(22)*cos(atan(sqrt(5319)/73)/3))/3.

G.f.: 2*(4-28*x+48*x^2-25*x^3+2*x^4)/((1-x)*(1-7*x+9*x^2-x^3)). [Colin Barker, Jan 20 2012]

Example

a(0) = 8 because the trace of the order-8 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: A143336 A328529 A053596 * A183400 A111218 A339340

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