cp's OEIS Frontend

A138560 Number of "squashed-tree" graphs with n central nodes, the labeled case, not allowing the direct link between L and R.

%I A138560 #10 Feb 20 2018 02:44:57
%S A138560 0,1,14,265,6830,230511,9813824,510662531,31637636492,2283908878873,
%T A138560 188734671539720,17594292380775969,1828013405513246504,
%U A138560 209549687662076216495,26278678714657914834056,3579272018433287670435859,526228717479514441247416016,83065444843454983344683712849
%N A138560 Number of "squashed-tree" graphs with n central nodes, the labeled case, not allowing the direct link between L and R.
%C A138560 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.
%F A138560 Although we have not written out all the details of the proof, it appears that a(n) ~ 2^n*n^(n-2).
%e A138560 a(1) = 1: L--1--R.
%e A138560 a(2) = 14:
%e A138560 =====
%e A138560 . 1
%e A138560 ./.\
%e A138560 L . R (number = 1)
%e A138560 .\./
%e A138560 . 2
%e A138560 =====
%e A138560 . 1
%e A138560 ./.\
%e A138560 L . R (number = 4)
%e A138560 .\..
%e A138560 . 2
%e A138560 =====
%e A138560 . 1
%e A138560 ./|\
%e A138560 L | R (number = 1)
%e A138560 .\|/
%e A138560 . 2
%e A138560 =====
%e A138560 . 1
%e A138560 ./|\
%e A138560 L | R (number = 4)
%e A138560 .\|.
%e A138560 . 2
%e A138560 =====
%e A138560 . 1
%e A138560 ./|\
%e A138560 L | R (number = 2)
%e A138560 . |.
%e A138560 . 2
%e A138560 =====
%e A138560 . 1
%e A138560 . |\
%e A138560 L | R (number = 2)
%e A138560 .\|.
%e A138560 . 2
%e A138560 =====
%e A138560 Total = 14
%o A138560 (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
%Y A138560 Cf. A138562.
%K A138560 nonn
%O A138560 0,3
%A A138560 _Nadia Heninger_ and _N. J. A. Sloane_, May 10 2008
%E A138560 Edited and extended by _Max Alekseyev_, May 10 2009