A297474 Number of maximal matchings in the n-cocktail party graph.

1, 2, 14, 92, 844, 9304, 121288, 1822736, 31030928, 590248736, 12406395616, 285558273472, 7143371664064, 192972180052352, 5598713198048384, 173627942889668864, 5731684010612723968, 200669613102747214336, 7426773564495661485568, 289713958515451427511296

Offset

1,2

Comments

A maximal matching in the n-cocktail party graph is either a perfect matching or a matching with a single unmatched pair. - Andrew Howroyd, Dec 30 2017

Links

Andrew Howroyd, Table of n, a(n) for n = 1..500

Eric Weisstein's World of Mathematics, Cocktail Party Graph.

Eric Weisstein's World of Mathematics, Matching.

Eric Weisstein's World of Mathematics, Maximal Independent Edge Set.

Formula

a(n) = A053871(n) + n*A053871(n-1). - Andrew Howroyd, Dec 30 2017

Mathematica

Table[(-1)^(n + 1) (n HypergeometricPFQ[{1/2, 1 - n}, {}, 2] - HypergeometricPFQ[{1/2, -n}, {}, 2]), {n, 20}]
Table[-I (-1)^n (n HypergeometricU[1/2, n + 1/2, -1/2] - HypergeometricU[1/2, n + 3/2, -1/2])/Sqrt[2], {n, 20}]

Prog

(PARI) \\ here b(n) is A053871.
b(n)={if(n<1, n==0, sum(k=0, n, (-1)^(n-k)*binomial(n, k)*(2*k)!/(2^k*k!)))}
a(n)=b(n) + n*b(n-1); \\ Andrew Howroyd, Dec 30 2017

Crossrefs

Cf. A053871, A293073.

Sequence in context: A351857 A341395 A072148 * A270063 A033169 A090410

Adjacent sequences: A297471 A297472 A297473 * A297475 A297476 A297477

Keyword

nonn

Author

Eric W. Weisstein, Dec 30 2017

Extensions

a(9)-a(20) from Andrew Howroyd, Dec 30 2017

Status

approved