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

Author

Eric W. Weisstein, Apr 12 2018

Keywords

• nonn

Links

• Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
• Eric Weisstein's World of Mathematics, Path Complement Graph

Crossrefs

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

Programs

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}]

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

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

Extensions

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