login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

%I M1421 N0558

%S 1,1,2,5,12,33,90,261,766,2312,7068,21965,68954,218751,699534,2253676,

%T 7305788,23816743,78023602,256738751,848152864,2811996972,9353366564,

%U 31204088381,104384620070,350064856815,1176693361956,3963752002320

%N 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 Also the number of unlabeled connected cographs on n nodes. - _N. J. A. Sloane_ and _Eric W. Weisstein_, Oct 21 2003

%C A cograph is a simple graph which contains no path of length 3 as an induced subgraph. - _Michael Somos_, Apr 19 2014

%C Also called "hierarchies" by Genitrini (2016). - _N. J. A. Sloane_, Mar 24 2017

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

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

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

%D 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 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 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 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.

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

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

%H N. J. A. Sloane, <a href="/A000669/b000669.txt">First 1001 terms of A000669</a>

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H Peter J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See pp. 155, 162, 165, 172. - _N. J. A. Sloane_, Apr 18 2014

%H Peter J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.

%H Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong, <a href="http://arxiv.org/abs/1504.06979">Obstructions for three-coloring graphs without induced paths on six vertices</a>, arXiv preprint arXiv:1504.06979 [math.CO], 2015-2018.

%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Series-parallel networks</a>

%H Philippe Flajolet, <a href="http://algo.inria.fr/libraries/autocomb/schroeder-html/schroeder1.html">A Problem in Statistical Classification Theory</a>

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 72

%H Daniel L. Geisler, <a href="http://www.tetration.org/Combinatorics/index.html">Combinatorics of Iterated Functions</a>

%H A. Genitrini, <a href="http://arxiv.org/abs/1605.00837">Full asymptotic expansion for Polya structures</a>, arXiv:1605.00837 [math.CO], May 03 2016, p. 9.

%H O. Golinelli, <a href="http://arXiv.org/abs/cond-mat/9707023">Asymptotic behavior of two-terminal series-parallel networks</a>, arXiv:cond-mat/9707023 [cond-mat.stat-mech], 1997.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=44">Encyclopedia of Combinatorial Structures 44</a>

%H V. P. Johnson, <a href="http://people.math.sc.edu/czabarka/Theses/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From _N. J. A. Sloane_, Dec 22 2012

%H P. A. MacMahon, <a href="https://doi.org/10.1112/plms/s1-22.1.330">Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees"</a>, Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. Page 333 gives A000084 = 2*A000669.

%H Arnau Mir, Francesc Rossello, Lucia Rotger, <a href="https://arxiv.org/abs/1805.01329">Sound Colless-like balance indices for multifurcating trees</a>, arXiv:1805.01329 [q-bio.PE], 2018.

%H V. Modrak, D. Marton, <a href="http://dx.doi.org/10.3390/e15104285">Development of Metrics and a Complexity Scale for the Topology of Assembly Supply Chains</a>, Entropy 2013, 15, 4285-4299.

%H J. W. Moon, <a href="http://dx.doi.org/10.1016/S0304-0208(08)73057-3">Some enumerative results on series-parallel networks</a>, Annals Discrete Math., 33 (1987), 199-226.

%H J. Riordan, <a href="/A000669/a000669.pdf">Letter to N. J. A. Sloane, Sep. 1970</a>

%H J. Riordan, <a href="/A000262/a000262_1.pdf">Letter to N. J. A. Sloane, Nov 10 1970</a>

%H Audace Amen Vioutou Dossou-Olory, Stephan Wagner, <a href="https://arxiv.org/abs/1802.06696">Inducibility of Topological Trees</a>, arXiv:1802.06696 [math.CO], 2018.

%H Audace Amen Vioutou Dossou-Olory, <a href="https://arxiv.org/abs/1806.03995">The topological trees with extremal Matula numbers</a>, arXiv:1806.03995 [math.CO], 2018.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Series-ParallelNetwork.html">Series-Parallel Network</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Mo#Moon87">Index entries for sequences mentioned in Moon (1987)</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

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

%F a(n) ~ c * d^n / n^(3/2), where d = 3.560839309538943329526129172709667..., c = 0.20638144460078903185013578707202765... . - _Vaclav Kotesovec_, Aug 25 2014

%e G.f. = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 33*x^6 + 90*x^7 + 261*x^8 + ...

%e a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)). - _Michael Somos_, Jul 25 2003

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

%p # Method 3:

%p b:= proc(n, i) option remember; `if`(n=0, 1,

%p `if`(i<1, 0, add(binomial(a(i)+j-1, j)*

%p b(n-i*j, i-1), j=0..n/i)))

%p end:

%p a:= n-> `if`(n<2, n, b(n, n-1)):

%p seq(a(n), n=1..40); # _Alois P. Heinz_, Jan 28 2016

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

%t 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]

%t (* _Jean-Fran├žois Alcover_, Jun 24 2011, after PARI prog. *)

%o (PARI) {a(n) = my(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)}; /* _Michael Somos_, Jul 25 2003 */

%Y Equals (1/2)*A000084 for n >= 2.

%Y Cf. A000055, A000311, A001678, A007827.

%Y Cf. A000311, labeled hierarchies on n points.

%Y Column 1 of A319254.

%Y Main diagonal of A292085.

%Y Row sums of A292086.

%K nonn,nice,easy

%O 1,3

%A _N. J. A. Sloane_, John Riordan

%E Sequence crossreference 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 | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 17:55 EDT 2018. Contains 316237 sequences. (Running on oeis4.)