|
|
A232699
|
|
Number of labeled point-determining 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 point-determining 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
|
|
|
FORMULA
|
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 point-determining, but it is not bipartite, so it is not counted in a(3). The graph 1--2--3 is bipartite, but it is not point-determining (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;
|
|
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 point-determining graphs).
Cf. A092430, A004108 (labeled and unlabeled connected point-determining graphs).
Cf. A218090 (unlabeled point-determining bipartite graphs).
Cf. A232700, A088974 (labeled and unlabeled connected point-determining bipartite graphs).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|