A327379 Number of labeled non-mating-type graphs with n vertices.

0, 1, 4, 32, 436, 11292, 545784, 49826744, 8647819328, 2876819527744, 1848998498567936, 2312324942899031040, 5659406410382924819712, 27230994319259100289485568, 258465217554621196991878652416, 4851552662579126853087143276476928

Offset

1,3

Comments

A mating-type graph has all different rows in its adjacency matrix.

Links

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

Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.

Gus Wiseman, The a(4) = 32 non-mating-type graphs.

Formula

a(n) = A006125(n) - A006024(n). - Andrew Howroyd, Sep 11 2019

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n], {2}]], !UnsameQ@@AdjacencyMatrix[Graph[Range[n], #]]&]], {n, 5}]

Prog

(PARI) a(n) = {2^binomial(n, 2) - sum(k=0, n, stirling(n, k, 1)*2^binomial(k, 2))} \\ Andrew Howroyd, Sep 11 2019

Crossrefs

The unlabeled version is A141580.

Cf. A006024, A006125, A028242, A059167, A245797, A327369, A327370.

Sequence in context: A088991 A009668 A005121 * A214379 A192500 A192486

Adjacent sequences: A327376 A327377 A327378 * A327380 A327381 A327382

Keyword

nonn

Author

Gus Wiseman, Sep 05 2019

Extensions

Terms a(7) and beyond from Andrew Howroyd, Sep 11 2019

Status

approved