|
|
A006024
|
|
Number of labeled mating graphs with n nodes. Also called point-determining 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 (n-1)-node labeled mating graphs allowing loops and without isolated nodes. - Vladeta Jovovic, Mar 08 2008
|
|
REFERENCES
|
R. C. Read, The Enumeration of Mating-Type Graphs. Report CORR 89-38, 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(n-1)/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*(k-1)/2)*log(1+x+x*O(x^n))^k/k!), n) \\ Paul D. Hanna, May 20 2009
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|