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

Comments

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

Links

Andrew Howroyd, Table of n, a(n) for n = 1..500

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

Eric Weisstein's World of Mathematics, Path Complement Graph.

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

Mathematica

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

Prog

(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

Crossrefs

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

Sequence in context: A038259 A358590 A393349 * A268000 A223529 A189422

Adjacent sequences: A302747 A302748 A302749 * A302751 A302752 A302753

Keyword

nonn

Author

Eric W. Weisstein, Apr 12 2018

Extensions

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

Status

approved