|
| |
|
|
A138562
|
|
Number of "squashed-tree" graphs with n central nodes, the labeled case, allowing the direct link between L and R.
|
|
1
| |
|
|
1, 4, 38, 616, 14744, 479364, 20021768, 1031673164, 63597989864, 4579513525216, 377953469391584, 35211153592004064, 3657198048669038384, 419166387797337858500, 52561549979435515611488, 7158828855330149502246076, 1052478318277669232896492064, 166132533639153074372662711680
(list; graph; refs; listen; history; internal format)
|
|
|
|
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) ) ) } [From Max Alekseyev]
|
|
|
CROSSREFS
| Cf. A138560. A001187(n+2) is an upper bound.
Sequence in context: A077745 A138214 A195442 * A177382 A201861 A171779
Adjacent sequences: A138559 A138560 A138561 * A138563 A138564 A138565
|
|
|
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
|
| |
|
|
