%I #49 Jun 19 2022 17:20:02
%S 3,6,13,31,78,201,523,1366,3573,9351,24478,64081,167763,439206,
%T 1149853,3010351,7881198,20633241,54018523,141422326,370248453,
%U 969323031,2537720638,6643838881,17393796003,45537549126,119218851373,312119004991,817138163598
%N a(n) is the number of perfect matchings of an edge-labeled 2 X (2n+1) Mobius grid graph.
%C This is a specialization for m=2 of a general formula for the number of perfect matchings of an edge-labeled m X (2n+1) Mobius grid graph.
%H Clark Kimberling, <a href="/A162483/b162483.txt">Table of n, a(n) for n = 0..1000</a>
%H G. Tesler, <a href="http://dx.doi.org/10.1006/jctb.1999.1941">Matchings in graphs on non-orientable surfaces</a>, Journal of Combinatorial Theory B, 78(2000), 198-231.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4,1).
%F a(n) = Real((1-I) * ((L(2*n+1) - F(2*n+1))/2 + F(2*n+2) + 2*I)).
%F From _R. J. Mathar_, Aug 08 2009: (Start)
%F a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3).
%F G.f.: (3-6*x+x^2)/((1-x)*(x^2-3*x+1)). (End)
%F a(n+1)-a(n) = A005248(n+1). - _R. J. Mathar_, Dec 18 2010
%F a(n) = A000032(2n+1)+2. - _Clark Kimberling_, Oct 26 2012
%F a(n) = 2^(-1-n)*(2^(2+n)-(3-sqrt(5))^n*(-1+sqrt(5))+(1+sqrt(5))*(3+sqrt(5))^n). - _Colin Barker_, Nov 03 2016
%F a(n) = 2 + L(2*n+1), A256233(n) = -a(-n-1) for all n in Z. - _Michael Somos_, Nov 03 2016
%e G.f. = 3 + 6*x + 13*x^2 + 31*x^3 + 78*x^4 + 201*x^5 + 523*x^6 + 1366*x^7 + ...
%e a(0) = 3 because this is the number of perfect matchings of a 2 X 1 Mobius grid graph (one for each of the three multiple edges).
%t Table[Re[(1 - I) (2*I + Fibonacci[2 + 2*n] + 1/2 (-Fibonacci[1 + 2*n] + LucasL[1 + 2*n]))], {n, 0, 30}]
%t Table[LucasL[2*n + 1] + 2, {n, 0, 30}] (* _Clark Kimberling_, Oct 26 2012 *)
%t LinearRecurrence[{4, -4, 1}, {3, 6, 13}, 30] (* or *) CoefficientList[Series[(-3 + 6 x - x^2)/(-1 + 4 x - 4 x^2 + x^3), {x, 0, 30}], x] (* _Stefano Spezia_, Sep 23 2018 *)
%o (PARI) {a(n) = 2 + fibonacci(2*n) + fibonacci(2*n+2)}; /* _Michael Somos_, Nov 03 2016 */
%o (Magma) m:=25; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((3-6*x+x^2)/((1-x)*(x^2-3*x+1)))); // _G. C. Greubel_, Sep 22 2018
%Y Cf. A020878, A256233.
%K nonn,easy
%O 0,1
%A _Sarah-Marie Belcastro_, Jul 04 2009