A287497 Number of maximal matchings in the n-web graph.

1, 9, 22, 53, 166, 432, 1212, 3341, 9175, 25364, 69829, 192560, 530830, 1463170, 4033687, 11119101, 30651528, 84495213, 232922084, 642082488, 1769987094, 4879211973, 13450215173, 37077354584, 102208799091, 281752521488, 776689338352, 2141050324382

Offset

1,2

Comments

Extended to a(1)-a(2) using the formula.

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Eric Weisstein's World of Mathematics, Matching

Eric Weisstein's World of Mathematics, Maximal Independent Edge Set

Eric Weisstein's World of Mathematics, Web Graph

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

Formula

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

G.f.: (x*(-1-8*x-9*x^2+8*x^3-6*x^5))/(-1+x+4*x^2+3*x^3-2*x^4+x^6).

Mathematica

LinearRecurrence[{1, 4, 3, -2, 0, 1}, {1, 9, 22, 53, 166, 432}, 20]
Rest @ CoefficientList[Series[(x (-1 - 8 x - 9 x^2 + 8 x^3 - 6 x^5))/(-1 + x + 4 x^2 + 3 x^3 - 2 x^4 + x^6), {x, 0, 20}], x]
Table[RootSum[-1 + 2 #^2 - 3 #^3 - 4 #^4 - #^5 + #^6 &, #^n &], {n, 20}]
RootSum[-1 + 2 #^2 - 3 #^3 - 4 #^4 - #^5 + #^6 &, #^Range[20] &] (* Eric W. Weisstein, Dec 30 2017 *)

Prog

(Magma) I:=[1, 9, 22, 53, 166, 432]; [n le 6 select I[n] else Self(n-1)+4*Self(n-2)+3*Self(n-3)-2*Self(n-4)+Self(n-6): n in [1..30]]; // Vincenzo Librandi, Sep 03 2017

Crossrefs

Sequence in context: A250730 A251285 A197498 * A232024 A327150 A264651

Adjacent sequences: A287494 A287495 A287496 * A287498 A287499 A287500

Keyword

nonn

Author

Eric W. Weisstein, May 25 2017

Status

approved