OFFSET
0,2
COMMENTS
These are simple connected graphs with n+2 nodes labeled L, R, 1, 2, ..., n. The subgraph on nodes 1..n is a forest (no loops). Nodes L and R are both connected to some subset of 1..n and perhaps to each other.
These are the graphs that can arise when one starts with a tree with m >= n+2 labeled nodes, some of which are colored blue, some are colored red and the remaining n nodes are uncolored. Then all the blue nodes are coalesced into a single node L and all the red nodes into a single node R.
FORMULA
Although we have not written out all the details of the proof, it appears that a(n) ~ 2^n*n^(n-2).
EXAMPLE
a(0) = 1: L--R.
a(1) = 4: L--1--R, 1--L--R, L--R--1 and the 3-cycle L--1--R--L.
a(2) = 38: the 14 examples shown in A138460 plus the same set with an edge joining L and R: 28 in all, plus the following 10 graphs, for a total of 38.
=====
. 1
./..
L---R (number = 2)
.\..
. 2
=====
. 1
./..
L---R (number = 2)
.../
. 2
=====
. 1
./|.
L-|-R (number = 2)
.\|.
. 2
=====
. 1
./|.
L-|-R (number = 4)
..|.
. 2
=====
PROG
(PARI) { a(n) = local(p, q, m); p=partitions(n); sum(j=1, #p, q=p[j]; m=vector(n); for(i=1, #q, m[q[i]]++); n! * prod(i=1, #q, q[i]^(q[i]-2)/q[i]!) / prod(i=1, #m, m[i]!) * (prod(i=1, #q, 4^q[i]-1)*2 - 2^#q*prod(i=1, #q, 2^q[i]-1) ) ) } \\ Max Alekseyev, May 10 2009
CROSSREFS
KEYWORD
nonn
AUTHOR
Nadia Heninger and N. J. A. Sloane, May 10 2008
EXTENSIONS
Edited and extended by Max Alekseyev, May 10 2009
STATUS
approved