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,1

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).

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)

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 *)

Prog

(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
(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

Crossrefs

Sequence in context: A091606 A027037 A276428 * A158278 A187505 A027100

Adjacent sequences: A020875 A020876 A020877 * A020879 A020880 A020881

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved