login
a(n) = (-1)^(n+1) * (3^n+1)/2.
0

%I #12 Feb 13 2021 14:41:16

%S -1,2,-5,14,-41,122,-365,1094,-3281,9842,-29525,88574,-265721,797162,

%T -2391485,7174454,-21523361,64570082,-193710245,581130734,-1743392201,

%U 5230176602,-15690529805,47071589414,-141214768241,423644304722,-1270932914165,3812798742494,-11438396227481,34315188682442

%N a(n) = (-1)^(n+1) * (3^n+1)/2.

%C Shown by Tutte (he erroneously gave the negative of this sequence) to be the value of the function g(X_n), where X_n is the graph with one vertex and n loops, and g() is the extension to all graphs of the function f(G) defined on trivalent graphs by f(G) =(-1)^n.Q(G), where 2n is the number of vertices of G, and Q(G) is the number of spanning subgraphs of G such that every vertex of G is incident with 2 edges, and obeying the recursions discussed by Tutte in the article.

%C This sequence is given in balanced ternary representation as (-1), 1(-1), (-1)11, 1(-1)(-1)(-1), (-1)1111, 1(-1)(-1)(-1)(-1)(-1), etc.

%D W. T. Tutte, Some polynomials associated with graphs, Combinatorics, Proceedings of the British Combinatorial Conference. Vol. 13. Cambridge Univ. Press London, 1973.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (-4,-3).

%F a(n) = -4*a(n-1) - 3*a(n-2) for n > 1.

%F G.f.: -(1 + 2*x)/(1 + 4*x + 3*x^2). - _Stefano Spezia_, Feb 13 2021

%o (Python)

%o def a(n):

%o return (-1)**(n+1) * (3 ** n + 1) // 2

%Y Absolute values give A007501.

%Y Cf. A076040.

%K sign,easy

%O 0,2

%A _Jack W Grahl_, Feb 12 2021