

A006024


Number of labeled mating graphs with n nodes. Also called pointdetermining graphs.
(Formerly M3650)


28



1, 1, 1, 4, 32, 588, 21476, 1551368, 218608712, 60071657408, 32307552561088, 34179798520396032, 71474651351939175424, 296572048493274368856832, 2448649084251501449508762880, 40306353989748719650902623919616
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

A mating graph is one in which no two vertices have identical adjacencies with the other vertices.  Ronald C. Read and Vladeta Jovovic, Feb 10 2003
Also number of (n1)node labeled mating graphs allowing loops and without isolated nodes.  Vladeta Jovovic, Mar 08 2008


REFERENCES

R. C. Read, The Enumeration of MatingType Graphs. Report CORR 8938, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS



FORMULA

a(n) = Sum_{k=0..n} Stirling1(n, k)*2^binomial(k, 2).  Ronald C. Read and Vladeta Jovovic, Feb 10 2003
E.g.f.: Sum_{n>=0} 2^(n(n1)/2)*log(1+x)^n/n!.  Paul D. Hanna, May 20 2009


EXAMPLE

Consider the square (cycle of length 4) on vertices 1, 2, 3 and 4 in that order. Join a fifth vertex (5) to vertices 1, 3 and 4. The resulting graph is not a mating graph since vertices 1 and 3 both have the set {2, 4, 5} as neighbors. If we delete the edge (1,5) then the resulting graph is a mating graph: the neighborhood sets for vertices 1, 2, 3, 4 and 5 are respectively {2,4}, {1,3}, {2,4,5}, {1,3,5} and {3,4}  all different.


MATHEMATICA

a[n_] := Sum[StirlingS1[n, k] 2^Binomial[k, 2], {k, 0, n}];


PROG

(PARI) a(n)=n!*polcoeff(sum(k=0, n, 2^(k*(k1)/2)*log(1+x+x*O(x^n))^k/k!), n) \\ Paul D. Hanna, May 20 2009


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



