

A000669


Number of seriesreduced planted trees with n leaves. Also the number of essentially series seriesparallel networks with n edges; also the number of essentially parallel seriesparallel networks with n edges.
(Formerly M1421 N0558)


34



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)



OFFSET

1,3


COMMENTS

Also the number of unlabeled connected cographs on n nodes.  N. J. A. Sloane and Eric W. Weisstein, Oct 21 2003
A cograph is a simple graph which contains no path of length 3 as an induced subgraph.  Michael Somos, Apr 19 2014


REFERENCES

N. L. Biggs et al., Graph Theory 17361936, Oxford, 1976, p. 43.
A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999. (For definition of cograph)
Cameron, Peter J. Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155183. MR0891613 (89a:05009). See p. 155.  N. J. A. Sloane, Apr 18 2014
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89102.
A. Cayley, Collected Mathematical Papers. Vols. 113, Cambridge Univ. Press, London, 18891897, 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 2.3.4.4 5.
P. A. MacMahon, Yoketrains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330346; reprinted in Coll. Papers I, pp. 600616. Page 333 gives A000084 = 2*A000669. Reprinted in Discrete Appl. Math., 54 (1994), 225228.
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. 107108. 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, 42854299; doi:10.3390/e15104285
J. W. Moon, Some enumerative results on seriesparallel networks, Annals Discrete Math., 33 (1987), 199226.
J. Riordan and C. E. Shannon, The number of twoterminal seriesparallel networks, J. Math. Phys., 21 (1942), 8393 (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. 560570.
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).


LINKS

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.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155183. See pp. 162, 165, 172.
Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong, Obstructions for threecoloring graphs without induced paths on six vertices, arXiv preprint, 2015.
S. R. Finch, Seriesparallel 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 twoterminal seriesparallel networks.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 44
Eric Weisstein's World of Mathematics, SeriesParallel Network
Index entries for sequences related to rooted trees
Index entries for sequences mentioned in Moon (1987)
Index entries for sequences related to trees


FORMULA

Product_{k>0} 1/(1x^k)^a_k = 1+x+2*Sum_{k>1} a_k*x^k.
a(n) ~ c * d^n / n^(3/2), where d = 3.560839309538943329526129172709667..., c = 0.20638144460078903185013578707202765... .  Vaclav Kotesovec, Aug 25 2014


EXAMPLE

a(4)=5 with the following seriesreduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)).
G.f. = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 33*x^6 + 90*x^7 + 261*x^8 + ...


MAPLE

Method 1: a := [1, 1]; for n from 3 to 30 do L := series( mul( (1x^k)^(a[k]), k=1..n1)/(1x^n)^b, x, n+1); t1 := coeff(L, x, n); R := series( 1+2*add(a[k]*x^k, k=1..n1)+2*b*x^n, x, n+1); t2 := coeff(R, x, n); t3 := solve(t1t2, 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[m1]+2*add(p[k]*a[mk], k=1..m2)+t3; a[m] := t4/m; p[m] := t3+t4; od: # A000669 := n> a[n]; A058757 := n>p[n];


MATHEMATICA

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]
(* JeanFrançois Alcover, Jun 24 2011, after PARI prog. *)


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)};


CROSSREFS

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


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane, John Riordan


EXTENSIONS

Sequence crossreference fixed by Sean A. Irvine, Sep 15 2009


STATUS

approved



