A006024
Number of labeled mating graphs with n nodes. Also called point-determining graphs.
Original entry on oeis.org
1, 1, 1, 4, 32, 588, 21476, 1551368, 218608712, 60071657408, 32307552561088, 34179798520396032, 71474651351939175424, 296572048493274368856832, 2448649084251501449508762880, 40306353989748719650902623919616
Offset: 0
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.
- 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).
- Andrew Howroyd, Table of n, a(n) for n = 0..50
- I. M. Gessel and J. Li, Enumeration of Point-Determining Graphs, arXiv:0705.0042 [math.CO], 2007-2009.
- I. M. Gessel and J. Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 591-612.
- R. C. Read, The Enumeration of Mating-Type Graphs, Dept. Combinatorics and Optimization, Univ. Waterloo, Oct 1989. (Annotated scanned copy)
- D. Sumner, Point determination in graphs, Discrete Mathematics 5 (1973), 179-187.
-
a[n_] := Sum[StirlingS1[n, k] 2^Binomial[k, 2], {k, 0, n}];
Array[a, 15] (* Jean-François Alcover, Jul 25 2018 *)
-
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
A079307
Number of n-node labeled mating digraphs whose complements are connected.
Original entry on oeis.org
1, 2, 47, 3537, 990504, 1052216730, 4368243719790, 71899754628285990, 4719127231162959826680, 1237680394434222243386835240, 1297992518900121521819851167607200
Offset: 1
A079306
Number of n-node labeled mating graphs whose complements are connected.
Original entry on oeis.org
1, 0, 3, 19, 462, 18268, 1410394, 206677954, 58152577504, 31715883698744, 33827568741818376, 71066571962356168856, 295645506683051855529248, 2444503529745123468127635920, 40269655263141217619540592737168
Offset: 1
A006023
Number of unlabeled mating digraphs with n nodes.
Original entry on oeis.org
1, 1, 2, 12, 183, 8884, 1495984, 872987584, 1787227218134, 13013640978954744, 341143259362180445672, 32519497484526664873838560, 11366387701006542223325518765872, 14668949294272099348849331250968826816
Offset: 0
- R. C. Read, The Enumeration of Mating-Type Graphs. Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, Oct 1989.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
-
permcount[v_] := Module[{m = 1, s = 0, t, i, k = 0}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Sum[v[[i]] - 1, {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, If[n == 0, Return[1]]; Sum[Do[ s += permcount[p]* 2^edges[p] * Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {p, IntegerPartitions[k]}], {k, 1, n}]; s];
a /@ Range[0, 20] (* Jean-François Alcover, Sep 22 2019, after Andrew Howroyd *)
-
\\ compare A000273.
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i]-1)}
a(n) = {if(n<1, n==0, my(s=0); sum(k=1, n, forpart(p=k, s+=permcount(p) * 2^edges(p) * polcoef(prod(i=1, #p, 1-x^p[i]), n-k)/k!)); s)} \\ Andrew Howroyd, Sep 09 2018
A160710
E.g.f.: Sum_{n>=0} 2^(n^2)*log(1+x)^n/n!.
Original entry on oeis.org
1, 2, 14, 468, 62628, 32916240, 68221619760, 561512669071200, 18431003537355665760, 2417187863502316739842560, 1267541812947815891035704645120, 2658386273978048637324643356687805440
Offset: 0
E.g.f.: A(x) = 1 + 2*x + 14*x^2/2! + 468*x^3/3! + 62628*x^4/4! +...
A(x) = 1 + 2*log(1+x) + 2^4*log(1+x)^2/2! + 2^9*log(1+x)^3/3! +...
-
Table[Sum[StirlingS1[n, k]*2^(k^2), {k, 0, n}], {n, 0, 30}] (* G. C. Greubel, May 02 2018 *)
-
{a(n)=n!*polcoeff(sum(k=0,n,2^(k^2)*log(1+x+x*O(x^n))^k/k!),n)}
-
{a(n)=sum(k=0,n,2^(k^2)*n!*polcoeff(binomial(x, n), k))}
Showing 1-5 of 5 results.
Comments