A020878 Number of maximum matchings in the n-Moebius ladder M_n.

2, 3, 3, 6, 7, 13, 18, 31, 47, 78, 123, 201, 322, 523, 843, 1366, 2207, 3573, 5778, 9351, 15127, 24478, 39603, 64081, 103682, 167763, 271443, 439206, 710647, 1149853, 1860498, 3010351, 4870847, 7881198, 12752043, 20633241, 33385282, 54018523, 87403803

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

References

• J. P. McSorley, Counting structures in the Moebius ladder, Discrete Math., 184 (1998), 137-164.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Eric Weisstein's World of Mathematics, Matching
• Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
• Eric Weisstein's World of Mathematics, Moebius Ladder
• Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-1).

Programs

Magma

I:=[2, 3, 3, 6]; [n le 4 select I[n] else Self(n-1)+2*Self(n-2)-Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Apr 20 2012

Mathematica

CoefficientList[Series[(2+x-4*x^2-x^3)/((1+x)*(1-x)*(1-x-x^2)),{x,0,40}],x] (* Vincenzo Librandi, Apr 20 2012 *)
Table[1 - (-1)^n + LucasL[n], {n, 20}] (* Eric W. Weisstein, Dec 31 2017 *)
LinearRecurrence[{1, 2, -1, -1}, {3, 3, 6, 7}, 20] (* Eric W. Weisstein, Dec 31 2017 *)

PARI

Vec((2 + x - 4*x^2 - x^3) / ((1 - x)*(1 + x)*(1 - x - x^2)) + O(x^50)) \\ Colin Barker, Jul 12 2017

Formula

If n mod 2 = 0 then L(n) else L(n)+2, where L() are the Lucas numbers.

a(n) = A001350(n) + 2.

G.f.: (2 + x - 4*x^2 - x^3) / ((1 - x)*(1 + x)*(1 - x - x^2)). - Colin Barker, Jan 23 2012

From Colin Barker, Jul 12 2017: (Start)

a(n) = ((1 - sqrt(5))/2)^n + ((1 + sqrt(5))/2)^n for n even.

a(n) = ((1 - sqrt(5))/2)^n + ((1 + sqrt(5))/2)^n + 2 for n odd.

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

(End)