|
%I #18 Feb 04 2016 03:06:01
%S 8,8,32,158,828,4408,23564,126106,675076,3614144,19349432,103593806,
%T 554625900,2969386480,15897666068,85113810058,455687062276,
%U 2439682811480,13061709929936,69930511268510,374397872321628
%N Trace of the n-th power of a certain 8X8 adjacency matrix.
%C 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.
%C 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.
%C Remarkably, for n>1, a(n)=A141221(n)+2.
%C 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.
%H Max A. Alekseyev, Gérard P. Michon, <a href="http://arxiv.org/abs/1602.01396">Making Walks Count: From Silent Circles to Hamiltonian Cycles</a>, arXiv:1602.01396 [math.CO], 2016.
%H G. P. Michon, <a href="http://www.numericana.com/answer/graphs.htm#prisms">A screaming game for short-sighted people</a>.
%H G. P. Michon, <a href="http://www.numericana.com/answer/graphs.htm#alekseyev">Silent circles</a>, enumerated by Max Alekseyev.
%H G. P. Michon, <a href="http://www.numericana.com/answer/counting.htm#scream">Brocoum's Screaming Circles</a>.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (8,-16,10,-1).
%F For n>=5, a(n) = 8*a(n-1)-16*a(n-2)+10*a(n-3)-a(n-4).
%F 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.
%F 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]
%e a(0) = 8 because the trace of the order-8 identity matrix is 8.
%e a(1) = 8 because all diagonal elements of the adjacency matrix are 1 (there's a loop at each vertex).
%Y Cf. A141221.
%K easy,nonn
%O 0,1
%A _Gerard P. Michon_, Jun 29 2008
%E Edited by _Max Alekseyev_, Aug 03 2015
| 