Search: id:A138562
Results 1-1 of 1 results found.

%I A138562
%S A138562 1,4,38,616,14744,479364,20021768,1031673164,63597989864,4579513525216,
               377953469391584,
%T A138562 35211153592004064,3657198048669038384,419166387797337858500,52561549979435515611488,
%U A138562 7158828855330149502246076,1052478318277669232896492064,166132533639153074372662711680
%N A138562 Number of "squashed-tree" graphs with n central nodes, the labeled case, 
               allowing the direct link between L and R.
%C A138562 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.
%C A138562 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.
%F A138562 Although we have not written out all the details of the proof, it appears 
               that a(n) ~ 2^n*n^(n-2).
%e A138562 a(0) = 1: L--R.
%e A138562 a(1) = 4: L--1--R, 1--L--R, L--R--1 and the 3-cycle L--1--R--L.
%e A138562 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.
%e A138562 =====
%e A138562 . 1
%e A138562 ./..
%e A138562 L---R (number = 2)
%e A138562 .\..
%e A138562 . 2
%e A138562 =====
%e A138562 . 1
%e A138562 ./..
%e A138562 L---R (number = 2)
%e A138562 .../
%e A138562 . 2
%e A138562 =====
%e A138562 . 1
%e A138562 ./|.
%e A138562 L-|-R (number = 2)
%e A138562 .\|.
%e A138562 . 2
%e A138562 =====
%e A138562 . 1
%e A138562 ./|.
%e A138562 L-|-R (number = 4)
%e A138562 ..|.
%e A138562 . 2
%e A138562 =====
%o A138562 (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]
%Y A138562 Cf. A138560. A001187(n+2) is an upper bound.
%Y A138562 Sequence in context: A113664 A077745 A138214 this_sequence A096332 A084284 
               A084285
%Y A138562 Adjacent sequences: A138559 A138560 A138561 this_sequence A138563 A138564 
               A138565
%K A138562 nonn
%O A138562 0,2
%A A138562 Nadia Heninger (nadiah(AT)cs.princeton.edu) and N. J. A. Sloane (njas(AT)research.att.com), 
               May 10 2008
%E A138562 Edited and extended by Max Alekseyev (maxale(AT)gmail.com), May 10 2009

Search completed in 0.001 seconds