login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A302750 Number of maximum matchings in the n-path complement graph. 1
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 (list; graph; refs; listen; history; text; internal format)
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: A283980 A288211 A038259 * 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 13 14:11 EDT 2021. Contains 342936 sequences. (Running on oeis4.)