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

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]))}

A060356 Expansion of e.g.f.: -LambertW(-x/(1+x)).

Original entry on oeis.org

0, 1, 0, 3, 4, 65, 306, 4207, 38424, 573057, 7753510, 134046671, 2353898196, 47602871329, 1013794852266, 23751106404495, 590663769125296, 15806094859299329, 448284980183376078, 13515502344669830287

Offset: 0

Vladeta Jovovic, Apr 01 2001

Also the number of labeled lone-child-avoiding rooted trees with n nodes. A rooted tree is lone-child-avoiding if it has no unary branchings, meaning every non-leaf node covers at least two other nodes. The unlabeled version is A001678(n + 1). - Gus Wiseman, Jan 20 2020

			From _Gus Wiseman_, Dec 31 2019: (Start)
Non-isomorphic representatives of the a(7) = 4207 trees, written as root[branches], are:
  1[2,3[4,5[6,7]]]
  1[2,3[4,5,6,7]]
  1[2[3,4],5[6,7]]
  1[2,3,4[5,6,7]]
  1[2,3,4,5[6,7]]
  1[2,3,4,5,6,7]
(End)

Harry J. Smith, Table of n, a(n) for n = 0..100
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Cf. A052871, A060313.
Cf. A008297.
Column k=0 of A231602.
The unlabeled version is A001678(n + 1).
The case where the root is fixed is A108919.
Unlabeled rooted trees are counted by A000081.
Lone-child-avoiding rooted trees with labeled leaves are A000311.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Singleton-reduced rooted trees are counted by A330951.
Cf. A000669, A004111, A005121, A048816, A292504, A316651, A316652, A318231, A318813, A330465, A330624.

List([0..20],n->Sum([1..n],k->(-1)^(n-k)*Factorial(n)/Factorial(k) *Binomial(n-1,k-1)*k^(k-1))); # Muniru A Asiru, Feb 19 2018

seq(coeff(series( -LambertW(-x/(1+x)), x, n+1), x, n)*n!, n = 0..20); # G. C. Greubel, Mar 16 2020

CoefficientList[Series[-LambertW[-x/(1+x)], {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Nov 27 2012 *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
a[n_]:=If[n==1,1,n*Sum[Times@@a/@Length/@stn,{stn,Select[sps[Range[n-1]],Length[#]>1&]}]];
Array[a,10] (* Gus Wiseman, Dec 31 2019 *)

{ for (n=0, 100, f=n!; a=sum(k=1, n, (-1)^(n - k)*f/k!*binomial(n - 1, k - 1)*k^(k - 1)); write("b060356.txt", n, " ", a); ) } \\ Harry J. Smith, Jul 04 2009

my(x='x+O('x^20)); concat([0], Vec(serlaplace(-lambertw(-x/(1+x))))) \\ G. C. Greubel, Feb 19 2018

a(n) = Sum_{k=1..n} (-1)^(n-k)*n!/k!*binomial(n-1, k-1)*k^(k-1). a(n) = Sum_{k=0..n} Stirling1(n, k)*A058863(k). - Vladeta Jovovic, Sep 17 2003
a(n) ~ n^(n-1) * (1-exp(-1))^(n+1/2). - Vaclav Kotesovec, Nov 27 2012
a(n) = n * A108919(n). - Gus Wiseman, Dec 31 2019

A316652 Number of series-reduced rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.

Original entry on oeis.org

1, 2, 9, 69, 623, 7793, 110430, 1906317, 36833614, 816101825, 19925210834, 541363267613, 15997458049946, 515769374925576, 17905023985615254, 669030297769291562, 26689471638523499483, 1134895275721374771655, 51161002326406795249910, 2440166138715867838359915

Offset: 1

Gus Wiseman, Jul 09 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches.

			The a(3) = 9 trees:
(1(11)), (111),
(1(12)), (2(11)), (112),
(1(23)), (2(13)), (3(12)), (123).

Cf. A000081, A000311, A000669, A001678, A005804, A141268, A181821, A292504, A304660.

Cf. A316651, A316653, A316654, A316655, A316656.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
Table[Sum[Length[gro[m]],{m,Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n]}],{n,4}]

\\ See A339645 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)}
StronglyNormalLabelingsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Jan 04 2021

Terms a(10) and beyond from Andrew Howroyd, Jan 04 2021

A108919 Number of series-reduced labeled trees with n nodes.

Original entry on oeis.org

1, 0, 1, 1, 13, 51, 601, 4803, 63673, 775351, 12186061, 196158183, 3661759333, 72413918019, 1583407093633, 36916485570331, 929770285841137, 24904721121298671, 711342228666833173, 21502519995056598639, 687345492498807434461, 23135454269839313430715, 818568166383797223246601, 30357965273255025673685091

Offset: 1

Vladeta Jovovic, Jul 20 2005

"Series-reduced" means that if the tree is rooted at 1, then there is no node with just a single child.

Callan points out that A002792 is an incorrect version of this sequence. - Joerg Arndt, Jul 01 2014

Seiichi Manyama, Table of n, a(n) for n = 1..415
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], 2014.

The rooted version is A060356.

Cf. A000311, A000669, A001678, A292504, A316651, A316652, A318231, A318813, A330465, A330624, A352410.

f[n_] := Sum[(-1)^(n-k)*n!/k!*Binomial[n-1, k-1]*k^(k-1), {k, n}]/n; Table[ f[n], {n, 20}] (* Robert G. Wilson v, Jul 21 2005 *)

a(n) = { 1/n * sum(k=1, n, (-1)^(n-k) * binomial(n,k) * (n-1)!/(k-1)! * k^(k-1) ); } \\ Joerg Arndt, Aug 28 2014

a(n) = A060356(n)/n.
1 = Sum_{n>=0} a(n+1)*(exp(x)-x)^(-n-1)*x^n/n!.
E.g.f.: A(x) = Sum_{n>=0} a(n+1)*x^n/n! satisfies A(x) = exp(x*A(x))/(1+x). - Olivier Gérard, Dec 31 2013 (edited by Gus Wiseman, Dec 31 2019)
E.g.f.: -Integral (LambertW(-x/(1 + x))/x) dx. - Ilya Gutkovskiy, Jul 01 2020

More terms from Robert G. Wilson v, Jul 21 2005
New name (from A002792) by Joerg Arndt, Aug 28 2014
Offset corrected by Gus Wiseman, Dec 31 2019

A330465 Number of non-isomorphic series-reduced rooted trees whose leaves are multisets with a total of n elements.

Original entry on oeis.org

1, 4, 14, 87, 608, 5573, 57876, 687938, 9058892, 130851823, 2048654450, 34488422057, 620046639452, 11839393796270, 238984150459124, 5079583100918338, 113299159314626360, 2644085918303683758, 64393240540265515110, 1632731130253043991252, 43013015553755764179000

Offset: 1

Gus Wiseman, Dec 21 2019

nonn

Also inequivalent leaf-colorings of phylogenetic rooted trees with n labels. A phylogenetic rooted tree is a series-reduced rooted tree whose leaves are (usually disjoint) sets.

			Non-isomorphic representatives of the a(3) = 14 trees:
  ((1)((1)(1)))  ((1)((1)(2)))  ((1)((2)(3)))  ((2)((1)(1)))
  ((1)(1)(1))    ((1)(1)(2))    ((1)(2)(3))    ((2)(1,1))
  ((1)(1,1))     ((1)(1,2))     ((1)(2,3))
  (1,1,1)        (1,1,2)        (1,2,3)

The version where leaves are atoms is A318231.
The case with sets as leaves is A330624.
The case with disjoint sets as leaves is A141268.
Labeled versions are A330467 (strongly normal) and A330469 (normal).
The singleton-reduced version is A330470.
Cf. A000311, A000669, A004114, A005804, A007716, A281118, A289501, A292504, A316651, A316652, A318812, A319312, A330471, A330474, A330625, A339645.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n), p=sEulerT(x*sv(1) + O(x*x^n))); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sEulerT(x*Ser(v[1..n])), n ) + polcoef(p,n)); x*Ser(v)}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 13 2020

Terms a(7) and beyond from Andrew Howroyd, Dec 13 2020

A316655 Number of series-reduced rooted trees whose leaves span an initial interval of positive integers with multiplicities the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 1, 2, 3, 5, 4, 12, 9, 12, 17, 33, 29, 44, 26, 90, 90, 261, 68, 168, 93, 766, 144, 197, 307, 575, 269, 2312, 428, 7068, 236, 625, 1017, 863, 954, 21965, 3409, 2342, 712

Offset: 1

Gus Wiseman, Jul 09 2018

A rooted tree is series-reduced if every non-leaf node has at least two branches.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			Sequence of sets of trees begins:
1:
2: 1
3: (11)
4: (12)
5: (1(11)), (111)
6: (1(12)), (2(11)), (112)
7: (1(1(11))), (1(111)), ((11)(11)), (11(11)), (1111)
8: (1(23)), (2(13)), (3(12)), (123)
9: (1(1(22))), (1(2(12))), (1(122)), (2(1(12))), (2(2(11))), (2(112)), ((11)(22)), ((12)(12)), (11(22)), (12(12)), (22(11)), (1122)

Cf. A000081, A000311, A000669, A001678, A005804, A056239, A141268, A181821, A292504, A296150, A300660, A304660.

Cf. A316651, A316652, A316653, A316654, A316656.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
Table[Length[gro[Flatten[MapIndexed[Table[#2,{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]]]]],{n,20}]

a(prime(n)) = A000669(n).

a(2^n) = A000311(n).

a(37)-a(40) from Robert Price, Sep 13 2018

A330470 Number of non-isomorphic series/singleton-reduced rooted trees on a multiset of size n.

Original entry on oeis.org

1, 1, 2, 7, 39, 236, 1836, 16123, 162008, 1802945, 22012335, 291290460, 4144907830, 62986968311, 1016584428612, 17344929138791, 311618472138440, 5875109147135658, 115894178676866576, 2385755803919949337, 51133201045333895149, 1138659323863266945177, 26296042933904490636133

Offset: 0

Gus Wiseman, Dec 22 2019

nonn

A series/singleton-reduced rooted tree on a multiset m is either the multiset m itself or a sequence of series/singleton-reduced rooted trees, one on each part of a multiset partition of m that is neither minimal (all singletons) nor maximal (only one part).

			Non-isomorphic representatives of the a(4) = 39 trees, with singleton leaves (x) replaced by just x:
  (1111)      (1112)      (1122)      (1123)      (1234)
  (1(111))    (1(112))    (1(122))    (1(123))    (1(234))
  (11(11))    (11(12))    (11(22))    (11(23))    (12(34))
  ((11)(11))  (12(11))    (12(12))    (12(13))    ((12)(34))
  (1(1(11)))  (2(111))    ((11)(22))  (2(113))    (1(2(34)))
              ((11)(12))  (1(1(22)))  (23(11))
              (1(1(12)))  ((12)(12))  ((11)(23))
              (1(2(11)))  (1(2(12)))  (1(1(23)))
              (2(1(11)))              ((12)(13))
                                      (1(2(13)))
                                      (2(1(13)))
                                      (2(3(11)))

The case with all atoms equal or all atoms different is A000669.
Not requiring singleton-reduction gives A330465.
Labeled versions are A316651 (normal orderless) and A330471 (strongly normal).
The case where the leaves are sets is A330626.
Row sums of A339645.
Cf. A000311, A005121, A005804, A141268, A213427, A292504, A292505, A318812, A318848, A318849, A330467, A330469, A330474, A330624.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sEulerT(x*Ser(v[1..n])), n )); x*Ser(v)}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 11 2020

Terms a(7) and beyond from Andrew Howroyd, Dec 11 2020

A330655 Number of balanced reduced multisystems of weight n whose atoms cover an initial interval of positive integers.

Original entry on oeis.org

1, 1, 2, 12, 138, 2652, 78106, 3256404, 182463296, 13219108288, 1202200963522, 134070195402644, 17989233145940910, 2858771262108762492, 530972857546678902490, 113965195745030648131036, 27991663753030583516229824, 7800669355870672032684666900, 2448021231611414334414904013956

Offset: 0

Gus Wiseman, Dec 27 2019

nonn

A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem. The weight of an atom is 1, while the weight of a multiset is the sum of weights of its elements.

			The a(0) = 1 through a(3) = 12 multisystems:
  {}  {1}  {1,1}  {1,1,1}
           {1,2}  {1,1,2}
                  {1,2,2}
                  {1,2,3}
                  {{1},{1,1}}
                  {{1},{1,2}}
                  {{1},{2,2}}
                  {{1},{2,3}}
                  {{2},{1,1}}
                  {{2},{1,2}}
                  {{2},{1,3}}
                  {{3},{1,2}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Row sums of A330776.
The unlabeled version is A330474.
The strongly normal case is A330475.
The tree version is A330654.
The maximum-depth case is A330676.
The case where the atoms are all different is A005121.
The case where the atoms are all equal is A318813.
Multiset partitions of normal multisets are A255906.
Series-reduced rooted trees with normal leaves are A316651.
Cf. A000311, A000669, A001678, A213427, A318812, A330675, A330679.

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
totm[m_]:=Prepend[Join@@Table[totm[p],{p,Select[mps[m],1

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n,k)={my(v=vector(n), u=vector(n)); v[1]=k; for(n=1, #v, u += v*sum(j=n, #v, (-1)^(j-n)*binomial(j-1,n-1)); v=EulerT(v)); u}
seq(n)={concat([1], sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k))))} \\ Andrew Howroyd, Dec 30 2019

Terms a(7) and beyond from Andrew Howroyd, Dec 30 2019

A316653 Number of series-reduced rooted identity trees with n leaves spanning an initial interval of positive integers.

Original entry on oeis.org

1, 1, 6, 58, 774, 13171, 272700, 6655962, 187172762, 5959665653, 211947272186, 8327259067439, 358211528524432, 16744766791743136, 845195057333580332, 45814333121920927067, 2654330505021077873594, 163687811930206581162063, 10705203621191765328300832

Offset: 1

Gus Wiseman, Jul 09 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is an identity tree if no branch appears multiple times under the same root.

			The a(3) = 6 trees are (1(12)), (2(12)), (1(23)), (2(13)), (3(12)), (123).

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000081, A000311, A000669, A001678, A004111, A005804, A034691, A141268, A292504, A300660.

Cf. A316651, A316652, A316654, A316655, A316656.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
gro[m_]:=If[Length[m]==1,m,Select[Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])],UnsameQ@@#&]];
allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Sum[Length[gro[m]],{m,allnorm[n]}],{n,5}]

\\ here R(n,2) is A031148.
WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
R(n,k)={my(v=[k]); for(n=2, n, v=concat(v, WeighT(concat(v,[0]))[n])); v}
seq(n)={sum(k=1, n, R(n,k)*sum(r=k, n, binomial(r,k)*(-1)^(r-k)) )} \\ Andrew Howroyd, Sep 14 2018

Terms a(9) and beyond from Andrew Howroyd, Sep 14 2018

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

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

A060356 Expansion of e.g.f.: -LambertW(-x/(1+x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

PARI

Formula

A316652 Number of series-reduced rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A108919 Number of series-reduced labeled trees with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A330465 Number of non-isomorphic series-reduced rooted trees whose leaves are multisets with a total of n elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A316655 Number of series-reduced rooted trees whose leaves span an initial interval of positive integers with multiplicities the integer partition with Heinz number n.