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