|
Search: id:A138560
|
|
|
| A138560 |
|
Number of "squashed-tree" graphs with n central nodes, the labeled case, not allowing the direct link between L and R. |
|
+0
2
|
|
| 0, 1, 14, 265, 6830, 230511, 9813824, 510662531, 31637636492, 2283908878873, 188734671539720, 17594292380775969, 1828013405513246504, 209549687662076216495, 26278678714657914834056, 3579272018433287670435859, 526228717479514441247416016, 83065444843454983344683712849
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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.
|
|
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
|
|
PROGRAM
|
(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) ) ) } [From Max Alekseyev]
|
|
CROSSREFS
|
Cf. A138562.
Sequence in context: A159516 A005611 A115611 this_sequence A051690 A048668 A001820
Adjacent sequences: A138557 A138558 A138559 this_sequence A138561 A138562 A138563
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Nadia Heninger (nadiah(AT)cs.princeton.edu) and N. J. A. Sloane (njas(AT)research.att.com), May 10 2008
|
|
EXTENSIONS
|
Edited and extended by Max Alekseyev (maxale(AT)gmail.com), May 10 2009
|
|
|
Search completed in 0.002 seconds
|
