A302749 Number of maximal matchings in the n-path complement graph.

1, 1, 1, 2, 6, 11, 41, 77, 365, 694, 3984, 7639, 51499, 99343, 769159, 1490474, 13031514, 25341713, 246925295, 481540391, 5173842311, 10113069526, 118776068256, 232612909297, 2964697094281, 5815557347521, 79937923931761, 157024987610282, 2315462770608870, 4553838477539219

Offset

1,4

Links

Table of n, a(n) for n=1..30.

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

Eric Weisstein's World of Mathematics, Path Complement Graph

Formula

a(2n+1) = A302750(2n+1), a(2n) = Sum_{k=0..n} (1-k)*(-1)^k*binomial(2*n-k,k)*(2*(n-k)-1)!!. - Andrew Howroyd, Apr 15 2018

Mathematica

Table[If[Mod[n, 2] == 0, (n - 1)!! (Hypergeometric1F1[1 - n/2, 1 - n, -2] + Hypergeometric1F1[-n/2, -n, -2]), (2^-Floor[n/2] n! Hypergeometric1F1[-Floor[n/2], -n, -2])/Floor[n/2]!], {n, 30}]

Prog

(PARI)
b(n)=(2*n)!/(2^n*n!);
a(n)=sum(k=0, n\2, if(n%2, 1, (1-k))*(-1)^k*binomial(n-k, k)*b((n+1)\2-k)) \\ Andrew Howroyd, Apr 15 2018

Crossrefs

Cf. A170941 (matchings), A302750 (maximum matchings).

Sequence in context: A318199 A242791 A156065 * A130274 A352662 A368810

Adjacent sequences: A302746 A302747 A302748 * A302750 A302751 A302752

Keyword

nonn

Author

Eric W. Weisstein, Apr 12 2018

Extensions

a(17)-a(30) from Andrew Howroyd, Apr 15 2018

Status

approved