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!)
A302749 Number of maximal matchings in the n-path complement graph. 1
1, 1, 1, 2, 6, 11, 41, 77, 365, 694, 3984, 7639, 51499, 99343, 769159, 1490474, 13031514, 25341713, 246925295, 481540391, 5173842311, 10113069526, 118776068256, 232612909297, 2964697094281, 5815557347521, 79937923931761, 157024987610282, 2315462770608870, 4553838477539219 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

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(2n+1) = A302750(2n+1), a(2n) = Sum_{k=0..n} (1-k)*(-1)^k*binomial(2*n-k,k)*(2*(n-k)-1)!!. - Andrew Howroyd, Apr 15 2018

MATHEMATICA

Table[If[Mod[n, 2] == 0, (n - 1)!! (Hypergeometric1F1[1 - n/2, 1 - n, -2] + Hypergeometric1F1[-n/2, -n, -2]), (2^-Floor[n/2] n! Hypergeometric1F1[-Floor[n/2], -n, -2])/Floor[n/2]!], {n, 30}]

PROG

(PARI)

b(n)=(2*n)!/(2^n*n!);

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

CROSSREFS

Cf. A170941 (matchings), A302750 (maximum matchings).

Sequence in context: A318199 A242791 A156065 * A130274 A208893 A057294

Adjacent sequences:  A302746 A302747 A302748 * A302750 A302751 A302752

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 11 10:52 EDT 2021. Contains 342886 sequences. (Running on oeis4.)