A005640 -id:A005640 - cp's OEIS frontend

A000311 Schroeder's fourth problem; also series-reduced rooted trees with n labeled leaves; also number of total partitions of n.

0, 1, 1, 4, 26, 236, 2752, 39208, 660032, 12818912, 282137824, 6939897856, 188666182784, 5617349020544, 181790703209728, 6353726042486272, 238513970965257728, 9571020586419012608, 408837905660444010496, 18522305410364986906624

Offset: 0

N. J. A. Sloane

a(n) is the number of labeled series-reduced rooted trees with n leaves (root has degree 0 or >= 2); a(n-1) = number of labeled series-reduced trees with n leaves. Also number of series-parallel networks with n labeled edges, divided by 2.
A total partition of n is essentially what is meant by the first part of the previous line: take the numbers 12...n, and partition them into at least two blocks. Partition each block with at least 2 elements into at least two blocks. Repeat until only blocks of size 1 remain. (See the reference to Stanley, Vol. 2.) - N. J. A. Sloane, Aug 03 2016
Polynomials with coefficients in triangle A008517, evaluated at 2. - Ralf Stephan, Dec 13 2004
Row sums of unsigned A134685. - Tom Copeland, Oct 11 2008
Row sums of A134991, which contains an e.g.f. for this sequence and its compositional inverse. - Tom Copeland, Jan 24 2018
From Gus Wiseman, Dec 28 2019: (Start)
Also the number of singleton-reduced phylogenetic trees with n labels. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) nonempty sets. It is singleton-reduced if no non-leaf node covers only singleton branches. For example, the a(4) = 26 trees are:
  {1,2,3,4}  {{1},{2},{3,4}}  {{1},{2,3,4}}
             {{1},{2,3},{4}}  {{1,2},{3,4}}
             {{1,2},{3},{4}}  {{1,2,3},{4}}
             {{1},{2,4},{3}}  {{1,2,4},{3}}
             {{1,3},{2},{4}}  {{1,3},{2,4}}
             {{1,4},{2},{3}}  {{1,3,4},{2}}
                              {{1,4},{2,3}}
                              {{{1},{2,3}},{4}}
                              {{{1,2},{3}},{4}}
                              {{1},{{2},{3,4}}}
                              {{1},{{2,3},{4}}}
                              {{{1},{2,4}},{3}}
                              {{{1,2},{4}},{3}}
                              {{1},{{2,4},{3}}}
                              {{{1,3},{2}},{4}}
                              {{{1},{3,4}},{2}}
                              {{{1,3},{4}},{2}}
                              {{{1,4},{2}},{3}}
                              {{{1,4},{3}},{2}}
(End)

			E.g.f.: A(x) = x + x^2/2! + 4*x^3/3! + 26*x^4/4! + 236*x^5/5! + 2752*x^6/6! + ...
where exp(A(x)) = 1 - x + 2*A(x), and thus
Series_Reversion(A(x)) = x - x^2/2! - x^3/3! - x^4/4! - x^5/5! - x^6/6! + ...
O.g.f.: G(x) = x + x^2 + 4*x^3 + 26*x^4 + 236*x^5 + 2752*x^6 + 39208*x^7 + ...
where
G(x) = x/2 + x/(2*(2-x)) + x/(2*(2-x)*(2-2*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)*(2-4*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)*(2-4*x)*(2-5*x)) + ...
From _Gus Wiseman_, Dec 28 2019: (Start)
A rooted tree is series-reduced if it has no unary branchings, so every non-leaf node covers at least two other nodes. The a(4) = 26 series-reduced rooted trees with 4 labeled leaves are the following. Each bracket (...) corresponds to a non-leaf node.
  (1234)  ((12)34)  ((123)4)
          (1(23)4)  (1(234))
          (12(34))  ((124)3)
          (1(24)3)  ((134)2)
          ((13)24)  (((12)3)4)
          ((14)23)  ((1(23))4)
                    ((12)(34))
                    (1((23)4))
                    (1(2(34)))
                    (((12)4)3)
                    ((1(24))3)
                    (1((24)3))
                    (((13)2)4)
                    ((13)(24))
                    (((13)4)2)
                    ((1(34))2)
                    (((14)2)3)
                    ((14)(23))
                    (((14)3)2)
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 224.
J. Felsenstein, Inferring phyogenies, Sinauer Associates, 2004; see p. 25ff.
L. R. Foulds and R. W. Robinson, Enumeration of phylogenetic trees without points of degree two. Ars Combin. 17 (1984), A, 169-183. Math. Rev. 85f:05045
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 197.
E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see "total partitions", Example 5.2.5, Equation (5.27), and also Fig. 5-3 on page 14. See also the Notes on page 66.

N. J. A. Sloane, Table of n, a(n) for n = 0..375 [Shortened file because terms grow rapidly: see Sloane link below for additional terms]
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.
Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, Mickaël Maazoun, and Adeline Pierrot, Random cographs: Brownian graphon limit and asymptotic degree distribution, arXiv:1907.08517 [math.CO], 2019.
Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024. See p. 58.
A. Blass, N. Dobrinen, and D. Raghavan, The next best thing to a P-point, arXiv preprint arXiv:1308.3790 [math.LO], 2013.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See p. 155 and 159.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
L. Carlitz and J. Riordan, The number of labeled two-terminal series-parallel networks, Duke Math. J. 23 (1956), 435-445 (the sequence called {A_n}).
Tom Copeland, Comments on A000311
Brian Drake, Ira M. Gessel, and Guoce Xin, Three Proofs and a Generalization of the Goulden-Litsyn-Shevelev Conjecture on a Sequence Arising in Algebraic Geometry, J. of Integer Sequences, Vol. 10 (2007), Article 07.3.7
John Engbers, David Galvin, and Clifford Smyth, Restricted Stirling and Lah numbers and their inverses, arXiv:1610.05803 [math.CO], 2016.
J. Felsenstein, The number of evolutionary trees, Systematic Zoology, 27 (1978), 27-33. (Annotated scanned copy)
J. Felsenstein, The number of evolutionary trees, Systematic Biology, 27 (1978), pp. 27-33, 1978.
S. 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 129
Daniel L. Geisler, Combinatorics of Iterated Functions
M. D. Hendy, C. H. C. Little, David Penny, Comparing trees with pendant vertices labelled, SIAM J. Appl. Math. 44 (5) (1984) Table 1
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 69
D. Jackson, A. Kempf, and A. Morales, A robust generalization of the Legendre transform for QFT, arXiv:1612.0046 [hep-th], 2017.
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.
B. R. Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
Vladimir V. Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.
Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.
Shi-Mei Ma, Jun-Ying Liu, Jean Yeh, and Yeong-Nan Yeh, Eulerian-type polynomials over Stirling permutations and box sorting algorithm, arXiv:2506.16438 [math.CO], 2025. See p. 5.
Dragan Mašulović, Big Ramsey spectra of countable chains, arXiv:1912.03022 [math.CO], 2019.
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.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
F. Murtagh, Counting dendrograms: a survey, Discrete Appl. Math., 7 (1984), 191-199.
Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.
P. Regner, Phylogenetic Trees: Selected Combinatorial Problems, Master's Thesis, 2012, Institute of Discrete Mathematics and Geometry, TU Vienna, pp. 50-59.
J. Riordan, Letter to N. J. A. Sloane, Jul. 1970
J. Riordan, The blossoming of Schröder's fourth problem, Acta Math., 137 (1976), 1-16.
E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]
N. J. A. Sloane, Table of n, a(n) for n = 0..500
J. Taylor, Formal group laws and hypergraph colorings, doctoral thesis, Univ. of Wash., 2016, p. 95. [_Tom Copeland_, Dec 20 2018]
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See pp. 2, 12.
Index entries for sequences related to trees
Index entries for sequences related to rooted trees
Index entries for "core" sequences
Index entries for sequences mentioned in Moon (1987)
Index entries for sequences related to parenthesizing

Row sums of A064060 and A134991.
The unlabeled version is A000669.
Unlabeled phylogenetic trees are A141268.
The node-counting version is A060356, with unlabeled version A001678.
Phylogenetic trees with n labels are A005804.
Chains of set partitions are A005121, with maximal version A002846.
Inequivalent leaf-colorings of series-reduced rooted trees are A318231.
Cf. A001003, A007827, A005805, A006351, A000084.
For n >= 2, A000311(n) = A006351(n)/2 = A005640(n)/2^(n+1).
Cf. A000110, A000669 = unlabeled hierarchies, A119649.
Cf. A000670, A135494, A134685.
Cf. A048816, A196545, A213427, A316651, A316652, A330626, A330627.
Cf. A000169, A042977, A133314, A134685, A269939.

M:=499; a:=array(0..500); a[0]:=0; a[1]:=1; a[2]:=1; for n from 0 to 2 do lprint(n,a[n]); od: for n from 2 to M do a[n+1]:=(n+2)*a[n]+2*add(binomial(n,k)*a[k]*a[n-k+1],k=2..n-1); lprint(n+1,a[n+1]); od:
Order := 50; t1 := solve(series((exp(A)-2*A-1),A)=-x,A); A000311 := n-> n!*coeff(t1,x,n);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(combinat[multinomial](n, n-i*j, i$j)/j!*
      a(i)^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=0..40);  # Alois P. Heinz, Jan 28 2016
# faster program:
b:= proc(n, i) option remember;
    `if`(i=0 and n=0, 1, `if`(i<=0 or i>n, 0,
    i*b(n-1, i) + (n+i-1)*b(n-1, i-1))) end:
a:= n -> `if`(n<2, n, add(b(n-1, i), i=0..n-1)):
seq(a(n), n=0..40);  # Peter Luschny, Feb 15 2021

nn = 19; CoefficientList[ InverseSeries[ Series[1+2a-E^a, {a, 0, nn}], x], x]*Range[0, nn]! (* Jean-François Alcover, Jul 21 2011 *)
a[ n_] := If[ n < 1, 0, n! SeriesCoefficient[ InverseSeries[ Series[ 1 + 2 x - Exp[x], {x, 0, n}]], n]]; (* Michael Somos, Jun 04 2012 *)
a[n_] := (If[n < 2,n,(column = ConstantArray[0, n - 1]; column[[1]] = 1; For[j = 3, j <= n, j++, column = column * Flatten[{Range[j - 2], ConstantArray[0, (n - j) + 1]}] + Drop[Prepend[column, 0], -1] * Flatten[{Range[j - 1, 2*j - 3], ConstantArray[0, n - j]}];]; Sum[column[[i]], {i, n - 1}]  )]); Table[a[n], {n, 0, 20}] (* Peter Regner, Oct 05 2012, after a formula by Felsenstein (1978) *)
multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&,j]]]/j!*a[i]^j *b[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := If[n<2, n, b[n, n-1]]; Table[ a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 07 2016, after Alois P. Heinz *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[sps[m],1Gus Wiseman, Dec 28 2019 *)
(* Lengthy but easy to follow *)
  lead[, n /; n < 3] := 0
  lead[h_, n_] := Module[{p, i},
        p = Position[h, {_}];
        Sum[MapAt[{#, n} &, h, p[[i]]], {i, Length[p]}]
        ]
  follow[h_, n_] := Module[{r, i},
        r = Replace[Position[h, {_}], {a__} -> {a, -1}, 1];
        Sum[Insert[h, n, r[[i]]], {i, Length[r]}]
        ]
  marry[, n /; n < 3] := 0
  marry[h_, n_] := Module[{p, i},
        p = Position[h, _Integer];
        Sum[MapAt[{#, n} &, h, p[[i]]], {i, Length[p]}]
        ]
  extend[a_ + b_, n_] := extend[a, n] + extend[b, n]
  extend[a_, n_] := lead[a, n] + follow[a, n] + marry[a, n]
  hierarchies[1] := hierarchies[1] = extend[hier[{}], 1]
  hierarchies[n_] := hierarchies[n] = extend[hierarchies[n - 1], n] (* Daniel Geisler, Aug 22 2022 *)

a(n):=if n=1 then 1 else sum((n+k-1)!*sum(1/(k-j)!*sum((2^i*(-1)^(i)*stirling2(n+j-i-1,j-i))/((n+j-i-1)!*i!),i,0,j),j,1,k),k,1,n-1); /* Vladimir Kruchinin, Jan 28 2012 */

{a(n) = local(A); if( n<0, 0, for( i=1, n, A = Pol(exp(A + x * O(x^i)) - A + x - 1)); n! * polcoeff(A, n))}; /* Michael Somos, Jan 15 2004 */

{a(n) = my(A); if( n<0, 0, A = O(x); for( i=1, n, A = intformal( 1 / (1 + x - 2*A))); n! * polcoeff(A, n))}; /* Michael Somos, Oct 25 2014 */

{a(n) = n! * polcoeff(serreverse(1+2*x - exp(x +x^2*O(x^n))), n)}
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Oct 27 2014

\p100 \\ set precision
{A=Vec(sum(n=0, 600, 1.*x/prod(k=0, n, 2 - k*x + O(x^31))))}
for(n=0, 25, print1(if(n<1,0,round(A[n])),", ")) \\ Paul D. Hanna, Oct 27 2014

from functools import lru_cache
from math import comb
@lru_cache(maxsize=None)
def A000311(n): return n if n <= 1 else -(n-1)*A000311(n-1)+comb(n,m:=n+1>>1)*(0 if n&1 else A000311(m)**2) + (sum(comb(n,i)*A000311(i)*A000311(n-i) for i in range(1,m))<<1) # Chai Wah Wu, Nov 10 2022

E.g.f. A(x) satisfies exp A(x) = 2*A(x) - x + 1.
a(0)=0, a(1)=a(2)=1; for n >= 2, a(n+1) = (n+2)*a(n) + 2*Sum_{k=2..n-1} binomial(n, k)*a(k)*a(n-k+1).
a(1)=1; for n>1, a(n) = -(n-1) * a(n-1) + Sum_{k=1..n-1} binomial(n, k) * a(k) * a(n-k). - Michael Somos, Jun 04 2012
From the umbral operator L in A135494 acting on x^n comes, umbrally, (a(.) + x)^n = (n * x^(n-1) / 2) - (x^n / 2) + Sum_{j>=1} j^(j-1) * (2^(-j) / j!) * exp(-j/2) * (x + j/2)^n giving a(n) = 2^(-n) * Sum_{j>=1} j^(n-1) * ((j/2) * exp(-1/2))^j / j! for n > 1. - Tom Copeland, Feb 11 2008
Let h(x) = 1/(2-exp(x)), an e.g.f. for A000670, then the n-th term of A000311 is given by ((h(x)*d/dx)^n)x evaluated at x=0, i.e., A(x) = exp(x*a(.)) = exp(x*h(u)*d/du) u evaluated at u=0. Also, dA(x)/dx = h(A(x)). - Tom Copeland, Sep 05 2011 (The autonomous differential eqn. here is also on p. 59 of Jones. - Tom Copeland, Dec 16 2019)
A134991 gives (b.+c.)^n = 0^n, for (b_n)=A000311(n+1) and (c_0)=1, (c_1)=-1, and (c_n)=-2* A000311(n) = -A006351(n) otherwise. E.g., umbrally, (b.+c.)^2 = b_2*c_0 + 2 b_1*c_1 + b_0*c_2 =0. - Tom Copeland, Oct 19 2011
a(n) = Sum_{k=1..n-1} (n+k-1)!*Sum_{j=1..k} (1/(k-j)!)*Sum_{i=0..j} 2^i*(-1)^i*Stirling2(n+j-i-1, j-i)/((n+j-i-1)!*i!), n>1, a(0)=0, a(1)=1. - Vladimir Kruchinin, Jan 28 2012
Using L. Comtet's identity and D. Wasserman's explicit formula for the associated Stirling numbers of second kind (A008299) one gets: a(n) = Sum_{m=1..n-1} Sum_{i=0..m} (-1)^i * binomial(n+m-1,i) * Sum_{j=0..m-i} (-1)^j * ((m-i-j)^(n+m-1-i))/(j! * (m-i-j)!). - Peter Regner, Oct 08 2012
G.f.: x/Q(0), where Q(k) = 1 - k*x - x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
G.f.: x*Q(0), where Q(k) = 1 - x*(k+1)/(x*(k+1) - (1-k*x)*(1-x-k*x)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 11 2013
a(n) ~ n^(n-1) / (sqrt(2) * exp(n) * (2*log(2)-1)^(n-1/2)). - Vaclav Kotesovec, Jan 05 2014
E.g.f. A(x) satisfies d/dx A(x) = 1 / (1 + x - 2 * A(x)). - Michael Somos, Oct 25 2014
O.g.f.: Sum_{n>=0} x / Product_{k=0..n} (2 - k*x). - Paul D. Hanna, Oct 27 2014
E.g.f.: (x - 1 - 2 LambertW(-exp((x-1)/2) / 2)) / 2. - Vladimir Reshetnikov, Oct 16 2015 (This e.g.f. is given in A135494, the entry alluded to in my 2008 formula, and in A134991 along with its compositional inverse. - Tom Copeland, Jan 24 2018)
a(0) = 0, a(1) = 1; a(n) = n! * [x^n] exp(Sum_{k=1..n-1} a(k)*x^k/k!). - Ilya Gutkovskiy, Oct 17 2017
a(n+1) = Sum_{k=0..n} A269939(n, k) for n >= 1. - Peter Luschny, Feb 15 2021

Name edited by Gus Wiseman, Dec 28 2019

A006351 Number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon.

Original entry on oeis.org

1, 2, 8, 52, 472, 5504, 78416, 1320064, 25637824, 564275648, 13879795712, 377332365568, 11234698041088, 363581406419456, 12707452084972544, 477027941930515456, 19142041172838025216, 817675811320888020992, 37044610820729973813248, 1774189422608238694776832

Offset: 1

N. J. A. Sloane

For a simple relationship to series-reduced rooted trees, partitions of n, and phylogenetic trees among other combinatoric constructs, see comments in A000311. - Tom Copeland, Jan 06 2021

			D^3(1) = (12*x^2+56*x+52)/(x-1)^6. Evaluated at x = 0 this gives a(4) = 52.
a(3) = 8: The 8 possible increasing plane trees on 3 vertices with vertices of outdegree k >= 1 coming in 2 colors, B or W, are
.......................................................
.1B..1B..1W..1W.....1B.......1W........1B........1W....
.|...|...|...|...../.\....../..\....../..\....../..\...
.2B..2W..2B..2W...2...3....2....3....3....2....3....2..
.|...|...|...|.........................................
.3...3...3...3.........................................
G.f. = x + 2*x^2 + 8*x^3 + 52*x^4 + 472*x^5 + 5504*x^6 + 78416*x^7 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
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.
P. A. MacMahon, The combination of resistances, The Electrician, 28 (1892), 601-602; reprinted in Coll. Papers I, pp. 617-619.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.40(a), S(x).

Alois P. Heinz, Table of n, a(n) for n = 1..200
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024. See p. 58.
Peter J. Cameron, Counting two-graphs related to trees, Elec. J. Combin., Vol. 2, #R4. [From _Aaron Meyerowitz_, Sep 30 2010]
Frédéric Chapoton, Florent Hivert, and Jean-Christophe Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013
Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052 [math.CA], 2005.
Brian Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.5.1 ), Ph. D. dissertation, Brandeis Univ., 2008.
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.
ISCGI, Cograph graphs
Song He, Fei Teng, and Yong Zhang, String Correlators: Recursive Expansion, Integration-by-Parts and Scattering Equations, arXiv:1907.06041 [hep-th], 2019. Also in Journal of High Energy Physics (2019), 2019:85.
Walter Knödel, Über Zerfällungen, Monatsh. Math., 55 (1951), 20-27.
Vladimir Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.
Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.
Michael D. Moffitt, Search Strategies for Topological Network Optimization, Proceedings of the AAAI Conference on Artificial Intelligence, 36(9) (2022), 10299-10308.
John W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226 (the e.g.f. U(x)).
N. J. A. Sloane, Transforms
Index entries for reversions of series
Index entries for sequences mentioned in Moon (1987)
Index entries for sequences related to trees [From _Aaron Meyerowitz_, Sep 30 2010]

Cf. A000311, A000084 (for unlabeled case), A032188. A140945.

Cf. A133314, A134991, A135494.

read transforms; t1 := 2*ln(1+x)-x; t2 := series(t1,x,10); t3 := seriestoseries(t2,'revogf'); t4 := SERIESTOLISTMULT(%);
# N denotes all series-parallel networks, S = series networks, P = parallel networks;
spec := [ N, N=Union(Z,S,P),S=Set(Union(Z,P),card>=2), P=Set(Union(Z,S), card>=2)}, labeled ]: A006351 := n->combstruct[count](spec,size=n);
A006351 := n -> add(combinat[eulerian2](n-1,k)*2^(n-k-1),k=0..n-1):
seq(A006351(n), n=1..18); # Peter Luschny, Nov 16 2012

max = 18; f[x_] := 2*Log[1+x]-x; Rest[ CoefficientList[ InverseSeries[ Series[ f[x], {x, 0, max}], x], x]]*Range[max]! (* Jean-François Alcover, Nov 25 2011 *)

a(n):=if n=1 then 1 else ((n-1)!*sum(binomial(n+k-1,n-1)* sum((-1)^(j)*binomial(k,j)*sum((binomial(j,l)*(j-l)!*2^(j-l)*(-1)^l* stirling1(n-l+j-1,j-l))/(n-l+j-1)!,l,0,j),j,1,k),k,1,n-1)); /* Vladimir Kruchinin, Jan 24 2012 */

x='x+O('x^66); Vec(serlaplace(serreverse( 2*log(1+x) - 1*x ))) \\ Joerg Arndt, May 01 2013

# uses[eulerian2 from A201637]
def A006351(n): return add(A201637(n-1, k)*2^(n-k-1) for k in (0..n-1))
[A006351(n) for n in (1..18)]  # Peter Luschny, Nov 16 2012

For n >= 2, A006351(n) = 2*A000311(n) = A005640(n)/2^n. Row sums of A140945.
E.g.f. is reversion of 2*log(1+x)-x.
Also exponential transform of A000311, define b by 1+sum b_n x^n / n! = exp ( 1 + sum a_n x^n /n!).
E.g.f.: A(x), B(x)=x*A(x) satisfies the differential equation B'(x)=(1+B(x))/(1-B(x)). - Vladimir Kruchinin, Jan 18 2011
From Peter Bala, Sep 05 2011: (Start)
The generating function A(x) satisfies the autonomous differential equation A'(x) = (1+A)/(1-A) with A(0) = 0. Hence the inverse function A^-1(x) = int {t = 0..x} (1-t)/(1+t) = 2*log(1+x)-x, which yields A(x) = -1-2*W(-1/2*exp((x-1)/2)), where W is the Lambert W function.
The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx((1+x)/(1-x)*g(x)). Compare with A032188.
Applying [Bergeron et al., Theorem 1] to the result x = int {t = 0..A(x)} 1/phi(t), where phi(t) = (1+t)/(1-t) = 1 + 2*t + 2*t^2 + 2*t^3 + ..., leads to the following combinatorial interpretation for the sequence: a(n) gives the number of plane increasing trees on n vertices where each vertex of outdegree k >=1 can be in one of 2 colors. An example is given below. (End)
A134991 gives (b.+c.)^n = 0^n , for (b_n)=A000311(n+1) and (c_0)=1, (c_1)=-1, and (c_n)=-2* A000311(n) = -A006351(n) otherwise. E.g., umbrally, (b.+c.)^2 = b_2*c_0 + 2 b_1*c_1 + b_0*c_2 =0. - Tom Copeland, Oct 19 2011
G.f.: 1/S(0) where S(k) = 1 - x*(k+1) - x*(k+1)/S(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 18 2011
a(n) = ((n-1)!*sum(k=1..n-1, C(n+k-1,n-1)*sum(j=1..k, (-1)^(j)*C(k,j)* sum(l=0..j, (C(j,l)*(j-l)!*2^(j-l)*(-1)^l*stirling1(n-l+j-1,j-l))/ (n-l+j-1)!)))), n>1, a(1)=1. - Vladimir Kruchinin, Jan 24 2012
E.g.f.: A(x) = exp(B(x))-1 where B(x) is the e.g.f. of A000311. - Vladimir Kruchinin, Sep 25 2012
a(n) = sum_{k=0..n-1} A201637(n-1,k)*2^(n-k-1). - Peter Luschny, Nov 16 2012
G.f.: -1 + 2/Q(0), where Q(k)= 1 - k*x - x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
a(n) ~ sqrt(2)*n^(n-1)/((2*log(2)-1)^(n-1/2)*exp(n)). - Vaclav Kotesovec, Jul 17 2013
G.f.: Q(0)/(1-x), where Q(k) = 1 - x*(k+1)/( x*(k+1) - (1 -x*(k+1))*(1 -x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 10 2013
a(1) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k). - Ilya Gutkovskiy, Aug 28 2020
Conjecture: a(n) = A379459(n-2,0) = A379460(n-1,0) for n > 1 with a(1) = 1. - Mikhail Kurkov, Jan 16 2025

A005736 Number of degenerate fanout-free Boolean functions of n variables using And, Or and Not gates.

Original entry on oeis.org

0, 2, 6, 32, 314, 4892, 104518, 2814520, 91069042, 3434371508, 147755228670, 7137203824016, 382309275191786, 22484502178536140, 1440083130444110134, 99761235465965943400, 7431676025141300550370, 592372327653418546022756

Offset: 0

N. J. A. Sloane

nonn

J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..200
K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, 27 (1978), 309-318. (Annotated scanned copy)
Index entries for sequences related to Boolean functions

Cf. A005640, A005737, A224766.

a(n) = Sum_{k=0..n-1} binomial(n, k) * s(k) where s(0)=2 and s(n) = A005640(n + 1) otherwise. - Sean A. Irvine, Jul 21 2016

a(n) = A005737(n) - A224766(n). - Andrew Howroyd, Mar 29 2025

More terms from Sean A. Irvine, Jul 21 2016

Name clarified by Andrew Howroyd, Apr 03 2025

A005172 Number of labeled rooted trees of subsets of an n-set.

Original entry on oeis.org

1, 4, 32, 416, 7552, 176128, 5018624, 168968192, 6563282944, 288909131776, 14212910809088, 772776684683264, 46017323176296448, 2978458881388183552, 208198894960190160896, 15631251601179130462208, 1254492810303112820555776, 107174403941451434687463424, 9711022458989438255300083712

Offset: 1

N. J. A. Sloane

Each node is a subset of the labeled set {1,...,n}. If the subset node is empty, it must have at least two children.

John W. Layman observes that this is the Stirling transform of A005264.

			x + 4*x^2 + 32*x^3 + 416*x^4 + 7552*x^5 + 176128*x^6 + 5018624*x^7 + ...
D^3(1) = 32*(12*x^2+28*x+13)/(2*x-1)^6. Evaluated at x = 0 this gives a(4) = 416.
From _Peter Bala_, Sep 06 2011: (Start)
a(3) = 32: The 32 increasing plane trees on 3 vertices with vertices of outdegree k coming in 2^(k+1) colors are
.
           1(x4 colors)      1(x8 colors)      1(x8 colors)
           |                / \               / \
           2(x4 colors)    2   3             3   2
           |
           3
.
  Totals: 16        +        8        +        8     = 32.   (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.26.

T. D. Noe and Vaclav Kotesovec, Table of n, a(n) for n = 1..240 (terms 1..30 from T. D. Noe)
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
F. Chapoton, F. Hivert, and J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052 [math.CA], 2005.
L. R. Foulds and R. W. Robinson, Determining the asymptotic number of phylogenetic trees, pp. 110-126 of Combinatorial Mathematics VII (Newcastle, August 1979), ed. R. W. Robinson, G. W. Southern and W. D. Wallis. Lect. Notes in Math., 829. Springer, 1980.
L. R. Foulds and R. W. Robinson, Determining the asymptotic number of phylogenetic trees, Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.
F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10.
F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10. [Annotated scanned copy]
István Mezo, Victor H. Moll, José L. Ramírez, and Diego Villamizar, On the r-Derangements of type B, arXiv:2103.04151 [math.CO], 2021.
Index entries for sequences related to trees
Index entries for sequences related to rooted trees

Cf. A005640, A032188.

See A225170 for another version.

with(combinat); A005172 := n -> add(eulerian2(n-1,k)*2^(2*n-k-2),k=0..n-1): seq(A005172(n), n=1..16); # Peter Luschny, Nov 10 2012
A005172_list := proc(len) local A, n; A[1] := 1; for n from 2 to len do
A[n] := 2*A[n-1] + add(binomial(n,j)*A[j]*A[n-j], j=1..n-1) od:
convert(A,list) end: A005172_list(19); # Peter Luschny, May 24 2017

max = 16; g[x_] := -1/2 - ProductLog[-E^(-1/2 + x)/2]; Drop[ CoefficientList[ Series[ g[x], {x, 0, max}], x]*Range[0, max]!, 1](* Jean-François Alcover, Nov 17 2011, after 1st e.g.f. *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ -1/2 - ProductLog[ -Exp[ -1/2 + z] / 2], {z, 0, n}]] (* Michael Somos, Jun 07 2012 *)
a[1] = 1; a[n_] := (Sum[(n + k - 1)!*Sum[(-1)^j/(k - j)!*Sum[(-1)^i*2^(n - i + j - 1)*StirlingS1[n - i + j - 1, j - i]/((n - i + j - 1)!*i!), {i, 0, j}], {j, 1, k}], {k, 1, n - 1}]);
Array[a, 20] (* Jean-François Alcover, Jun 24 2018, after Vladimir Kruchinin *)
Eulerian2[n_, k_] := Eulerian2[n, k] = If[k == 0, 1, If[k == n, 0, Eulerian2[n-1, k] (k + 1) + Eulerian2[n - 1, k - 1] (2n - k - 1)]]; A005172[n_] := Sum[Eulerian2[n - 1, k] 2^(2 n - k - 2), {k, 0, n - 1}]; Table[A005172[n], {n, 19}] (* Peter Luschny, Jun 24 2018 *)

a(n):=if n=1 then 1 else (sum((n+k-1)!*sum((-1)^j/(k-j)!*sum((-1)^i*2^(n-i+j-1)*stirling1(n-i+j-1,j-i)/((n-i+j-1)!*i!),i,0,j),j,1,k),k,1,n-1)); /* Vladimir Kruchinin, Jan 30 2012 */

{a(n)=local(A=1+x);for(i=0,n,A=1+intformal(A*(1+A+x*O(x^n))^2));n!*polcoeff(A,n)} \\ Paul D. Hanna, Sep 06 2008

N=66; x='x+O('x^N);
Q(k)=if(k>N,1,1-2*(k+1)*x-2*x*(k+1)/Q(k+1));
gf=1/Q(0);  Vec(gf) \\ Joerg Arndt, May 01 2013

@CachedFunction
def eulerian2(n, k):
    if k==0: return 1
    elif k==n: return 0
    return eulerian2(n-1, k)*(k+1)+eulerian2(n-1, k-1)*(2*n-k-1)
A005172 = lambda n: add(eulerian2(n-1,k)*2^(2*n-k-2) for k in (0..n-1))
[A005172(n) for n in (1..16)]  # Peter Luschny, Nov 10 2012

E.g.f.: -1/2 - LambertW ( - exp( -1/2 + x) / 2 ).
E.g.f.: A(x) = 1 + Integral A(x)*(1 + A(x))^2 dx. - Paul D. Hanna, Sep 06 2008
From Peter Bala, Sep 06 2011: (Start)
The generating function A(x) = x+4*x^2/2!+32*x^3/3!+... satisfies the autonomous differential equation A'(x) = (1+2*A)/(1-2*A) with A(0) = 0. Hence the inverse function A^-1(x) = Integral_{t = 0..x} (1-2*t)/(1+2*t) dt = log(1+2*x)-x.
The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx((1+2*x)/(1-2*x)*g(x)). Compare with A032188.
Applying [Bergeron et al., Theorem 1] to the result x = Integral_{t = 0..A(x)} 1/phi(t) dt, where phi(t) = (1+2*t)/(1-2*t) = 1+4*t+8*t^2+16*t^3+32*t^4+... leads to the following combinatorial interpretation for this sequence: a(n) gives the number of plane increasing trees on n vertices where each vertex of outdegree k >= 1 can be colored in 2^(k+1) ways. An example is given below. (End)
a(n) = Sum_{k=1..n-1} (n+k-1)!*Sum_{j=1..k} (-1)^j/(k-j)!*Sum_{i=0..j} (-1)^i* 2^(n-i+j-1)*Stirling1(n-i+j-1,j-i)/((n-i+j-1)!*i!), n>1, a(1)=1. - Vladimir Kruchinin, Jan 30 2012
Let p(n,w) = w*Sum_{k=0..n-1}((-1)^k*E2(n-1,k)*w^k)/(1+w)^(2*n-1), E2 the second-order Eulerian numbers as defined by Knuth, then a(n) = -p(n,-1/2). - Peter Luschny, Nov 10 2012
a(n) ~ (2/(2*log(2)-1))^(n-1/2)*n^(n-1)/exp(n). - Vaclav Kotesovec, Jan 05 2013
G.f.: 1/Q(0), where Q(k)= 1 - 2*(k+1)*x - 2*x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
a(n) = 2*a(n-1) + Sum_{j=1..n-1} binomial(n,j)*a(j)*a(n-j) for n>1, a(1) = 1. - Peter Luschny, May 24 2017
a(1) = 1; a(n) = n! * [x^n] exp(x + Sum_{k=1..n-1} a(k)*x^k/k!). - Ilya Gutkovskiy, Oct 18 2017

cp's OEIS Frontend

A000311 Schroeder's fourth problem; also series-reduced rooted trees with n labeled leaves; also number of total partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

Python

Formula

Extensions

A006351 Number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Sage

Formula

A005736 Number of degenerate fanout-free Boolean functions of n variables using And, Or and Not gates.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A005172 Number of labeled rooted trees of subsets of an n-set.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Sage

Formula

A005263 Number of labeled Greg trees.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A224766 Number of non-degenerate fanout-free Boolean functions of n variables using And, Or and Not gates.

Views

Author