A138560 Number of "squashed-tree" graphs with n central nodes, the labeled case, not allowing the direct link between L and R.

0, 1, 14, 265, 6830, 230511, 9813824, 510662531, 31637636492, 2283908878873, 188734671539720, 17594292380775969, 1828013405513246504, 209549687662076216495, 26278678714657914834056, 3579272018433287670435859, 526228717479514441247416016, 83065444843454983344683712849

Offset: 0

Author

Nadia Heninger and N. J. A. Sloane, May 10 2008

Keywords

• nonn

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 but not to each other.

Examples

			a(1) = 1: L--1--R.
a(2) = 14:
=====
. 1
./.\
L . R (number = 1)
.\./
. 2
=====
. 1
./.\
L . R (number = 4)
.\..
. 2
=====
. 1
./|\
L | R (number = 1)
.\|/
. 2
=====
. 1
./|\
L | R (number = 4)
.\|.
. 2
=====
. 1
./|\
L | R (number = 2)
. |.
. 2
=====
. 1
. |\
L | R (number = 2)
.\|.
. 2
=====
Total = 14
		

Crossrefs

Cf. A138562.

Programs

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^#q*prod(i=1,#q,2^q[i]-1) ) ) } \\ Max Alekseyev, May 10 2009

Formula

Although we have not written out all the details of the proof, it appears that a(n) ~ 2^n*n^(n-2).

Extensions

Edited and extended by Max Alekseyev, May 10 2009