

A232699


Number of labeled pointdetermining bipartite graphs on n vertices.


4



1, 1, 1, 3, 15, 135, 1875, 38745, 1168545, 50017905, 3029330745, 257116925835, 30546104308335, 5065906139629335, 1172940061645387035, 379092680506164049425, 171204492289446788997825, 108139946568584292606269025, 95671942593719946611454522225
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

A graph is pointdetermining if no two vertices have the same set of neighbors. This kind of graph is also called a mating graph.
a(n) is always odd.
For every prime p > 2, a(n) is divisible by p for all n >= p. It follows that, if m is odd and squarefree with largest prime factor q, then a(n) is divisible by m for all n >= q. A similar property appears to hold for odd prime powers, in which case it would hold for all odd numbers.


LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..100 (terms 0..20 from Justin M. Troyka)
Ira Gessel and Ji Li, Enumeration of pointdetermining graphs, arXiv:0705.0042 [math.CO], 20072009.
Andy Hardt, Pete McNeely, Tung Phan, and Justin M. Troyka, Combinatorial species and graph enumeration, arXiv:1312.0542 [math.CO], 2013.


FORMULA

From Andrew Howroyd, Sep 09 2018: (Start)
a(n) = Sum_{k=0..n} Stirling1(n,k)*A047864(k).
E.g.f: sqrt(Sum_{k=0..n} exp(2^k*log(1+x))*log(1+x)^k/k!). (End)


EXAMPLE

Consider n = 3. The triangle graph is pointdetermining, but it is not bipartite, so it is not counted in a(3). The graph 123 is bipartite, but it is not pointdetermining (the vertices on the two ends have the same neighborhood), so it is also not counted in a(3). The only graph counted in a(3) is the graph ** * (with three possible labelings).  Justin M. Troyka, Nov 27 2013


MATHEMATICA

terms = 20;
CoefficientList[Sqrt[Sum[((1+x)^2^k Log[1+x]^k)/k!, {k, 0, terms}]] + O[x]^terms, x] Range[0, terms1]! (* JeanFrançois Alcover, Sep 13 2018, after Andrew Howroyd *)


PROG

(PARI) seq(n)={my(A=log(1+x+O(x*x^n))); Vec(serlaplace(sqrt(sum(k=0, n, exp(2^k*A)*A^k/k!))))} \\ Andrew Howroyd, Sep 09 2018


CROSSREFS

Cf. A006024, A004110 (labeled and unlabeled pointdetermining graphs).
Cf. A092430, A004108 (labeled and unlabeled connected pointdetermining graphs).
Cf. A218090 (unlabeled pointdetermining bipartite graphs).
Cf. A232700, A088974 (labeled and unlabeled connected pointdetermining bipartite graphs).
Sequence in context: A246804 A230166 A059861 * A030539 A028362 A195764
Adjacent sequences: A232696 A232697 A232698 * A232700 A232701 A232702


KEYWORD

nonn


AUTHOR

Justin M. Troyka, Nov 27 2013


STATUS

approved



