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
Keywords
Links
- Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
- Eric Weisstein's World of Mathematics, Path Complement Graph
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
Comments