A292086 -id:A292086 - cp's OEIS frontend

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.

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

N. J. A. Sloane and John Riordan

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

			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

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

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.
Vlady Ravelomanana and Loys Thimonier, Asymptotic enumeration of cographs, Electronic Notes in Discrete Mathematics, Volume 7, April 2001, pp. 58-61, Theorem 4.
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.
Wei Wang and Ximei Huang, Almost all cographs have a cospectral mate, arXiv:2507.16730 [math.CO], 2025. See pp. 6, 8.
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

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.

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

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

{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 */

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

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... [Ravelomanana and Thimonier, 2001]. - 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

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

A292085 Number A(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 2, 0, 1, 1, 2, 4, 3, 0, 1, 1, 2, 5, 9, 6, 0, 1, 1, 2, 5, 11, 23, 11, 0, 1, 1, 2, 5, 12, 30, 58, 23, 0, 1, 1, 2, 5, 12, 32, 80, 156, 46, 0, 1, 1, 2, 5, 12, 33, 87, 228, 426, 98, 0, 1, 1, 2, 5, 12, 33, 89, 251, 656, 1194, 207, 0

Offset: 1

Alois P. Heinz, Sep 08 2017

			:               T(4,3) = 4             :
:                                      :
:       o       o         o       o    :
:      / \     / \       / \     /|\   :
:     o   N   o   o     o   N   o N N  :
:    / \     ( ) ( )   /|\     ( )     :
:   o   N    N N N N  N N N    N N     :
:  ( )                                 :
:  N N                                 :
:                                      :
Square array A(n,k) begins:
  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   2,   2,   2,   2,   2,   2, ...
  0,  2,   4,   5,   5,   5,   5,   5, ...
  0,  3,   9,  11,  12,  12,  12,  12, ...
  0,  6,  23,  30,  32,  33,  33,  33, ...
  0, 11,  58,  80,  87,  89,  90,  90, ...
  0, 23, 156, 228, 251, 258, 260, 261, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to rooted trees

Columns k=1-10 give: A063524, A001190, A268172, A292210, A292211, A292212, A292213, A292214, A292215, A292216.
Main diagonal gives A000669.
Cf. A244372, A288942, A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n

b[n_, i_, v_, k_] := b[n, i, v, k] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[v == n, 1, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, v - j, k], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n < 2, n, Sum[b[n, n + 1 - j, j, k], {j, 2, Min[n, k]}]];
Table[Table[A[n, 1 + d - n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

A(n,k) = Sum_{j=1..k} A292086(n,j).

A292087 Limit of the number of (unlabeled) rooted trees without unary nodes where n is the difference between the number of leafs and the maximal outdegree as the tree size increases.

Original entry on oeis.org

1, 2, 7, 23, 78, 262, 893, 3040, 10411, 35724, 122950, 424004, 1465254, 5071981, 17584226, 61046464, 212197118, 738422362, 2572261241, 8968726829, 31298189180, 109307655964, 382031357974, 1336107044159, 4675807680776, 16372936282017, 57363325974309

Offset: 0

Alois P. Heinz, Sep 08 2017

nonn

			: a(0) = 1:
:                  o
:               //( )\\
:             N N N N N N
:
: a(1) = 2:
:             o               o
:           /   \          / /|\ \
:          o     N        o N N N N
:       / /|\ \          ( )
:      N N N N N         N N
:
: a(2) = 7:
:           o             o            o             o
:          / \          /   \        /( )\         / | \
:         o   N        o     N      o N N N       o  N  N
:        / \         /( )\         / \          /( )\
:       o   N       o N N N       o   N        N N N N
:     /( )\        ( )           ( )
:    N N N N       N N           N N
:
:          o            o              o
:        /   \        /( )\         / ( \ \
:       o     o      o N N N      o   o  N N
:     /( )\  ( )    /|\          ( ) ( )
:    N N N N N N   N N N         N N N N
:

Alois P. Heinz, Table of n, a(n) for n = 0..100
Index entries for sequences related to rooted trees

Limit of reversed rows of A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(2*n+3, n+3)-A(2*n+3, n+2):
seq(a(n), n=0..23);

b[n_, i_, v_, k_] := b[n, i, v, k] = If[n == 0,
    If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0,
    If[v == n, 1, Sum[Binomial[A[i, k] + j - 1, j]*
    b[n - i*j, i - 1, v - j, k], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n < 2, n,
    Sum[b[n, n + 1 - j, j, k], {j, 2, Min[n, k]}]];
a[n_] := A[2*n + 3, n + 3] - A[2*n + 3, n + 2];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Feb 28 2024, after Alois P. Heinz *)

A292229 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals three.

Original entry on oeis.org

1, 2, 6, 17, 47, 133, 380, 1096, 3186, 9351, 27618, 82168, 245882, 740003, 2238186, 6801375, 20754977, 63583715, 195486605, 603003882, 1865692570, 5788676649, 18007192835, 56151236196, 175486946089, 549586009252, 1724530420457, 5421195811358, 17070958403725

Offset: 3

Alois P. Heinz, Sep 12 2017

nonn

			: a(5) = 6:
:        o        o        o        o          o         o
:       / \      / \      /|\     /   \       /|\      / | \
:      o   N    o   N    o N N   o     o     o N N   o   o  N
:     / \      /|\      / \     /|\   ( )   /|\     ( ) ( )
:    o   N    o N N    o   N   N N N  N N  N N N    N N N N
:   /|\      ( )      ( )
:  N N N     N N      N N
:

Alois P. Heinz, Table of n, a(n) for n = 3..1000
Index entries for sequences related to rooted trees

Column k=3 of A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, 3)-A(n, 2):
seq(a(n), n=3..35);

A292230 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals four.

Original entry on oeis.org

1, 2, 7, 22, 72, 230, 751, 2442, 8006, 26280, 86604, 285994, 946866, 3140812, 10438300, 34747649, 115849084, 386779317, 1292998720, 4327654320, 14500841169, 48639319376, 163308287353, 548820437392, 1845999502151, 6214297279692, 20935992503127, 70586182742450

Offset: 4

Alois P. Heinz, Sep 12 2017

nonn

			: a(6) = 7:
:           o             o            o             o
:          / \          /   \        /( )\         / | \
:         o   N        o     N      o N N N       o  N  N
:        / \         /( )\         / \          /( )\
:       o   N       o N N N       o   N        N N N N
:     /( )\        ( )           ( )
:    N N N N       N N           N N
:
:          o            o              o
:        /   \        /( )\         / ( \ \
:       o     o      o N N N      o   o  N N
:     /( )\  ( )    /|\          ( ) ( )
:    N N N N N N   N N N         N N N N
:

Alois P. Heinz, Table of n, a(n) for n = 4..1000
Index entries for sequences related to rooted trees

Column k=4 of A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, 4)-A(n, 3):
seq(a(n), n=4..35);

A292231 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals five.

Original entry on oeis.org

1, 2, 7, 23, 77, 256, 861, 2897, 9800, 33232, 113012, 385165, 1315434, 4500398, 15421463, 52919299, 181826880, 625467087, 2153816295, 7423887771, 25611710370, 88430103927, 305555059139, 1056532822348, 3655607694207, 12656112780583, 43841784746311

Offset: 5

Alois P. Heinz, Sep 12 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 5..1000
Index entries for sequences related to rooted trees

Column k=5 of A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, 5)-A(n, 4):
seq(a(n), n=5..35);

A292232 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals six.

Original entry on oeis.org

1, 2, 7, 23, 78, 261, 887, 3008, 10268, 35112, 120445, 413979, 1425919, 4919635, 17000553, 58828575, 203826882, 707008418, 2454916048, 8532126320, 29679297122, 103322632386, 359962092302, 1254914172463, 4377704183644, 15280415561913, 53365850603107

Offset: 6

Alois P. Heinz, Sep 12 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 6..1000
Index entries for sequences related to rooted trees

Column k=6 of A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, 6)-A(n, 5):
seq(a(n), n=6..35);

A292233 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals seven.

Original entry on oeis.org

1, 2, 7, 23, 78, 262, 892, 3034, 10379, 35581, 122338, 421498, 1455216, 5032559, 17431384, 60460263, 209967105, 729996715, 2540602259, 8850326207, 30857134567, 107670278671, 375970664930, 1313731592633, 4593388008873, 16069958896737, 56251584472388

Offset: 7

Alois P. Heinz, Sep 12 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..1000
Index entries for sequences related to rooted trees

Column k=7 of A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, 7)-A(n, 6):
seq(a(n), n=7..35);

A292234 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals eight.

Original entry on oeis.org

1, 2, 7, 23, 78, 262, 893, 3039, 10405, 35692, 122807, 423392, 1462748, 5061942, 17544791, 60893535, 211610421, 736189821, 2563823467, 8937012397, 31179543205, 108865543805, 380389514123, 1330027798273, 4653356214277, 16290208735442, 57059113819218

Offset: 8

Alois P. Heinz, Sep 12 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 8..1000
Index entries for sequences related to rooted trees

Column k=8 of A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, 8)-A(n, 7):
seq(a(n), n=8..35);

A292235 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals nine.

Original entry on oeis.org

1, 2, 7, 23, 78, 262, 893, 3040, 10410, 35718, 122918, 423861, 1464642, 5069475, 17574187, 61007028, 212044176, 737835578, 2570028204, 8960286527, 31266462620, 109188954531, 381589000393, 1334464142298, 4669723965497, 16350466246944, 57280522330579

Offset: 9

Alois P. Heinz, Sep 12 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 9..1000
Index entries for sequences related to rooted trees

Column k=9 of A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, 9)-A(n, 8):
seq(a(n), n=9..40);

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A292085 Number A(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A292087 Limit of the number of (unlabeled) rooted trees without unary nodes where n is the difference between the number of leafs and the maximal outdegree as the tree size increases.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A292229 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals three.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A292230 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals four.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A292231 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals five.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A292232 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals six.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A292233 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that the maximum of the node outdegrees equals seven.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple