A138562 Number of "squashed-tree" graphs with n central nodes, the labeled case, allowing the direct link between L and R.
1, 4, 38, 616, 14744, 479364, 20021768, 1031673164, 63597989864, 4579513525216, 377953469391584, 35211153592004064, 3657198048669038384, 419166387797337858500, 52561549979435515611488, 7158828855330149502246076, 1052478318277669232896492064, 166132533639153074372662711680
Offset: 0
Keywords
Examples
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 =====
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 - 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
Comments