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

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

Also called "hierarchies" by Genitrini (2016). - N. J. A. Sloane, Mar 24 2017

References

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)

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

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

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.

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

Links

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

Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, and Martin Leuner, On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture, arXiv:1907.01073 [math.CO], 2019.

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

Peter J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See pp. 155, 162, 165, 172. - N. J. A. Sloane, Apr 18 2014

Peter 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.

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, and Mingxian Zhong, Obstructions for three-coloring graphs without induced paths on six vertices, arXiv preprint arXiv:1504.06979 [math.CO], 2015-2018.

Steven R. Finch, Series-parallel networks

Steven R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]

Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.

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

A. Genitrini, Full asymptotic expansion for Polya structures, arXiv:1605.00837 [math.CO], May 03 2016, p. 9.

O. Golinelli, Asymptotic behavior of two-terminal series-parallel networks, arXiv:cond-mat/9707023 [cond-mat.stat-mech], 1997.

JiSun Huh and Seonjeong Park, Toric varieties of Schröder type, arXiv:2204.00214 [math.AG], 2022. (Table 1)

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 44 [broken link].

V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From N. J. A. Sloane, Dec 22 2012

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.

Arnau Mir, Francesc Rossello, and Lucia Rotger, Sound Colless-like balance indices for multifurcating trees, arXiv:1805.01329 [q-bio.PE], 2018.

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

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

J. Riordan, The blossoming of Schröder's fourth problem, Acta Math., 137 (1976), 1-16. (page 6)

J. Riordan, Letter to N. J. A. Sloane, Sep. 1970

J. Riordan, Letter to N. J. A. Sloane, Nov 10 1970

Audace Amen Vioutou Dossou-Olory, and Stephan Wagner, Inducibility of Topological Trees, arXiv:1802.06696 [math.CO], 2018.

Audace Amen Vioutou Dossou-Olory, The topological trees with extremal Matula numbers, arXiv:1806.03995 [math.CO], 2018.

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

Formula

Product_{k>0} 1/(1-x^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

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

Example

G.f. = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 33*x^6 + 90*x^7 + 261*x^8 + ...
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

Maple

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];
# Method 3:
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(a(i)+j-1, j)*
       b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n, n-1)):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 28 2016

Mathematica

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}]]];
a[n_] := If[n<2, n, b[n, n-1]];
Array[a, 40] (* Jean-François Alcover, Jan 08 2021, after Alois P. Heinz *)

Prog

(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 */
(Sage)
from collections import Counter
def A000669_list(n):
    list = [1] + [0] * (n - 1)
    for i in range(1, n):
        for p in Partitions(i + 1, min_length=2):
            m = Counter(p)
            list[i] += prod(binomial(list[s - 1] + m[s] - 1, m[s]) for s in m)
    return list
print(A000669_list(20)) # M. Eren Kesim, Jun 21 2021

Crossrefs

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

Cf. A000055, A000311, A001678, A007827, A363064.

Cf. A000311, labeled hierarchies on n points.

Column 1 of A319254.

Main diagonal of A292085.

Row sums of A292086.

Sequence in context: A292214 A292215 A292216 * A295461 A191769 A221206

Adjacent sequences: A000666 A000667 A000668 * A000670 A000671 A000672

Keyword

nonn,nice,easy,changed

Author

N. J. A. Sloane and John Riordan

Extensions

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

Status

approved