This site is supported by donations to The OEIS Foundation.



Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
(Formerly M1421 N0558)
1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, 218751, 699534, 2253676, 7305788, 23816743, 78023602, 256738751, 848152864, 2811996972, 9353366564, 31204088381, 104384620070, 350064856815, 1176693361956, 3963752002320 (list; graph; refs; listen; history; text; internal format)



Also the number of unlabeled connected cographs on n nodes. - N. J. A. Sloane and Eric W Weisstein, Oct 21, 2003.


N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 43.

A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999. (For definition of cograph)

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.

A. Cayley, Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 3, p. 246.

V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012; http://www.math.sc.edu/~czabarka/JohnsonThesis.pdf. - From N. J. A. Sloane, Dec 22 2012

D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 5.

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. Reprinted in Discrete Appl. Math., 54 (1994), 225-228.

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.

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.

V. Modrak, D. Marton, Development of Metrics and a Complexity Scale for the Topology of Assembly Supply Chains, Entropy 2013, 15, 4285-4299; doi:10.3390/e15104285

J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226.

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.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


N. J. A. Sloane, First 1001 terms of A000669

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

S. R. Finch, Series-parallel networks

Philippe Flajolet, A Problem in Statistical Classification Theory

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72

Daniel L. Geisler, Combinatorics of Iterated Functions

O. Golinelli, Asymptotic behavior of two-terminal series-parallel networks.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 44

Eric Weisstein's World of Mathematics, Series-Parallel Network

Index entries for sequences related to rooted trees

Index entries for sequences mentioned in Moon (1987)

Index entries for sequences related to trees


Product_{k>0} 1/(1-x^k)^a_k = 1+x+2*Sum_{k>1} a_k*x^k.


a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)).


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];

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;

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];


a[1] = 1; a[n_] := (s = Series[1/(1 - x), {x, 0, n}];

Do[s = Series[s/(1 - x^k)^Coefficient[s, x^k], {x, 0, n}], {k, 2, n}]; Coefficient[s, x^n]/2); Array[a, 28]

(* Jean-Fran├žois Alcover, Jun 24 2011, after PARI prog. *)


(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)


Equals (1/2)*A000084 for n >= 2. Cf. A000055, A000311, A001678, A007827.

Cf. A000311, labeled hierarchies on n points.

Sequence in context: A000560 A212823 A032124 * A191769 A221206 A225616

Adjacent sequences:  A000666 A000667 A000668 * A000670 A000671 A000672




N. J. A. Sloane, John Riordan


Sequence cross reference fixed by Sean A. Irvine, Sep 15 2009



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 18 05:28 EDT 2014. Contains 240688 sequences.