Here, an endpoint is a vertex of degree $1$. For $n=1,2,3,\ldots$ the number of such graphs is $1,1,2,15,314,\ldots\;$. This is sequence A059167 in Sloane's OEIS. The exponential generating function (e.g.f.) is given in the OEIS entry:
$$\exp\left(\frac{x^2}2\right)\sum_{n=0}^\infty\frac1{n!}\left(\frac{x}{e^x}\right)^n2^{\binom{n}2}$$
Is there some way to easily arrive at the generating function by applying symbolic derivation methods such as those described in Flajolet and Sedgewick Analytic Combinatorics?
I understand the factor $\exp(\frac{x^2}{2})$. I also see that the summation WITHOUT THE FACTOR $\exp(-x)$ would be the e.g.f. for the total number of simple labeled graphs.
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:
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, 178281041We 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:
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, 68362504We 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:
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, 17288852All 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
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