A141268 -id:A141268 - 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

A005804 Number of phylogenetic rooted trees with n labels.

Original entry on oeis.org

1, 2, 8, 58, 612, 8374, 140408, 2785906, 63830764, 1658336270, 48169385024, 1546832023114, 54413083601268, 2080827594898342, 85948745163598088, 3813417859420469410, 180876816831806597500, 9133309115320844870078, 489156459621633161274704, 27696066472039561313329018

Offset: 1

N. J. A. Sloane

These are series-reduced rooted trees where each leaf is a nonempty subset of the set of n labels.

See A141268 for phylogenetic rooted trees with n unlabeled objects. - Thomas Wieder, Jun 20 2008

			a(3)=8 because we have:
  Set(Set(Z[3]),Set(Z[1]),Set(Z[2])),
  Set(Z[3],Z[2],Z[1]),
  Set(Set(Z[3],Z[1]),Set(Z[2])),
  Set(Set(Set(Z[3]),Set(Z[2])),Set(Z[1])),
  Set(Set(Set(Z[3]),Set(Z[1])),Set(Z[2])),
  Set(Set(Z[3]),Set(Set(Z[1]),Set(Z[2]))),
  Set(Set(Z[3]),Set(Z[2],Z[1])),
  Set(Set(Z[3],Z[2]),Set(Z[1])).
From _Gus Wiseman_, Jul 31 2018: (Start)
The 8 series-reduced rooted trees whose leaves are a set partition of {1,2,3}:
  {1,2,3}
  ({1}{2,3})
  ({1}({2}{3}))
  ({2}{1,3})
  ({2}({1}{3}))
  ({3}{1,2})
  ({3}({1}{2}))
  ({1}{2}{3})
(End)

Foulds, L. R.; Robinson, R. W. Enumeration of phylogenetic trees without points of degree two. Ars Combin. 17 (1984), A, 169-183. Math. Rev. 85f:05045
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..380 (first 100 terms from T. D. Noe)
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A000081, A000311, A000669, A001678, A005805, A141268, A292504, A300660, A316656.

# From Thomas Wieder, Jun 20 2008: (Start)
ser := series(-LambertW(-1/2*exp(1/2*exp(z)-1)) + 1/2*exp(z)-1, z=0, 10);
seq(n!*coeff(ser, z, n), n = 1..9);
# Alternative:
with(combstruct):
A005804 := [H, {H=Union(Set(Z,card>=1), Set(H,card>=2))}, labelled];
seq(count(A005804,size=j), j=1..20);
# (End)

numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
a[n_]:=a[n]=If[n==1,1,1+Sum[numSetPtnsOfType[ptn]*Times@@a/@ptn,{ptn,Rest[IntegerPartitions[n]]}]];
Array[a,20] (* Gus Wiseman, Jul 31 2018 *)

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n,k)={my(v=vector(n)); for(n=1, n, v[n]=binomial(n+k-1, n) + EulerT(v[1..n])[n]); v}
seq(n)={my(M=Mat(vectorv(n, k, b(n,k)))); vector(n, k, sum(i=1, k, binomial(k, i)*(-1)^(k-i)*M[i,k]))} \\ Andrew Howroyd, Oct 26 2018

Stirling transform of [ 1, 1, 4, 26, 236, ... ] = A000311 [ Foulds and Robinson ].
E.g.f.: -LambertW(-(1/2)*exp((1/2)*exp(z) - 1)) + (1/2)*exp(z) - 1. - Thomas Wieder, Jun 20 2008
a(n) ~ sqrt(log(2))*(log(2)+log(log(2)))^(1/2-n)*n^(n-1)/exp(n). - Vaclav Kotesovec, Aug 07 2013
E.g.f. f(x) satisfies  2*f(x) - exp(f(x)) = exp(x) - 2. - Gus Wiseman, Jul 31 2018

More terms, comment from Christian G. Bower, Dec 15 1999

A292504 Number of orderless tree-factorizations of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 2, 2, 11, 1, 6, 1, 6, 2, 2, 1, 20, 2, 2, 4, 6, 1, 8, 1, 30, 2, 2, 2, 27, 1, 2, 2, 20, 1, 8, 1, 6, 6, 2, 1, 74, 2, 6, 2, 6, 1, 20, 2, 20, 2, 2, 1, 38, 1, 2, 6, 96, 2, 8, 1, 6, 2, 8, 1, 114, 1, 2, 6, 6, 2, 8, 1, 74, 11, 2, 1

Offset: 1

Gus Wiseman, Sep 17 2017

nonn

A factorization of n is a finite multiset of positive integers greater than 1 with product n. An orderless tree-factorization of n is either (case 1) the number n itself or (case 2) a finite multiset of two or more orderless tree-factorizations, one of each factor in a factorization of n.

a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

			The a(16)=11 orderless tree-factorizations are: 16, (28), (2(24)), (2(2(22))), (2(222)), (44), (4(22)), ((22)(22)), (224), (22(22)), (2222).

Michael De Vlieger, Table of n, a(n) for n = 1..16384
Michael De Vlieger, Records and indices of records.

Cf. A000311, A001055, A050336, A141268, A281118, A292505.

postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[postfacs[n],{n}],n]];
Table[Length[oltfacs[n]],{n,83}]

seq(n)={my(v=vector(n), w=vector(n)); w[1]=v[1]=1; for(k=2, n, w[k]=v[k]+1; forstep(j=n\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j] += binomial(e+w[k]-1, e)*v[i]))); w} \\ Andrew Howroyd, Nov 18 2018

a(p^n) = A141268(n) for prime p. - Andrew Howroyd, Nov 18 2018

A050342 Expansion of Product_{m>=1} (1+x^m)^A000009(m).

Original entry on oeis.org

1, 1, 1, 3, 4, 7, 12, 19, 30, 49, 77, 119, 186, 286, 438, 670, 1014, 1528, 2300, 3437, 5119, 7603, 11241, 16564, 24343, 35650, 52058, 75820, 110115, 159510, 230522, 332324, 477994, 686044, 982519, 1404243, 2003063, 2851720, 4052429, 5748440, 8140007, 11507125

Offset: 0

Christian G. Bower, Oct 15 1999

nonn

Number of partitions of n into distinct parts with one level of parentheses. Each "part" in parentheses is distinct from all others at the same level. Thus (2+1)+(1) is allowed but (2)+(1+1) and (2+1+1) are not.

			4=(4)=(3)+(1)=(3+1)=(2+1)+(1).
From _Gus Wiseman_, Oct 11 2018: (Start)
a(n) is the number of set systems (sets of sets) whose multiset union is an integer partition of n. For example, the a(1) = 1 through a(6) = 12 set systems are:
  {{1}}  {{2}}  {{3}}      {{4}}        {{5}}        {{6}}
                {{1,2}}    {{1,3}}      {{1,4}}      {{1,5}}
                {{1},{2}}  {{1},{3}}    {{2,3}}      {{2,4}}
                           {{1},{1,2}}  {{1},{4}}    {{1,2,3}}
                                        {{2},{3}}    {{1},{5}}
                                        {{1},{1,3}}  {{2},{4}}
                                        {{2},{1,2}}  {{1},{1,4}}
                                                     {{1},{2,3}}
                                                     {{2},{1,3}}
                                                     {{3},{1,2}}
                                                     {{1},{2},{3}}
                                                     {{1},{2},{1,2}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..4000
N. J. A. Sloane, Transforms

Cf. A050343-A050350, A089254.
Cf. A001970, A089259, A141268, A258466, A261049, A320328, A320330.
Row sums of A330462 and of A360764.

g:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, g(n, i-1)+`if`(i>n, 0, g(n-i, i-1))))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(g(i, i), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..50);  # Alois P. Heinz, May 19 2013

g[n_, i_] := g[n, i] = If[n==0, 1, If[i<1, 0, g[n, i-1] + If[i>n, 0, g[n-i, i-1]]]]; b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[g[i, i], j]*b[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Dec 19 2015, after Alois P. Heinz *)
nn=10;Table[SeriesCoefficient[Product[(1+x^k)^PartitionsQ[k],{k,nn}],{x,0,n}],{n,0,nn}] (* Gus Wiseman, Oct 11 2018 *)

Weigh transform of A000009.

A339645 Triangle read by rows: T(n,k) is the number of inequivalent colorings of lone-child-avoiding rooted trees with n colored leaves using exactly k colors.

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 5, 17, 12, 5, 12, 73, 95, 44, 12, 33, 369, 721, 512, 168, 33, 90, 1795, 5487, 5480, 2556, 625, 90, 261, 9192, 41945, 58990, 36711, 12306, 2342, 261, 766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766, 2312, 249164, 2483192, 6593103, 7141755, 3965673, 1283624, 258887, 32313, 2312

Offset: 1

Andrew Howroyd, Dec 11 2020

Only the leaves are colored. Equivalence is up to permutation of the colors.

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

			Triangle begins:
    1;
    1,     1;
    2,     3,      2;
    5,    17,     12,      5;
   12,    73,     95,     44,     12;
   33,   369,    721,    512,    168,     33;
   90,  1795,   5487,   5480,   2556,    625,    90;
  261,  9192,  41945,  58990,  36711,  12306,  2342,  261;
  766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766;
  ...
From _Gus Wiseman_, Jan 02 2021: (Start)
Non-isomorphic representatives of the 39 = 5 + 17 + 12 + 5 trees with four colored leaves:
  (1111)      (1112)      (1123)      (1234)
  (1(111))    (1122)      (1(123))    (1(234))
  (11(11))    (1(112))    (11(23))    (12(34))
  ((11)(11))  (11(12))    (12(13))    ((12)(34))
  (1(1(11)))  (1(122))    (2(113))    (1(2(34)))
              (11(22))    (23(11))
              (12(11))    ((11)(23))
              (12(12))    (1(1(23)))
              (2(111))    ((12)(13))
              ((11)(12))  (1(2(13)))
              (1(1(12)))  (2(1(13)))
              ((11)(22))  (2(3(11)))
              (1(1(22)))
              (1(2(11)))
              ((12)(12))
              (1(2(12)))
              (2(1(11)))
(End)

Andrew Howroyd, PARI Functions for Combinatorial Species, v2, Dec 2020.
Wikipedia, Combinatorial species

The case with only one color is A000669.
Counting by nodes gives A318231.
A labeled version is A319376.
Row sums are A330470.
A000311 counts singleton-reduced phylogenetic trees.
A001678 counts unlabeled lone-child-avoiding rooted trees.
A005121 counts chains of set partitions, with maximal case A002846.
A005804 counts phylogenetic rooted trees with n labels.
A060356 counts labeled lone-child-avoiding rooted trees.
A141268 counts lone-child-avoiding rooted trees with leaves summing to n.
A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.
A316651 counts lone-child-avoiding rooted trees with normal leaves.
A316652 counts lone-child-avoiding rooted trees with strongly normal leaves.
A330465 counts inequivalent leaf-colorings of phylogenetic rooted trees.
Cf. A196545, A213427, A281118, A289501, A292504, A318812, A319312, A330627.

\\ See link above for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n )); x*Ser(v)}
{my(A=InequivalentColoringsTriangle(cycleIndexSeries(10))); for(n=1, #A~, print(A[n,1..n]))}

A096373 Number of partitions of n such that the least part occurs exactly twice.

Original entry on oeis.org

0, 1, 0, 2, 1, 3, 3, 6, 5, 11, 11, 17, 20, 30, 33, 49, 56, 77, 92, 122, 143, 190, 225, 287, 344, 435, 516, 648, 770, 951, 1134, 1388, 1646, 2007, 2376, 2868, 3395, 4078, 4807, 5749, 6764, 8042, 9449, 11187, 13101, 15463, 18070, 21236, 24772, 29021, 33764

Offset: 1

Vladeta Jovovic, Jul 19 2004

Also number of partitions of n such that the difference between the two largest distinct parts is 2 (it is assumed that 0 is a part in each partition). Example: a(6)=3 because we have [4,2], [3,1,1,1] and [2,2,2]. - Emeric Deutsch, Apr 08 2006
Number of partitions p of n+2 such that min(p) + (number of parts of p) is a part of p. - Clark Kimberling, Feb 27 2014
Number of partitions of n+1 such that the two smallest parts differ by one. - Giovanni Resta, Mar 07 2014
Also the number of integer partitions of n with an even number of parts that cannot be grouped into pairs of distinct parts. These are also integer partitions of n with an even number of parts whose greatest multiplicity is greater than half the number of parts. - Gus Wiseman, Oct 26 2018

			a(6)=3 because we have [4,1,1], [3,3] and [2,2,1,1].
G.f. = x^2 + 2*x^4 + x^5 + 3*x^6 + 3*x^7 + 6*x^8 + 5*x^9 + 11*x^10 + 11*x^11 + ...
From _Gus Wiseman_, Oct 26 2018: (Start)
The a(2) = 1 through a(10) = 11 partitions where the least part occurs exactly twice (zero terms not shown):
  (11)  (22)   (311)  (33)    (322)   (44)     (522)    (55)
        (211)         (411)   (511)   (422)    (711)    (433)
                      (2211)  (3211)  (611)    (4311)   (622)
                                      (3311)   (5211)   (811)
                                      (4211)   (32211)  (3322)
                                      (22211)           (4411)
                                                        (5311)
                                                        (6211)
                                                        (33211)
                                                        (42211)
                                                        (222211)
The a(2) = 1 through a(10) = 11 partitions that cannot be grouped into pairs of distinct parts (zero terms not shown):
  (11) (22)   (2111) (33)     (2221)   (44)       (3222)     (55)
       (1111)        (3111)   (4111)   (2222)     (6111)     (3331)
                     (111111) (211111) (5111)     (321111)   (4222)
                                       (221111)   (411111)   (7111)
                                       (311111)   (21111111) (222211)
                                       (11111111)            (331111)
                                                             (421111)
                                                             (511111)
                                                             (22111111)
                                                             (31111111)
                                                             (1111111111)
(End)

Giovanni Resta, Table of n, a(n) for n = 1..1000

Cf. A002865, A097091, A097092, A097093.
Cf. A117989.
Cf. A000070, A000569, A007717, A025065, A141268, A209816, A261049, A320328, A320891, A320921, A320922.

g:=sum(x^(2*k)/product(1-x^j,j=k+1..80),k=1..70): gser:=series(g,x=0,55): seq(coeff(gser,x,n),n=1..51); # Emeric Deutsch, Apr 08 2006

(* do first *) Needs["DiscreteMath`Combinatorica`"] (* then *) f[n_] := Block[{p = Partitions[n], l = PartitionsP[n], c = 0, k = 1}, While[k < l + 1, q = PadLeft[ p[[k]], 3]; If[ q[[1]] != q[[3]] && q[[2]] == q[[3]], c++ ]; k++ ]; c]; Table[ f[n], {n, 51}] (* Robert G. Wilson v, Jul 23 2004 *)
Table[Count[IntegerPartitions[n+2], p_ /; MemberQ[p, Length[p] + Min[p]]], {n, 50}] (* Clark Kimberling, Feb 27 2014 *)
p[n_, m_] := If[m == n, 1, If[m > n, 0, p[n, m] = Sum[p[n-m, k], {k, m, n}]]];
a[n_] := Sum[p[n+1-k, k+1], {k, n/2}]; Array[a, 100] (* Giovanni Resta, Mar 07 2014 *)

{q=sum(m=1,100,x^(2*m)/prod(i=m+1,100,1-x^i,1+O(x^60)),1+O(x^60));for(n=1,51,print1(polcoeff(q,n),","))} \\ Klaus Brockhaus, Jul 21 2004

{a(n) = if( n<0, 0, polcoeff( ( 1 - (1 - x - x^2) / eta(x + x^4 * O(x^n)) ) * (1 - x) / x^3, n))} /* Michael Somos, Feb 28 2014 */

G.f.: Sum_{m>0} (x^(2*m) / Product_{i>m} (1-x^i)). More generally, g.f. for number of partitions of n such that the least part occurs exactly k times is Sum_{m>0} (x^(k*m)/Product_{i>m} (1-x^i)).
G.f.: Sum_{k>=1} (x^(2*k-2)*(1-x^(k-1))/Product_{j=1..k} (1-x^j)). - Emeric Deutsch, Apr 08 2006
a(n) = -p(n+3)+2*p(n+2)-p(n), p(n)=A000041(n). - Mircea Merca, Jul 10 2013
a(n) ~ exp(Pi*sqrt(2*n/3)) * Pi / (12*sqrt(2)*n^(3/2)). - Vaclav Kotesovec, Jun 02 2018

Edited and extended by Robert G. Wilson v and Klaus Brockhaus, Jul 21 2004

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

A005804 Number of phylogenetic rooted trees with n labels.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A292504 Number of orderless tree-factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A050342 Expansion of Product_{m>=1} (1+x^m)^A000009(m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A339645 Triangle read by rows: T(n,k) is the number of inequivalent colorings of lone-child-avoiding rooted trees with n colored leaves using exactly k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A096373 Number of partitions of n such that the least part occurs exactly twice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple