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

%I #9 Sep 11 2019 15:52:20

%S 0,1,4,32,436,11292,545784,49826744,8647819328,2876819527744,

%T 1848998498567936,2312324942899031040,5659406410382924819712,

%U 27230994319259100289485568,258465217554621196991878652416,4851552662579126853087143276476928

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

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

%H Andrew Howroyd, <a href="/A327379/b327379.txt">Table of n, a(n) for n = 1..50</a>

%H Ronald C. Read, <a href="https://oeis.org/A006023/a006023.pdf"> The enumeration of mating-type graphs</a>, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.

%H Gus Wiseman, <a href="/A327379/a327379.png">The a(4) = 32 non-mating-type graphs.</a>

%F a(n) = A006125(n) - A006024(n). - _Andrew Howroyd_, Sep 11 2019

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

%o (PARI) a(n) = {2^binomial(n,2) - sum(k=0, n, stirling(n, k, 1)*2^binomial(k,2))} \\ _Andrew Howroyd_, Sep 11 2019

%Y The unlabeled version is A141580.

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

%K nonn

%O 1,3

%A _Gus Wiseman_, Sep 05 2019

%E Terms a(7) and beyond from _Andrew Howroyd_, Sep 11 2019