|
%I M1421 N0558 #156 May 19 2023 04:15:16
%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 Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, and Martin Leuner, <a href="https://arxiv.org/abs/1907.01073">On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture</a>, arXiv:1907.01073 [math.CO], 2019.
%H Peter 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, and 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 Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Series-parallel networks</a>
%H Steven R. Finch, <a href="/A000084/a000084_2.pdf">Series-parallel networks</a>, July 7, 2003. [Cached copy, with permission of the author]
%H Steven R. Finch, <a href="https://doi.org/10.1017/9781316997741">Mathematical Constants II</a>, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
%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 JiSun Huh and Seonjeong Park, <a href="https://arxiv.org/abs/2204.00214">Toric varieties of Schröder type</a>, arXiv:2204.00214 [math.AG], 2022. (Table 1)
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=44">Encyclopedia of Combinatorial Structures 44</a> [broken link].
%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, and 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 and 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="https://doi.org/10.1007/BF02392410">The blossoming of Schröder's fourth problem</a>, Acta Math., 137 (1976), 1-16. (page 6)
%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, and 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
%F Consider a nontrivial partition p of n. For each size s of a part occurring in p, compute binomial(a(s)+m-1, m) where m is the multiplicity of s. Take the product of this expression over all s. Take the sum of this new expression over all p to obtain a(n). - _Thomas Anton_, Nov 22 2018
%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 b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[a[i]+j-1, j]* b[n-i*j, i-1], {j, 0, n/i}]]];
%t a[n_] := If[n<2, n, b[n, n-1]];
%t Array[a, 40] (* _Jean-François Alcover_, Jan 08 2021, after _Alois P. Heinz_ *)
%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 */
%o (Sage)
%o from collections import Counter
%o def A000669_list(n):
%o list = [1] + [0] * (n - 1)
%o for i in range(1, n):
%o for p in Partitions(i + 1, min_length=2):
%o m = Counter(p)
%o list[i] += prod(binomial(list[s - 1] + m[s] - 1, m[s]) for s in m)
%o return list
%o print(A000669_list(20)) # _M. Eren Kesim_, Jun 21 2021
%Y Equals (1/2)*A000084 for n >= 2.
%Y Cf. A000055, A000311, A001678, A007827, A363064.
%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_ and _John Riordan_
%E Sequence crossreference fixed by _Sean A. Irvine_, Sep 15 2009
|
