A302750 Number of maximum matchings in the n-path complement graph.

1, 1, 1, 1, 6, 5, 41, 36, 365, 329, 3984, 3655, 51499, 47844, 769159, 721315, 13031514, 12310199, 246925295, 234615096, 5173842311, 4939227215, 118776068256, 113836841041, 2964697094281, 2850860253240, 79937923931761, 77087063678521, 2315462770608870, 2238375706930349

Offset: 1

Author

Eric W. Weisstein, Apr 12 2018

Keywords

• nonn

Comments

Except for n=2, the number of edges in a maximum matching is floor(n/2). - Andrew Howroyd, Apr 15 2018

Links

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

Crossrefs

Cf. A170941 (matchings), A302749 (maximal matchings).

Programs

Mathematica

Join[{1, 1}, Table[(2^-Floor[n/2] n! Hypergeometric1F1[-Floor[n/2], -n, -2])/Floor[n/2]!, {n, 3, 30}]]

PARI

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

Formula

a(n) = Sum_{k=0..floor(n/2)} (-1)^k*binomial(n-k,k)*(2*(ceiling(n/2)-k)-1)!! for n > 2. - Andrew Howroyd, Apr 15 2018

a(n) = 2^-floor(n/2)*n!*hypergeometric1f1(-floor(n/2), -n, -2)/(floor(n/2))! for n > 2. - Eric W. Weisstein, Apr 16 2018

Extensions

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