Remark. The OEIS entry A059167 sends
us to Harary and Palmer, Graphical Enumeration, which in turn sends
us to Some unusual enumeration problems by Read. There really is no
reason not to consult these sources.
Here are some ideas on the subject. Let $\mathcal{G}$ be the
species of all labeled graphs and $\mathcal{A}$ be the species of
labeled graphs with no endpoints and $\mathcal{B}$ be the species of
connected labeled graphs with no endpoints. Finally let $\mathcal{T}$
be the species of rooted labeled trees. Also introduce $\mathcal{U},$
unrooted labeled trees. We have by inspection that
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\mathcal{G} = \textsc{SET}(\mathcal{U} +
\mathcal{B}_{\ge 3}(\mathcal{T}))
\quad\text{and}\quad
\mathcal{A} = \textsc{SET}(\mathcal{B})$$
Translating to generating functions we get
$$G(z) = \exp(U(z) + B_{\ge 3}(T(z))
\quad\text{and}\quad
A(z) = \exp(B(z)).$$
and the goal is to compute $A(z).$ We get for $G(z)$
$$G(z) =
\exp\left(U(z) - T(z) + B(T(z))\right)
\\ =
\exp\left(U(z) - T(z) + \log A(T(z))\right)
\\ = \sum_{n\ge 0} 2^{n\choose 2} \frac{z^n}{n!}.$$
Here we have made use of the fact that the number of connected graphs
with no endpoints is one for the singleton node and zero for graphs on
two nodes.
Now we have for $\mathcal{T}$ that
$$\mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T})$$
which yields
$$T(z) = z \exp T(z)
\quad \text{or} \quad z = T(z) \exp (-T(z)).$$
Furthermore we have combinatorially
$$T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}
\quad \text{and} \quad
U(z) = \sum_{n\ge 1} n^{n-2} \frac{z^n}{n!}.$$
We now claim that
$$U(z) = T(z) - \frac{1}{2} T(z)^2.$$
This yields for the coefficient $[z^n] U(z)$ where $n\ge 1$
$$[z^n] U(z) =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}}
\left(T(z) - \frac{1}{2} T(z)^2\right) \; dz.$$
Using $T(z) = w$ and $z = w \exp(-w)$ and $dz = (\exp(-w) - w\exp(-w))
\; dw$ we obtain (this is a standard computation)
$$\frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{\exp((n+1)w)}{w^{n+1}}
\left(w-\frac{1}{2}w^2\right)
\exp(-w) (1-w)
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{\exp(nw)}{w^{n}}
\left(\frac{1}{2} w^2 - \frac{3}{2} w + 1\right)
\; dw.$$
This is for $n\ge 3$ (the small $n$ are left to the reader)
$$\frac{1}{2}\frac{n^{n-3}}{(n-3)!}
- \frac{3}{2}\frac{n^{n-2}}{(n-2)!}
+ \frac{n^{n-1}}{(n-1)!}
\\ = \frac{n^{n-2}}{n!}
\times \left(\frac{1}{2} \frac{n(n-1)(n-2)}{n}
- \frac{3}{2} n (n-1)
+ n^2\right) = \frac{n^{n-2}}{n!}.$$
This verifies the claim. Use this on $G(z)$ to get
$$G(z) =
\exp\left(-\frac{1}{2}T(z)^2
+ \log A(T(z))\right) = A(T(z)) \exp(-T(z)^2/2)$$
or
$$A(T(z)) = G(z) \exp(T(z)^2/2).$$
In order to conclude we put $T(z)=w$ and use the functional equation
of $T(z)$ which yields $z=w/\exp(w)$ to obtain
$$A(w) = G(w/\exp(w)) \exp(w^2/2).$$
This is
$$\bbox[5px,border:2px solid #00A000]{
A(w) = \exp\left(\frac{w^2}{2}\right)
\sum_{n\ge 0} \left(\frac{w}{e^w}\right)^n \frac{2^{n\choose 2}}{n!}.}$$
The following memory-efficient Perl script computes the first eight
values for comparison with the generating function.
#! /usr/bin/perl -w
#
sub enumerate {
my ($n, $deg, $sofar, $data,
$pos, $match, $verif) = @_;
my $vert;
if($verif == 1){
for($vert=1; $vert <= $n; $vert++){
last if $deg->[$vert] == 1;
}
$$match++ if $vert == $n+1;
}
return if $pos >= scalar(@$data);
return if $pos > 0 &&
$data->[$pos]->[0] > $data->[$pos-1]->[0] &&
$deg->[$data->[$pos-1]->[0]] == 1;
enumerate($n, $deg, $sofar, $data, $pos+1, $match, 0);
my ($u, $v) = @{$data->[$pos]};
$deg->[$u]++; $deg->[$v]++;
push @$sofar, $data->[$pos];
enumerate($n, $deg, $sofar, $data, $pos+1, $match, 1);
pop @$sofar;
$deg->[$u]--; $deg->[$v]--;
1;
}
MAIN: {
my $mx = int(shift || 5);
for(my $n=1; $n <= $mx; $n++){
my @srcdata;
for(my $u=1; $u <= $n; $u++){
for(my $v=$u+1; $v <= $n; $v++){
push @srcdata, [$u, $v];
}
}
my $noendp = 0; my @degsrc = (0) x ($n+1);
enumerate($n, \@degsrc, [],
\@srcdata, 0, \$noendp, 1);
print "$n: $noendp\n";
}
1;
}
The output was the following table:
1: 1
2: 1
3: 2
4: 15
5: 314
6: 13757
7: 1142968
8: 178281041
On the other hand Maple says:
> XGF := exp(z^2/2)*add((z/exp(z))^n*2^binomial(n,2)/n!, n=0..12):
> seq(n!*coeftayl(XGF, z=0, n), n=0..8);
1, 1, 1, 2, 15, 314, 13757, 1142968, 178281041
We would use recurrence relations to extract higher values.
Addendum, Sep 26, 2016. As per request we now treat the case of
graphs having one endpoint. The species equation now becomes
$$\textsc{SET}(\mathcal{Z})
\times \textsc{SET}(-\mathcal{Z}
+ \mathcal{B}(\mathcal{Z}))^{\Large\star}
\times \mathcal{P}(\mathcal{Z}).$$
This reads from left to right (the star denotes marking), first, a set
of singletons, second a set of connected graphs with no endpoints
where a node is marked and third, a rooted path (species
$\mathcal{P}$), not empty, that is attached at the marked node. Now
observe that there are $n!$ rooted paths on $n$ nodes and hence
$$P(z) = \sum_{n\ge 1} n! \frac{z^n}{n!} = \frac{z}{1-z}.$$
We thus obtain for the generating function (we mark using the operator
$z\frac{d}{dz}$)
$$\exp(z) \frac{z}{1-z}
z \left(\exp \left(-z + \log A(z)\right)\right)'
\\ = \exp(z) \frac{z}{1-z}
z \left(A(z) \exp(-z)\right)'
\\ = \exp(z) \frac{z}{1-z}
z (A'(z) \exp(-z) - A(z) \exp(-z))
\\ = \frac{z^2}{1-z} (A'(z)-A(z)).$$
These data can be verified with the following Perl script (not the
simplest possible but optimized to produce the value for $n=8$).
#! /usr/bin/perl -w
#
sub enumerate {
my ($n, $k, $endp, $deg, $sofar, $data,
$pos, $match, $verif) = @_;
$$match++ if ($verif == 1 && $endp == $k);
return if $pos >= scalar(@$data);
if($pos > 0 &&
$data->[$pos]->[0] > $data->[$pos-1]->[0]){
my $epcount = 0;
for(my $vert = 1;
$vert < $data->[$pos]->[0]; $vert++){
$epcount++ if $deg->[$vert] == 1;
}
return if $epcount > $k;
}
enumerate($n, $k, $endp, $deg,
$sofar, $data, $pos+1, $match, 0);
my ($u, $v) = @{$data->[$pos]};
$deg->[$u]++; $deg->[$v]++;
$endp++ if $deg->[$u] == 1;
$endp-- if $deg->[$u] == 2;
$endp++ if $deg->[$v] == 1;
$endp-- if $deg->[$v] == 2;
push @$sofar, $data->[$pos];
enumerate($n, $k, $endp, $deg,
$sofar, $data, $pos+1, $match, 1);
pop @$sofar;
$endp-- if $deg->[$u] == 1;
$endp++ if $deg->[$u] == 2;
$endp-- if $deg->[$v] == 1;
$endp++ if $deg->[$v] == 2;
$deg->[$u]--; $deg->[$v]--;
1;
}
MAIN: {
my $mx = int(shift || 5);
my $epsrch = int(shift || 0);
for(my $n=1; $n <= $mx; $n++){
my @srcdata;
for(my $u=1; $u <= $n; $u++){
for(my $v=$u+1; $v <= $n; $v++){
push @srcdata, [$u, $v];
}
}
my $noendp = 0; my @degsrc = (0) x ($n+1);
enumerate($n, $epsrch, 0, \@degsrc, [],
\@srcdata, 0, \$noendp, 1);
print "$n: $noendp\n";
}
1;
}
This produced the following table:
1: 0
2: 0
3: 0
4: 12
5: 320
6: 10890
7: 640836
8: 68362504
Maple says:
> XS := series(z^2/(1-z)*(diff(XGF, z)-XGF), z=0, 9):
> seq(n!*coeff(XS, z, n), n=1..8);
0, 0, 0, 12, 320, 10890, 640836, 68362504
We can also treat the problem of enumerating labeled graphs with two
endpoints. Now there are three cases: first case, a set of singletons,
an unrooted path on at least two nodes and a set of connected
components with no endpoints. We get
$$\exp(z) \times \frac{1}{2} \frac{z^2}{1-z}
\times \exp(-z + \log A(z))
= \frac{1}{2} \frac{z^2}{1-z} A(z).$$
Second, a set of singletons and two rooted paths attached to two
different nodes from a set of connected components with no endpoints.
This yields
$$\exp(z) \times \frac{z^2}{(1-z)^2} \times
\frac{1}{2} z^2 \frac{d}{dz} \frac{d}{dz} \exp(-z + \log A(z))
\\ = \exp(z) \times \frac{z^2}{(1-z)^2} \times
\frac{1}{2} z^2 \frac{d}{dz} \frac{d}{dz} \exp(-z) A(z)
\\ = \exp(z) \times \frac{z^2}{(1-z)^2} \times
\frac{1}{2} z^2 \frac{d}{dz} (\exp(-z) A'(z) - \exp(-z) A(z))
\\ = \exp(z) \times \frac{z^2}{(1-z)^2} \\ \times
\frac{1}{2} z^2 (\exp(-z) A''(z) - 2\exp(-z) A'(z) + \exp(-z) A(z))
\\ = \frac{1}{2} \frac{z^4}{(1-z)^2} (A''(z) - 2A'(z) + A(z)).$$
Third, a set of singletons and a fork attached to a node of a set of
connected components with no endpoints. The fork is
$$\frac{1}{2} \frac{1}{1-z} \frac{z^2}{(1-z)^2}$$
(the first term is the handle) which yields
$$\exp(z) \times \frac{1}{2} \frac{z^2}{(1-z)^3}
\times z\frac{d}{dz} \exp(-z + \log A(z))
\\ = \exp(z) \times \frac{1}{2} \frac{z^2}{(1-z)^3}
\times z\frac{d}{dz} \exp(-z) A(z)
\\ = \exp(z) \times \frac{1}{2} \frac{z^2}{(1-z)^3}
\times z(\exp(-z) A'(z) - \exp(-z) A(z))
\\ = \frac{1}{2} \frac{z^3}{(1-z)^3} (A'(z) - A(z)).$$
Collecting everything we obtain
$$\frac{1}{2} \frac{z^2}{1-z} A(z)
\\ + \frac{1}{2} \frac{z^4}{(1-z)^2} (A''(z) - 2A'(z) + A(z))
\\ + \frac{1}{2} \frac{z^3}{(1-z)^3} (A'(z) - A(z)).$$
The Perl script will produce the following table:
1: 0
2: 1
3: 6
4: 30
5: 260
6: 5445
7: 228564
8: 17288852
while Maple says:
> K1 := 1/2*z^2/(1-z)*XGF:
> K2 := 1/2*z^4/(1-z)^2*(diff(XGF, z$2)-2*diff(XGF,z)+XGF):
> K3 := 1/2*z^3/(1-z)^3*(diff(XGF, z)-XGF):
> XS := series(K1+K2+K3, z=0, 9):
> seq(n!*coeff(XS, z, n), n=1..8);
0, 1, 6, 30, 260, 5445, 228564, 17288852
All of these need careful checking as it is possible that errors in
the species decomposition might only become apparent with large values
of $n.$
Addendum, Sep 27, 2016. To enhance this post and make it more
useful we now treat the case of graphs having three
endpoints. Observe that these calculations are conjectural in nature
and require independent verification, most likely through recurrence
relations.
First case, set of singletons, a star (union of three paths) and a
set of connected components with no endpoints. We get
$$\exp(z)\times \frac{1}{6} z \frac{z^3}{(1-z)^3} \times
\exp(-z+\log A(z))
= \frac{1}{6} \frac{z^4}{(1-z)^3} A(z).$$
Second case, a set of singletons, an unrooted path and a set of
connected components with one node marked to which a path is
attached. We have
$$\exp(z)\times \frac{1}{2}\frac{z^2}{1-z} \times
\frac{z}{1-z} \times z\frac{d}{dz} \exp(-z+\log A(z))
\\ = \frac{1}{2}\frac{z^4}{(1-z)^2} (A'(z)-A(z)).$$
Third case, a set of singletons and three rooted paths attached to
three marked nodes from the set of connected components with no
endpoints.
$$\exp(z)\times \frac{z^3}{(1-z)^3} \times
\frac{1}{6} z^3\frac{d}{dz}\frac{d}{dz}\frac{d}{dz} \exp(-z+\log A(z))
\\ = \frac{1}{6} \frac{z^6}{(1-z)^3} (A'''(z)-3A''(z)+3A'(z)-A(z)).$$
Fourth case, a set of singletons, a rooted path and a fork attached to
two marked sites among the components with no endpoints (no symmetry
between the path and the fork):
$$\exp(z) \times \frac{z}{1-z} \times
\frac{1}{2} \frac{1}{1-z} \frac{z^2}{(1-z)^2}
\times z^2 \frac{d}{dz}\frac{d}{dz} \exp(-z+\log A(z))
\\ = \frac{1}{2} \frac{z^5}{(1-z)^4}
(A''(z)-2A'(z)+A(z)).$$
Fifth case, singletons, and a triple fork attached to a marked site
among the components with no endpoints.
$$\exp(z)\times \frac{1}{6} \frac{1}{1-z}\frac{z^3}{(1-z)^3}
\times z\frac{d}{dz} \exp(-z+\log A(z))
\\= \frac{1}{6} \frac{z^4}{(1-z)^4} (A'(z)-A(z)).$$
Finally, a repeat, but with the fork branching two times, which is the
handle, possibly empty, to which are attached two paths, one of which
forks:
$$\frac{1}{1-z} \times \frac{z}{1-z}
\frac{z}{1-z} \times \frac{1}{2} \frac{z}{1-z}\frac{z}{1-z}$$
for a contribution of
$$\exp(z)\times \frac{1}{2} \frac{z^4}{(1-z)^5}
\times z\frac{d}{dz} \exp(-z+\log A(z))
\\= \frac{1}{2} \frac{z^5}{(1-z)^5} (A'(z)-A(z)).$$
Collect these six to get the desired EGF.
Here the Perl script will produce the table
1: 0
2: 0
3: 0
4: 4
5: 80
6: 1860
7: 64680
8: 3666600
and Maple says
> K1 := 1/6*z^4/(1-z)^3*XGF:
> K2 := 1/2*z^4/(1-z)^2*(diff(XGF,z)-XGF):
> K3 := 1/6*z^6/(1-z)^3*(diff(XGF, z$3)-3*diff(XGF, z$2)+3*diff(XGF,z)-XGF):
> K4 := 1/2*z^5/(1-z)^4*(diff(XGF, z$2)-2*diff(XGF,z)+XGF):
> K5 := 1/6*z^4/(1-z)^4*(diff(XGF,z)-XGF):
> K6 := 1/2*z^5/(1-z)^5*(diff(XGF,z)-XGF):
> XS := series(K1+K2+K3+K4+K5+K6, z=0, 9):
> seq(n!*coeff(XS, z, n), n=1..8);
0, 0, 0, 4, 80, 1860, 64680, 3666600
