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

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(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: A288211 A038259 A358590 * 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