|
%I M3650 #48 Feb 20 2023 22:08:38
%S 1,1,1,4,32,588,21476,1551368,218608712,60071657408,32307552561088,
%T 34179798520396032,71474651351939175424,296572048493274368856832,
%U 2448649084251501449508762880,40306353989748719650902623919616
%N Number of labeled mating graphs with n nodes. Also called point-determining graphs.
%C 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
%C Also number of (n-1)-node labeled mating graphs allowing loops and without isolated nodes. - _Vladeta Jovovic_, Mar 08 2008
%D R. C. Read, The Enumeration of Mating-Type Graphs. Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Andrew Howroyd, <a href="/A006024/b006024.txt">Table of n, a(n) for n = 0..50</a>
%H I. M. Gessel and J. Li, <a href="http://arXiv.org/abs/0705.0042">Enumeration of Point-Determining Graphs</a>, arXiv:0705.0042 [math.CO], 2007-2009.
%H I. M. Gessel and J. Li, <a href="https://doi.org/10.1016/j.jcta.2010.03.009">Enumeration of point-determining graphs</a>, J. Combinatorial Theory Ser. A 118 (2011), 591-612.
%H R. C. Read, <a href="/A006023/a006023.pdf">The Enumeration of Mating-Type Graphs</a>, Dept. Combinatorics and Optimization, Univ. Waterloo, Oct 1989. (Annotated scanned copy)
%H D. Sumner, <a href="https://doi.org/10.1016/0012-365X(73)90109-X">Point determination in graphs</a>, Discrete Mathematics 5 (1973), 179-187.
%F a(n) = Sum_{k=0..n} Stirling1(n, k)*2^binomial(k, 2). - Ronald C. Read and _Vladeta Jovovic_, Feb 10 2003
%F E.g.f.: Sum_{n>=0} 2^(n(n-1)/2)*log(1+x)^n/n!. - _Paul D. Hanna_, May 20 2009
%e 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.
%t a[n_] := Sum[StirlingS1[n, k] 2^Binomial[k, 2], {k, 0, n}];
%t Array[a, 15] (* _Jean-François Alcover_, Jul 25 2018 *)
%o (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
%Y Cf. A006025.
%Y Cf. bi-point-determining graphs: labeled A129583, unlabeled A129584; connected bi-point-determining graphs: labeled A129585, unlabeled A129586; phylogenetic trees: labeled A000311, unlabeled A000669.
%Y Cf. A007833, A079306 (connected)
%K nonn
%O 0,4
%A _Simon Plouffe_
%E More terms from Ronald C. Read and _Vladeta Jovovic_, Feb 10 2003
%E a(0)=1 prepended by _Andrew Howroyd_, Sep 09 2018
|
