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,3

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.

Links

Table of n, a(n) for n=0..17.

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(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

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

Crossrefs

Cf. A138562.

Sequence in context: A115611 A205467 A216986 * A051690 A048668 A001820

Adjacent sequences: A138557 A138558 A138559 * A138561 A138562 A138563

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