login
The OEIS is supported by the many generous donors 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)
144
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
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
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.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72
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.
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)
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
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. 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
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
Sequence crossreference fixed by Sean A. Irvine, Sep 15 2009
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)