A162483 a(n) is the number of perfect matchings of an edge-labeled 2 X (2n+1) Mobius grid graph.

3, 6, 13, 31, 78, 201, 523, 1366, 3573, 9351, 24478, 64081, 167763, 439206, 1149853, 3010351, 7881198, 20633241, 54018523, 141422326, 370248453, 969323031, 2537720638, 6643838881, 17393796003, 45537549126, 119218851373, 312119004991, 817138163598

Offset

0,1

Comments

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.

Links

Clark Kimberling, Table of n, a(n) for n = 0..1000

G. Tesler, Matchings in graphs on non-orientable surfaces, Journal of Combinatorial Theory B, 78(2000), 198-231.

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

Formula

a(n) = Real((1-I) * ((L(2*n+1) - F(2*n+1))/2 + F(2*n+2) + 2*I)).

From R. J. Mathar, Aug 08 2009: (Start)

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

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

a(n+1)-a(n) = A005248(n+1). - R. J. Mathar, Dec 18 2010

a(n) = A000032(2n+1)+2. - Clark Kimberling, Oct 26 2012

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

a(n) = 2 + L(2*n+1), A256233(n) = -a(-n-1) for all n in Z. - Michael Somos, Nov 03 2016

Example

G.f. = 3 + 6*x + 13*x^2 + 31*x^3 + 78*x^4 + 201*x^5 + 523*x^6 + 1366*x^7 + ...
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).

Mathematica

Table[Re[(1 - I) (2*I + Fibonacci[2 + 2*n] + 1/2 (-Fibonacci[1 + 2*n] + LucasL[1 + 2*n]))], {n, 0, 30}]
Table[LucasL[2*n + 1] + 2, {n, 0, 30}] (* Clark Kimberling, Oct 26 2012 *)
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 *)

Prog

(PARI) {a(n) = 2 + fibonacci(2*n) + fibonacci(2*n+2)}; /* Michael Somos, Nov 03 2016 */
(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

Crossrefs

Cf. A020878, A256233.

Sequence in context: A293911 A018014 A358937 * A187780 A273974 A179928

Adjacent sequences: A162480 A162481 A162482 * A162484 A162485 A162486

Keyword

nonn,easy

Author

Sarah-Marie Belcastro, Jul 04 2009

Status

approved