A099176 a(n) = 2*a(n-1) + 4*a(n-2) - 4*a(n-3) - 4*a(n-4).

1, 1, 4, 8, 24, 60, 168, 448, 1232, 3344, 9152, 24960, 68224, 186304, 509056, 1390592, 3799296, 10379520, 28357632, 77473792, 211662848, 578272256, 1579870208, 4316282880, 11792306176, 32217174016, 88018960384, 240472260608, 656982441984, 1794909388800

Offset: 0

Author

Paul Barry, Oct 02 2004

Keywords

• easy
• nonn

Comments

Form the 6 node graph with matrix A=[1,1,1,1,0,0; 1,1,0,0,1,1; 1,0,0,0,0,0; 1,0,0,0,0,0; 0,1,0,0,0,0; 0,1,0,0,0,0]. Then a(n) counts closed walks of length n at either of the degree 5 vertices.

Links

• Index entries for linear recurrences with constant coefficients, signature (2,4,-4,-4).

Crossrefs

Cf. A002605, A099177.

Formula

G.f.: (1+x)*(1-2*x)/((1-2x^2)(1-2x-2x^2)).

a(n) = (3+sqrt(3))(1+sqrt(3))^n/12+(3-sqrt(3))(1-sqrt(3))^n/12+2^((n-4)/2)(1+(-1)^n).

a(n) = A002605(n)/2+2^((n-4)/2)(1+(-1)^n).

E.g.f.: (3*cosh(sqrt(2)*x) + exp(x)*(3*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x)))/6. - Stefano Spezia, Jun 07 2025