%I A000669 M1421 N0558
%S A000669 1,1,2,5,12,33,90,261,766,2312,7068,21965,68954,218751,699534,2253676,
%T A000669 7305788,23816743,78023602,256738751,848152864,2811996972,9353366564,
%U A000669 31204088381,104384620070,350064856815,1176693361956,3963752002320
%N A000669 Number of series-reduced planted trees with n leaves. Also the number
of essentially series series-parallel networks with n edges; also
the number of essentially parallel series-parallel networks with
n edges.
%C A000669 Also the number of unlabeled connected cographs on n nodes. - N. J. A.
Sloane (njas(AT)research.att.com) and Eric W Weisstein, Oct 21, 2003.
%D A000669 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A000669 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%D A000669 N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 43.
%D A000669 A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey,
SIAM Publications, 1999. (For definition of cograph)
%D A000669 P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989),
89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas,
Annals of Discrete Math., 43 (1989), 89-102.
%D A000669 A. Cayley, Collected Mathematical Papers. Vols. 1-13, Cambridge Univ.
Press, London, 1889-1897, Vol. 3, p. 246.
%D A000669 D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p.
589, Answers to Exercises Section 2.3.4.4 5.
%D A000669 P. A. MacMahon, Yoke-trains and multipartite compositions in connexion
with the analytical forms called "trees", Proc. London Math. Soc.
22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. Page
333 gives A000084 = 2*A000669.
%D A000669 L. F. Meyers, Corrections and additions to Tree Representations in Linguistics.
Report 3, 1966, p. 138. Project on Linguistic Analysis, Ohio State
University Research Foundation, Columbus, Ohio.
%D A000669 L. F. Meyers and W. S.-Y. Wang, Tree Representations in Linguistics.
Report 3, 1963, pp. 107-108. Project on Linguistic Analysis, Ohio
State University Research Foundation, Columbus, Ohio.
%D A000669 J. W. Moon, Some enumerative results on series-parallel networks, Annals
Discrete Math., 33 (1987), 199-226.
%D A000669 J. Riordan and C. E. Shannon, The number of two-terminal series-parallel
networks, J. Math. Phys., 21 (1942), 83-93 (the numbers called a_n
in this paper). Reprinted in Claude Elwood Shannon: Collected Papers,
edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993,
pp. 560-570.
%H A000669 N. J. A. Sloane, <a href="b000669.txt">First 1001 terms of A000669</a>
%H A000669 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
Sequences realized by oligomorphic permutation groups</a>, J. Integ.
Seqs. Vol. 3 (2000), #00.1.5.
%H A000669 S. R. Finch, <a href="http://algo.inria.fr/bsolve/">Series-parallel networks</
a>
%H A000669 Philippe Flajolet, <a href="http://algo.inria.fr/libraries/autocomb/schroeder-html/
schroeder1.html">A Problem in Statistical Classification Theory</
a>
%H A000669 Daniel L. Geisler, <a href="http://www.tetration.org/Combinatorics/index.html">
Combinatorics of Iterated Functions</a>
%H A000669 O. Golinelli, <a href="http://arXiv.org/abs/cond-mat/9707023">Asymptotic
behavior of two-terminal series-parallel networks</a>.
%H A000669 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=44">
Encyclopedia of Combinatorial Structures 44</a>
%H A000669 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
Series-ParallelNetwork.html">Series-Parallel Network</a>
%H A000669 <a href="Sindx_Ro.html#rooted">Index entries for sequences related to
rooted trees</a>
%H A000669 <a href="Sindx_Mo.html#Moon87">Index entries for sequences mentioned
in Moon (1987)</a>
%H A000669 <a href="Sindx_Tra.html#trees">Index entries for sequences related to
trees</a>
%H A000669 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
Publications/books.html">Analytic Combinatorics</a>, 2009; see page
72
%F A000669 Product_{k>0} 1/(1-x^k)^a_k = 1+x+2*Sum_{k>1} a_k*x^k.
%e A000669 a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)),
(o(ooo)), (o(o(oo))), ((oo)(oo)).
%p A000669 Method 1: a := [1,1]; for n from 3 to 30 do L := series( mul( (1-x^k)^(-a[k]),
k=1..n-1)/(1-x^n)^b, x,n+1); t1 := coeff(L,x,n); R := series( 1+2*add(a[k]*x^k,
k=1..n-1)+2*b*x^n, x, n+1); t2 := coeff(R,x,n); t3 := solve(t1-t2,
b); a := [op(a),t3]; od: A000669 := n-> a[n];
%p A000669 Method 2, more efficient: with(numtheory): M := 1001; a := array(0..M);
p := array(0..M); a[1] := 1; a[2] := 1; a[3] := 2; p[1] := 1; p[2]
:= 3; p[3] := 7;
%p A000669 Method 2, cont.: for m from 4 to M do t1 := divisors(m); t3 := 0; for
d in t1 minus {m} do t3 := t3+d*a[d]; od: t4 := p[m-1]+2*add(p[k]*a[m-k],
k=1..m-2)+t3; a[m] := t4/m; p[m] := t3+t4; od: # A000669 := n-> a[n];
A058757 := n->p[n];
%o A000669 (PARI) a(n)=local(A,X); if(n<2,n>0,X=x+x*O(x^n); A=1/(1-X); for(k=2,n,
A/=(1-X^k)^polcoeff(A,k)); polcoeff(A,n)/2)
%Y A000669 Equals (1/2)*A000084 for n >= 2. Cf. A000055, A000311, A001678, A007827.
%Y A000669 Cf. A000311, labeled hierarchies on n points.
%Y A000669 Sequence in context: A084075 A000560 A032124 this_sequence A004114 A076864
A032292
%Y A000669 Adjacent sequences: A000666 A000667 A000668 this_sequence A000670 A000671
A000672
%K A000669 nonn,nice,easy
%O A000669 1,3
%A A000669 N. J. A. Sloane (njas(AT)research.att.com), John Riordan
%E A000669 Sequence cross reference fixed by Sean A. Irvine (sairvin(AT)xtra.co.nz),
Sep 15 2009
|
