A302749 -id:A302749 - cp's OEIS frontend

A351588 Number of minimal edge covers in the n-path complement graph.

0, 0, 0, 1, 7, 34, 174, 1079, 7055, 48796, 366180, 2928387, 24726556, 220572828, 2071469527, 20393131971, 209934610376, 2254860549906, 25210893460938, 292826210789807, 3527105947667676, 43985152403166462, 567048383126842506, 7546842245268945427, 103560659196050026908

Offset: 1

Eric W. Weisstein, Feb 14 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Minimal Edge Cover.
Eric Weisstein's World of Mathematics, Path Complement Graph.

Cf. A302719, A302749, A351587.

a(n)={sum(i=0, n\2, sum(j=0, (n-2*i)\3, my(r=n-2*i-3*j, g=exp(x + O(x*x^r))); (-1)^i*binomial(i+j,i)*binomial(n-i-2*j,i+j)*(r)!*polcoef((2*g-1)^i*exp(j*x -x - x^2/2 + x*g), r)))} \\ Andrew Howroyd, Jun 14 2025

a(n) = Sum_{i=0..floor(n/2)} Sum{j=0..floor((n-2*i)/3)} (-1)^i * binomial(i+j,i) * binomial(n-i-2*j,i+j) * (n-2*i-3*j)! * [x^(n-2*i-3*j)] ((2*exp(x)-1)^i * exp(x)^j * exp(-x - x^2/2 + x*exp(x))). - Andrew Howroyd, Jun 14 2025

a(9)-a(12) from Andrew Howroyd, Feb 21 2022

a(13) onwards from Andrew Howroyd, Jun 14 2025

A302750 Number of maximum matchings in the n-path complement graph.

Original entry on oeis.org

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

Eric W. Weisstein, Apr 12 2018

nonn

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

Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
Eric Weisstein's World of Mathematics, Path Complement Graph

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

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

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

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

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

cp's OEIS Frontend

A351588 Number of minimal edge covers in the n-path complement graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions