A001678 -id:A001678 - cp's OEIS frontend

A002033 Number of perfect partitions of n.

1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3, 3, 1, 20, 2, 3, 4, 8, 1, 13, 1, 16, 3, 3, 3, 26, 1, 3, 3, 20, 1, 13, 1, 8, 8, 3, 1, 48, 2, 8, 3, 8, 1, 20, 3, 20, 3, 3, 1, 44, 1, 3, 8, 32, 3, 13, 1, 8, 3, 13, 1, 76, 1, 3, 8, 8, 3, 13, 1, 48, 8, 3, 1, 44, 3, 3, 3, 20, 1, 44, 3, 8, 3, 3, 3, 112

Offset: 0

N. J. A. Sloane

A perfect partition of n is one which contains just one partition of every number less than n when repeated parts are regarded as indistinguishable. Thus 1^n is a perfect partition for every n; and for n = 7, 4 1^3, 4 2 1, 2^3 1 and 1^7 are all perfect partitions. [Riordan]
Also number of ordered factorizations of n+1, see A074206.
Also number of gozinta chains from 1 to n (see A034776). - David W. Wilson
a(n) is the permanent of the n X n matrix with (i,j) entry = 1 if j|i+1 and = 0 otherwise. For n=3 the matrix is {{1, 1, 0}, {1, 0, 1}, {1, 1, 0}} with permanent = 2. - David Callan, Oct 19 2005
Appears to be the number of permutations that contribute to the determinant that gives the Moebius function. Verified up to a(9). - Mats Granvik, Sep 13 2008
Dirichlet inverse of A153881 (assuming offset 1). - Mats Granvik, Jan 03 2009
Equals row sums of triangle A176917. - Gary W. Adamson, Apr 28 2010
A partition is perfect iff it is complete (A126796) and knapsack (A108917). - Gus Wiseman, Jun 22 2016
a(n) is also the number of series-reduced planted achiral trees with n + 1 unlabeled leaves, where a rooted tree is series-reduced if all terminal subtrees have at least two branches, and achiral if all branches directly under any given node are equal. Also Moebius transform of A067824. - Gus Wiseman, Jul 13 2018

			n=0: 1 (the empty partition)
n=1: 1 (1)
n=2: 1 (11)
n=3: 2 (21, 111)
n=4: 1 (1111)
n=5: 3 (311, 221, 11111)
n=6: 1 (111111)
n=7: 4 (4111, 421, 2221, 1111111)
From _Gus Wiseman_, Jul 13 2018: (Start)
The a(11) = 8 series-reduced planted achiral trees with 12 unlabeled leaves:
  (oooooooooooo)
  ((oooooo)(oooooo))
  ((oooo)(oooo)(oooo))
  ((ooo)(ooo)(ooo)(ooo))
  ((oo)(oo)(oo)(oo)(oo)(oo))
  (((ooo)(ooo))((ooo)(ooo)))
  (((oo)(oo)(oo))((oo)(oo)(oo)))
  (((oo)(oo))((oo)(oo))((oo)(oo)))
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
D. E. Knuth, The Art of Computer Programming, Pre-Fasc. 3b, Sect. 7.2.1.5, no. 67, p. 25.
P. A. MacMahon, The theory of perfect partitions and the compositions of multipartite numbers, Messenger Math., 20 (1891), 103-119.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 123-124.
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).

T. D. Noe, Table of n, a(n) for n = 0..9999
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
HoKyu Lee, Double perfect partitions, Discrete Math., 306 (2006), 519-525.
Paul Pollack, On the parity of the number of multiplicative partitions and related problems, Proc. Amer. Math. Soc. 140 (2012), 3793-3803.
J. Riordan, Letter to N. J. A. Sloane, Dec. 1970
Eric Weisstein's World of Mathematics, Perfect Partition
Eric Weisstein's World of Mathematics, Dirichlet Series Generating Function
Index entries for "core" sequences

Same as A074206, up to the offset and initial term there.
Cf. A001055, A050324.
a(A002110)=A000670.
Cf. A000123, A100529, A117621.
Cf. A176917.
For parity see A008966.
Cf. A126796, A108917.
Cf. A001678, A003238, A067824, A167865, A214577, A289078, A292504, A316782.

a := array(1..150): for k from 1 to 150 do a[k] := 0 od: a[1] := 1: for j from 2 to 150 do for m from 1 to j-1 do if j mod m = 0 then a[j] := a[j]+a[m] fi: od: od: for k from 1 to 150 do printf(`%d,`,a[k]) od: # James Sellers, Dec 07 2000
# alternative
A002033 := proc(n)
    option remember;
    local a;
    if n <= 2 then
        return 1;
    else
        a := 0 ;
        for i from 0 to n-1 do
            if modp(n+1,i+1) = 0 then
                a := a+procname(i);
            end if;
        end do:
    end if;
    a ;
end proc: # R. J. Mathar, May 25 2017

a[0] = 1; a[1] = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range[96]  (* Jean-François Alcover, Apr 06 2011, updated Sep 23 2014. NOTE: This produces A074206(n) = a(n-1). - M. F. Hasler, Oct 12 2018 *)

A002033(n) = if(n,sumdiv(n+1,i,if(i<=n,A002033(i-1))),1) \\ Michael B. Porter, Nov 01 2009, corrected by M. F. Hasler, Oct 12 2018

from functools import lru_cache
from sympy import divisors
@lru_cache(maxsize=None)
def A002033(n):
    if n <= 1:
        return 1
    return sum(A002033(i-1) for i in divisors(n+1,generator=True) if i <= n) # Chai Wah Wu, Jan 12 2022

From David Wasserman, Nov 14 2006: (Start)
a(n-1) = Sum_{i|d, i < n} a(i-1).
a(p^k-1) = 2^(k-1).
a(n-1) = A067824(n)/2 for n > 1.
a(A122408(n)-1) = A122408(n)/2. (End)
a(A025487(n)-1) = A050324(n). - R. J. Mathar, May 26 2017
a(n) = (A253249(n+1)+1)/4, n > 0. - Geoffrey Critzer, Aug 19 2020

Edited by M. F. Hasler, Oct 12 2018

A000669 Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.

Original entry on oeis.org

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, 218751, 699534, 2253676, 7305788, 23816743, 78023602, 256738751, 848152864, 2811996972, 9353366564, 31204088381, 104384620070, 350064856815, 1176693361956, 3963752002320

Offset: 1

N. J. A. Sloane and John Riordan

Also the number of unlabeled connected cographs on n nodes. - N. J. A. Sloane and Eric W. Weisstein, Oct 21 2003
A cograph is a simple graph which contains no path of length 3 as an induced subgraph. - Michael Somos, Apr 19 2014
Also called "hierarchies" by Genitrini (2016). - N. J. A. Sloane, Mar 24 2017

			G.f. = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 33*x^6 + 90*x^7 + 261*x^8 + ...
a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)). - _Michael Somos_, Jul 25 2003

N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 43.
A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999. (For definition of cograph)
A. Cayley, Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 3, p. 246.
D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 2.3.4.4 5.
L. F. Meyers, Corrections and additions to Tree Representations in Linguistics. Report 3, 1966, p. 138. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
L. F. Meyers and W. S.-Y. Wang, Tree Representations in Linguistics. Report 3, 1963, pp. 107-108. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
J. Riordan and C. E. Shannon, The number of two-terminal series-parallel networks, J. Math. Phys., 21 (1942), 83-93 (the numbers called a_n in this paper). Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 560-570.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, First 1001 terms of A000669
Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, and Martin Leuner, On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture, arXiv:1907.01073 [math.CO], 2019.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See pp. 155, 162, 165, 172. - _N. J. A. Sloane_, Apr 18 2014
Peter J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, and Mingxian Zhong, Obstructions for three-coloring graphs without induced paths on six vertices, arXiv preprint arXiv:1504.06979 [math.CO], 2015-2018.
Steven R. Finch, Series-parallel networks
Steven R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Philippe Flajolet, A Problem in Statistical Classification Theory
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72
Daniel L. Geisler, Combinatorics of Iterated Functions
A. Genitrini, Full asymptotic expansion for Polya structures, arXiv:1605.00837 [math.CO], May 03 2016, p. 9.
O. Golinelli, Asymptotic behavior of two-terminal series-parallel networks, arXiv:cond-mat/9707023 [cond-mat.stat-mech], 1997.
JiSun Huh and Seonjeong Park, Toric varieties of Schröder type, arXiv:2204.00214 [math.AG], 2022. (Table 1)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 44 [broken link].
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From _N. J. A. Sloane_, Dec 22 2012
P. A. MacMahon, Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. Page 333 gives A000084 = 2*A000669.
Arnau Mir, Francesc Rossello, and Lucia Rotger, Sound Colless-like balance indices for multifurcating trees, arXiv:1805.01329 [q-bio.PE], 2018.
V. Modrak and D. Marton, Development of Metrics and a Complexity Scale for the Topology of Assembly Supply Chains, Entropy 2013, 15, 4285-4299.
J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226.
Vlady Ravelomanana and Loys Thimonier, Asymptotic enumeration of cographs, Electronic Notes in Discrete Mathematics, Volume 7, April 2001, pp. 58-61, Theorem 4.
J. Riordan, The blossoming of Schröder's fourth problem, Acta Math., 137 (1976), 1-16. (page 6)
J. Riordan, Letter to N. J. A. Sloane, Sep. 1970
J. Riordan, Letter to N. J. A. Sloane, Nov 10 1970
Audace Amen Vioutou Dossou-Olory, and Stephan Wagner, Inducibility of Topological Trees, arXiv:1802.06696 [math.CO], 2018.
Audace Amen Vioutou Dossou-Olory, The topological trees with extremal Matula numbers, arXiv:1806.03995 [math.CO], 2018.
Wei Wang and Ximei Huang, Almost all cographs have a cospectral mate, arXiv:2507.16730 [math.CO], 2025. See pp. 6, 8.
Eric Weisstein's World of Mathematics, Series-Parallel Network
Index entries for sequences related to rooted trees
Index entries for sequences mentioned in Moon (1987)
Index entries for sequences related to trees

Equals (1/2)*A000084 for n >= 2.
Cf. A000055, A000311, A001678, A007827, A363064.
Cf. A000311, labeled hierarchies on n points.
Column 1 of A319254.
Main diagonal of A292085.
Row sums of A292086.

Method 1: a := [1,1]; for n from 3 to 30 do L := series( mul( (1-x^k)^(-a[k]),k=1..n-1)/(1-x^n)^b, x,n+1); t1 := coeff(L,x,n); R := series( 1+2*add(a[k]*x^k,k=1..n-1)+2*b*x^n, x, n+1); t2 := coeff(R,x,n); t3 := solve(t1-t2,b); a := [op(a),t3]; od: A000669 := n-> a[n];
Method 2, more efficient: with(numtheory): M := 1001; a := array(0..M); p := array(0..M); a[1] := 1; a[2] := 1; a[3] := 2; p[1] := 1; p[2] := 3; p[3] := 7;
Method 2, cont.: for m from 4 to M do t1 := divisors(m); t3 := 0; for d in t1 minus {m} do t3 := t3+d*a[d]; od: t4 := p[m-1]+2*add(p[k]*a[m-k],k=1..m-2)+t3; a[m] := t4/m; p[m] := t3+t4; od: # A000669 := n-> a[n]; A058757 := n->p[n];
# Method 3:
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(a(i)+j-1, j)*
       b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n, n-1)):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 28 2016

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[a[i]+j-1, j]* b[n-i*j, i-1], {j, 0, n/i}]]];
a[n_] := If[n<2, n, b[n, n-1]];
Array[a, 40] (* Jean-François Alcover, Jan 08 2021, after Alois P. Heinz *)

{a(n) = my(A, X); if( n<2, n>0, X = x + x * O(x^n); A = 1 / (1 - X); for(k=2, n, A /= (1 - X^k)^polcoeff(A, k)); polcoeff(A, n)/2)}; /* Michael Somos, Jul 25 2003 */

from collections import Counter
def A000669_list(n):
    list = [1] + [0] * (n - 1)
    for i in range(1, n):
        for p in Partitions(i + 1, min_length=2):
            m = Counter(p)
            list[i] += prod(binomial(list[s - 1] + m[s] - 1, m[s]) for s in m)
    return list
print(A000669_list(20)) # M. Eren Kesim, Jun 21 2021

Product_{k>0} 1/(1-x^k)^a_k = 1+x+2*Sum_{k>1} a_k*x^k.
a(n) ~ c * d^n / n^(3/2), where d = 3.560839309538943329526129172709667..., c = 0.20638144460078903185013578707202765... [Ravelomanana and Thimonier, 2001]. - Vaclav Kotesovec, Aug 25 2014
Consider a nontrivial partition p of n. For each size s of a part occurring in p, compute binomial(a(s)+m-1, m) where m is the multiplicity of s. Take the product of this expression over all s. Take the sum of this new expression over all p to obtain a(n). - Thomas Anton, Nov 22 2018

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

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

Original entry on oeis.org

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

A067824 a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).

Original entry on oeis.org

1, 2, 2, 4, 2, 6, 2, 8, 4, 6, 2, 16, 2, 6, 6, 16, 2, 16, 2, 16, 6, 6, 2, 40, 4, 6, 8, 16, 2, 26, 2, 32, 6, 6, 6, 52, 2, 6, 6, 40, 2, 26, 2, 16, 16, 6, 2, 96, 4, 16, 6, 16, 2, 40, 6, 40, 6, 6, 2, 88, 2, 6, 16, 64, 6, 26, 2, 16, 6, 26, 2, 152, 2, 6, 16, 16, 6, 26, 2, 96, 16, 6, 2, 88, 6, 6, 6, 40, 2, 88, 6, 16, 6, 6, 6, 224, 2, 16, 16, 52

Offset: 1

Reinhard Zumkeller, Feb 08 2002

nonn

By a result of Karhumaki and Lifshits, this is also the number of polynomials p(x) with coefficients in {0,1} that divide x^n-1 and such that (x^n-1)/ {(x-1)p(x)} has all coefficients in {0,1}.
The number of tiles of a discrete interval of length n (an interval of Z). - Eric H. Rivals (rivals(AT)lirmm.fr), Mar 13 2007
Bodini and Rivals proved this is the number of tiles of a discrete interval of length n and also is the number (A107067) of polynomials p(x) with coefficients in {0,1} that divide x^n-1 and such that (x^n-1)/ {(x-1)p(x)} has all coefficients in {0,1} (Bodini, Rivals, 2006). This structure of such tiles is also known as Krasner's factorization (Krasner and Ranulac, 1937). The proof also gives an algorithm to recognize if a set is a tile in optimal time and in this case, to compute the smallest interval it can tile (Bodini, Rivals, 2006). - Eric H. Rivals (rivals(AT)lirmm.fr), Mar 13 2007
Number of lone-child-avoiding rooted achiral (or generalized Bethe) trees with positive integer leaves summing to n, where a rooted tree is lone-child-avoiding if all terminal subtrees have at least two branches, and achiral if all branches directly under any given node are equal. For example, the a(6) = 6 trees are 6, (111111), (222), ((11)(11)(11)), (33), ((111)(111)). - Gus Wiseman, Jul 13 2018. Updated Aug 22 2020.
From Gus Wiseman, Aug 20 2020: (Start)
Also the number of strict chains of divisors starting with n. For example, the a(n) chains for n = 1, 2, 4, 6, 8, 12 are:
  1  2    4      6      8        12
     2/1  4/1    6/1    8/1      12/1
          4/2    6/2    8/2      12/2
          4/2/1  6/3    8/4      12/3
                 6/2/1  8/2/1    12/4
                 6/3/1  8/4/1    12/6
                        8/4/2    12/2/1
                        8/4/2/1  12/3/1
                                 12/4/1
                                 12/4/2
                                 12/6/1
                                 12/6/2
                                 12/6/3
                                 12/4/2/1
                                 12/6/2/1
                                 12/6/3/1
(End)
a(n) is the number of chains including n of the divisor lattice of divisors of n, which is to say, a(n) is the number of (d_1,d_2,...,d_k) such that d_1 < d_2 < ... < d_k = n and d_i divides d_{i+1} for 1 <= i <= k-1. Using this definition, the recurrence a(n) = 1 + Sum_{0 < d < n, d|n} a(d) is evident by enumerating the preceding element of n in the chains. If we count instead the chains whose LCM of members is n, then a(1) would be 2 because the empty chain is included, and we would obtain 2*A074206(n). - Jianing Song, Aug 21 2024

			a(12) = 1 + a(6) + a(4) + a(3) + a(2) + a(1)
= 1+(1+a(3)+a(2)+a(1))+(1+a(2)+a(1))+(1+a(1))+(1+a(1))+(1)
= 1+(1+(1+a(1))+(1+a(1))+1)+(1+(1+a(1))+1)+(1+1)+(1+1)+(1)
= 1+(1+(1+1)+(1+1)+1)+(1+(1+1)+1)+(1+1)+(1+1)+(1)
= 1 + 6 + 4 + 2 + 2 + 1 = 16.

Olivier Bodini and Eric Rivals. Tiling an Interval of the Discrete Line. In M. Lewenstein and G. Valiente, editors, Proc. of the 17th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 4009 of Lecture Notes in Computer Science, pages 117-128. Springer Verlag, 2006.
Juhani Karhumaki, Yury Lifshits and Wojciech Rytter, Tiling Periodicity, in Combinatorial Pattern Matching, Lecture Notes in Computer Science, Volume 4580/2007, Springer-Verlag.

Reinhard Zumkeller, Table = of n, a(n) for n = 1..10000
Olivier Bodini and Eric Rivals, Tiling an Interval of the Discrete Line
Thomas Fink, Recursively divisible numbers, arXiv:1912.07979 [math.NT], 2019. See Table 1 p. 8.
T. M. A. Fink, Properties of the recursive divisor function and the number of ordered factorizations, arXiv:2307.09140 [math.NT], 2023.
Michael Greene and Robin Michaels, One Dimensional Tilings, Eureka (Cambridge) 54 (1996), 4-13.
G. Hajos, Sur le problème de factorisation des groupes cycliques, Acta Math. Acad. Sci. Hung., 1:189-195, 1950.
J. Karhumaki and Y. Lifshits, Tiling periodicity.
M. Krasner and B. Ranulac, Sur une propriété des polynomes de la division du cercle, Comptes Rendus Académie des Sciences Paris, 240:397-399, 1937.
Eric H. Rivals, Tiling
Index entries for sequences computed from exponents in factorization of n

Cf. A000005, A001678, A003238, A107067, A107748, A167865, A316782.
Cf. A122408 (fixed points).
Inverse Möbius transform of A074206.
A001055 counts factorizations.
A008480 counts maximal chains of divisors starting with n.
A074206 counts chains of divisors from n to 1.
A253249 counts nonempty chains of divisors.
A337070 counts chains of divisors starting with A006939(n).
A337071 counts chains of divisors starting with n!.
A337256 counts chains of divisors.
Cf. A001221, A001222, A002033, A124010, A337074, A337105, A378223, A378225 (Dirichlet inverse).

a067824 n = 1 + sum (map a067824 [d | d <- [1..n-1], mod n d == 0])
-- Reinhard Zumkeller, Oct 13 2011

a:= proc(n) option remember;
      1+add(a(d), d=numtheory[divisors](n) minus {n})
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 17 2021

a[1]=1; a[n_] := a[n] = 1+Sum[If[Mod[n,d]==0, a[d], 0], {d, 1, n-1}]; Array[a,100] (* Jean-François Alcover, Apr 28 2011 *)

A=vector(100);A[1]=1; for(n=2,#A,A[n]=1+sumdiv(n,d,A[d])); A \\ Charles R Greathouse IV, Nov 20 2012

a(n) = 2*A074206(n), n>1. - Vladeta Jovovic, Jul 03 2005
a(p^k) = 2^k for primes p. - Reinhard Zumkeller, Sep 03 2006
a(n) = Sum_{d|n} A002033(d-1) = Sum_{d|n} A074206(d). - Gus Wiseman, Jul 13 2018
Dirichlet g.f.: zeta(s) / (2 - zeta(s)). - Álvar Ibeas, Dec 30 2018
G.f. A(x) satisfies: A(x) = x/(1 - x) + Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, May 18 2019

Entry revised by N. J. A. Sloane, Aug 27 2006

A167865 Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 4, 1, 3, 3, 3, 1, 5, 1, 5, 4, 3, 1, 6, 2, 5, 4, 5, 1, 9, 1, 6, 4, 4, 4, 8, 1, 6, 6, 7, 1, 11, 1, 8, 8, 4, 1, 10, 3, 10, 5, 8, 1, 11, 4, 10, 7, 6, 1, 13, 1, 10, 11, 7, 6, 15, 1, 9, 5, 11, 1, 14, 1, 9, 12, 8, 5, 15, 1, 16, 9, 8, 1, 18, 5, 12, 7, 10, 1, 21, 7, 13, 11, 5

Offset: 0

Max Alekseyev, Nov 13 2009

Number of lone-child-avoiding achiral rooted trees with n + 1 vertices, where a rooted tree is lone-child-avoiding if all terminal subtrees have at least two branches, and achiral if all branches directly under any given vertex are equal. The Matula-Goebel numbers of these trees are given by A331967. - Gus Wiseman, Feb 07 2020

			a(12) = 4: [12], [10,2], [9,3], [8,4].
a(14) = 3: [14], [12,2], [8,4,2].
a(18) = 5: [18], [16,2], [15,3], [12,6], [12,4,2].
From _Gus Wiseman_, Jul 13 2018: (Start)
The a(36) = 8 lone-child-avoiding achiral rooted trees with 37 vertices:
  (oooooooooooooooooooooooooooooooooooo)
  ((oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo))
  ((ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo))
  ((ooooo)(ooooo)(ooooo)(ooooo)(ooooo)(ooooo))
  ((oooooooo)(oooooooo)(oooooooo)(oooooooo))
  (((ooo)(ooo))((ooo)(ooo))((ooo)(ooo))((ooo)(ooo)))
  ((ooooooooooo)(ooooooooooo)(ooooooooooo))
  ((ooooooooooooooooo)(ooooooooooooooooo))
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Cf. A001678, A067824, A122651, A167439, A167865, A167866, A184998, A316782.
The semi-achiral version is A320268.
Matula-Goebel numbers of these trees are A331967.
The semi-lone-child-avoiding version is A331991.
Achiral rooted trees are counted by A003238.
Cf. A000081, A000669, A289079, A320222, A331912, A331933, A331936, A331992.

with(numtheory):
a:= proc(n) option remember;
      `if`(n=0, 1, add(a((n-d)/d), d=divisors(n) minus{1}))
    end:
seq(a(n), n=0..200);  # Alois P. Heinz, Mar 28 2011

a[0] = 1; a[n_] := a[n] = DivisorSum[n, a[(n-#)/#]&, #>1&]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 07 2015 *)

{ A167865(n) = if(n==0,return(1)); sumdiv(n,d, if(d>1, A167865((n-d)\d) ) ) }

a(0) = 1 and for n>=1, a(n) = Sum_{d|n, d>1} a((n-d)/d).

G.f. A(x) satisfies: A(x) = 1 + x^2*A(x^2) + x^3*A(x^3) + x^4*A(x^4) + ... - Ilya Gutkovskiy, May 09 2019

A290689 Number of transitive rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 88, 143, 229, 370, 592, 955, 1527, 2457, 3929, 6304, 10081

Offset: 1

Gus Wiseman, Oct 19 2017

A rooted tree is transitive if every proper terminal subtree is also a branch of the root. First differs from A206139 at a(13) = 143.

Regarding the notation, a rooted tree is a finite multiset of rooted trees. For example, the rooted tree (o(o)(oo)) is short for {{},{{}},{{},{}}}. Each "o" is a leaf. Each pair of parentheses corresponds to a non-leaf node (such as the root). Its contents "(...)" represent a branch. - Gus Wiseman, Nov 16 2024

			The a(7) = 8 7-node transitive rooted trees are: (o(oooo)), (oo(ooo)), (o(o)((o))), (o(o)(oo)), (ooo(oo)), (oo(o)(o)), (oooo(o)), (oooooo).

Robert P. P. McKone, The transitive rooted trees with n=1 to n=22 nodes.

The restriction to identity trees (A004111) is A279861, ranks A290760.
These trees are ranked by A290822.
The anti-transitive version is A306844, ranks A324758.
The totally transitive case is A318185 (by leaves A318187), ranks A318186.
A version for integer partitions is A324753, for subsets A324736.
The ordered version is A358453, ranks A358457, undirected A358454.
Cf. A000081, A001192, A001678, A324770, A324969, A325705, A358455, A358460.

nn=18;
rtall[n_]:=If[n===1,{{}},Module[{cas},Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])]]];
Table[Length[Select[rtall[n],Complement[Union@@#,#]==={}&]],{n,nn}]

a(20) from Robert Price, Sep 13 2018

a(21)-a(22) from Robert P. P. McKone, Dec 16 2023

A141268 Number of phylogenetic rooted trees with n unlabeled objects.

Original entry on oeis.org

1, 2, 4, 11, 30, 96, 308, 1052, 3648, 13003, 47006, 172605, 640662, 2402388, 9082538, 34590673, 132566826, 510904724, 1978728356, 7697565819, 30063818314, 117840547815, 463405921002, 1827768388175, 7228779397588, 28661434308095, 113903170011006, 453632267633931

Offset: 1

Thomas Wieder, Jun 20 2008

nonn

Unlabeled analog of A005804 = Phylogenetic trees with n labels.
From Gus Wiseman, Jul 31 2018: (Start)
a(n) is the number of series-reduced rooted trees whose leaves form an integer partition of n. For example, the following are the a(4) = 11 series-reduced rooted trees whose leaves form an integer partition of 4.
  4,
  (13),
  (22),
  (112), (1(12)), (2(11)),
  (1111), (11(11)), (1(1(11))), (1(111)), ((11)(11)).
(End)

			For n=4 we have A141268(4)=11 because
Set(Set(Z),Set(Z),Set(Z,Z)),
Set(Set(Z),Set(Set(Z),Set(Z,Z))),
Set(Z,Z,Z,Z),
Set(Set(Z,Z),Set(Z,Z)),
Set(Set(Set(Z),Set(Z)),Set(Z,Z)),
Set(Set(Z),Set(Z),Set(Set(Z),Set(Z))),
Set(Set(Z),Set(Z),Set(Z),Set(Z)),
Set(Set(Z),Set(Set(Z),Set(Z),Set(Z))),
Set(Set(Set(Z),Set(Z)),Set(Set(Z),Set(Z))),
Set(Set(Z),Set(Z,Z,Z)),
Set(Set(Z),Set(Set(Z),Set(Set(Z),Set(Z))))

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Moshe Klein and A. Yu. Khrennikov, Recursion over partitions, P-Adic Numbers, Ultrametric Analysis, and Applications 6.4 (2014): 303-309. See sp_n.

Cf. A000081, A000311, A000669, A001678, A005804, A141268, A292504, A300660, A316655.

with(combstruct): A141268 := [H, {H=Union(Set(Z,card>=1),Set(H,card>=2))}, unlabelled]; seq(count(A141268, size=j), j=1..20);
# second Maple program:
b:= proc(n,i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)*binomial(a(i)+j-1, j), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, 1+b(n, n-1)):
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 18 2018

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
t[n_]:=t[n]=If[PrimeQ[n],{n},Join@@Table[Union[Sort/@Tuples[t/@fac]],{fac,Select[facs[n],Length[#]>1&]}]];
Table[Sum[Length[t[Times@@Prime/@ptn]],{ptn,IntegerPartitions[n]}],{n,7}] (* Gus Wiseman, Jul 31 2018 *)
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0,
     Sum[b[n-i*j, i-1]*Binomial[a[i]+j-1, j], {j, 0, n/i}]]];
a[n_] := If[n < 2, n, 1 + b[n, n-1]];
Array[a, 30] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=vector(n)); for(n=1, n, v[n]=1 + EulerT(v[1..n])[n]); v} \\ Andrew Howroyd, Oct 26 2018

a(n) ~ c * d^n / n^(3/2), where d = 4.210216501727104448901818751..., c = 0.21649387167268793159311306... . - Vaclav Kotesovec, Sep 04 2014

Offset corrected and more terms from Alois P. Heinz, Apr 21 2012

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

A032305 Number of rooted trees where any 2 subtrees extending from the same node have a different number of nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 12, 25, 51, 111, 240, 533, 1181, 2671, 6014, 13795, 31480, 72905, 168361, 393077, 914784, 2150810, 5040953, 11914240, 28089793, 66702160, 158013093, 376777192, 896262811, 2144279852, 5120176632, 12286984432, 29428496034, 70815501209

Offset: 1

Christian G. Bower

nonn

			The a(6) = 6 fully unbalanced trees: (((((o))))), (((o(o)))), ((o((o)))), (o(((o)))), (o(o(o))), ((o)((o))). - _Gus Wiseman_, Jan 10 2018

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Gus Wiseman, Illustration of the first 8 terms of A032305.
Index entries for sequences related to rooted trees

Cf. A000081, A001678, A003238, A004111, A213920, A273873, A290689, A291443, A297571.

Column k=1 of A318753.

A:= proc(n) if n<=1 then x else convert(series(x* (product(1+ coeff(A(n-1), x,i)*x^i, i=1..n-1)), x=0, n+1), polynom) fi end: a:= n-> coeff(A(n), x,n): seq(a(n), n=1..31);  # Alois P. Heinz, Aug 22 2008
# second Maple program:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(j=0, 1, g((i-1)$2))*g(n-i*j, i-1), j=0..min(1, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=1..35);  # Alois P. Heinz, Mar 04 2013

nn=30;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0 == Series[f[x]-x Product[1+a[i]x^i,{i,1,nn}],{x,0,nn}],x];Table[a[n],{n,1,nn}]/.sol  (* Geoffrey Critzer, Nov 17 2012 *)
allnim[n_]:=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[allnim/@c]],UnsameQ@@(Count[#,_List,{0,Infinity}]&/@#)&]]/@IntegerPartitions[n-1]];
Table[Length[allnim[n]],{n,15}] (* Gus Wiseman, Jan 10 2018 *)
g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0,
     Sum[If[j == 0, 1, g[i-1, i-1]]*g[n-i*j, i-1], {j, 0, Min[1, n/i]}]]];
a[n_] := g[n-1, n-1];
Array[a, 35] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

a(n)=polcoeff(x*prod(i=1,n-1,1+a(i)*x^i)+x*O(x^n),n)

Shifts left under "EFK" (unordered, size, unlabeled) transform.
G.f.: A(x) = x*Product_{n>=1} (1+a(n)*x^n) = Sum_{n>=1} a(n)*x^n. - Paul D. Hanna, Apr 07 2004
Lim_{n->infinity} a(n)^(1/n) = 2.5119824... - Vaclav Kotesovec, Nov 20 2019
G.f.: x * exp(Sum_{n>=1} Sum_{k>=1} (-1)^(k+1) * a(n)^k * x^(n*k) / k). - Ilya Gutkovskiy, Jun 30 2021

A079500 Number of compositions of the integer n in which the first part is >= the other parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 8, 14, 24, 43, 77, 140, 256, 472, 874, 1628, 3045, 5719, 10780, 20388, 38674, 73562, 140268, 268066, 513350, 984911, 1892875, 3643570, 7023562, 13557020, 26200182, 50691978, 98182666, 190353370, 369393466, 717457656, 1394632365, 2713061899

Offset: 0

Arnold Knopfmacher, Jan 21 2003

nonn

Essentially the same as A007059: a(n) = A007059(n+1).
In lunar arithmetic in base 2, this is the number of lunar divisors of the number 111...1 (with n 1's). E.g., 1111 has a(4) = 5 divisors (see A048888). - N. J. A. Sloane, Feb 23 2011.
First differences of A186537. - N. J. A. Sloane, Feb 23 2011
Number of balanced ordered rooted trees with n non-root nodes (see A048816 for unordered balanced trees); see example. The compositions are obtained from the level sequences by identifying a length-k run of (non-root) levels [t, t+1, t+2, ..., t+k-1] with a part k. - Joerg Arndt, Jul 20 2014

			From _Joerg Arndt_, Dec 29 2012: (Start)
There are a(7)=24 compositions p(1)+p(2)+...+p(m)=7 such that p(k) <= p(1):
[ 1]  [ 1 1 1 1 1 1 1 ]
[ 2]  [ 2 1 1 1 1 1 ]
[ 3]  [ 2 1 1 1 2 ]
[ 4]  [ 2 1 1 2 1 ]
[ 5]  [ 2 1 2 1 1 ]
[ 6]  [ 2 1 2 2 ]
[ 7]  [ 2 2 1 1 1 ]
[ 8]  [ 2 2 1 2 ]
[ 9]  [ 2 2 2 1 ]
[10]  [ 3 1 1 1 1 ]
[11]  [ 3 1 1 2 ]
[12]  [ 3 1 2 1 ]
[13]  [ 3 1 3 ]
[14]  [ 3 2 1 1 ]
[15]  [ 3 2 2 ]
[16]  [ 3 3 1 ]
[17]  [ 4 1 1 1 ]
[18]  [ 4 1 2 ]
[19]  [ 4 2 1 ]
[20]  [ 4 3 ]
[21]  [ 5 1 1 ]
[22]  [ 5 2 ]
[23]  [ 6 1 ]
[24]  [ 7 ]
(End)
From _Joerg Arndt_, Jul 20 2014: (Start)
The a(7) = 24 balanced ordered rooted trees with 7 non-root nodes are, as level sequences (of the pre-order walk):
01:  [ 0 1 1 1 1 1 1 1 ]
02:  [ 0 1 2 1 2 1 2 2 ]
03:  [ 0 1 2 1 2 2 1 2 ]
04:  [ 0 1 2 1 2 2 2 2 ]
05:  [ 0 1 2 2 1 2 1 2 ]
06:  [ 0 1 2 2 1 2 2 2 ]
07:  [ 0 1 2 2 2 1 2 2 ]
08:  [ 0 1 2 2 2 2 1 2 ]
09:  [ 0 1 2 2 2 2 2 2 ]
10:  [ 0 1 2 3 1 2 3 3 ]
11:  [ 0 1 2 3 2 3 2 3 ]
12:  [ 0 1 2 3 2 3 3 3 ]
13:  [ 0 1 2 3 3 1 2 3 ]
14:  [ 0 1 2 3 3 2 3 3 ]
15:  [ 0 1 2 3 3 3 2 3 ]
16:  [ 0 1 2 3 3 3 3 3 ]
17:  [ 0 1 2 3 4 2 3 4 ]
18:  [ 0 1 2 3 4 3 4 4 ]
19:  [ 0 1 2 3 4 4 3 4 ]
20:  [ 0 1 2 3 4 4 4 4 ]
21:  [ 0 1 2 3 4 5 4 5 ]
22:  [ 0 1 2 3 4 5 5 5 ]
23:  [ 0 1 2 3 4 5 6 6 ]
24:  [ 0 1 2 3 4 5 6 7 ]
(End)
From _Gus Wiseman_, Oct 07 2018: (Start)
The a(0) = 1 through a(6) = 14 balanced rooted plane trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)      (oooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))     ((ooooo))
                 (((o)))  (((oo)))   (((ooo)))    (((oooo)))
                          ((o)(o))   ((o)(oo))    ((o)(ooo))
                          ((((o))))  ((oo)(o))    ((oo)(oo))
                                     ((((oo))))   ((ooo)(o))
                                     (((o)(o)))   ((((ooo))))
                                     (((((o)))))  (((o)(oo)))
                                                  (((oo)(o)))
                                                  ((o)(o)(o))
                                                  (((((oo)))))
                                                  ((((o)(o))))
                                                  (((o))((o)))
                                                  ((((((o))))))
(End)

Arnold Knopfmacher and Neville Robbins, Compositions with parts constrained by the leading summand, Ars Combin. 76 (2005), 287-295.

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 400 terms from T. D. Noe)
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, arXiv:1107.1130 [math.NT], 2011. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
Srecko Brlek, Andrea Frosini, Simone Rinaldi, and Laurent Vuillon, Tilings by translation: enumeration by a rational language approach, The Electronic Journal of Combinatorics, vol.13, (2006).
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.1.
R. Kemp, Balanced ordered trees, Random Structures Algorithms, 5 (1994), pp. 99-121.
Index entries for sequences related to dismal (or lunar) arithmetic

Cf. A188541.
Cf. A000081 A000311, A001678, A120803, A320154, A320160, A316624, A320169.
Cf. A092921.

M:=101:
t1:=add( (1-x)*x^k/(1-2*x+x^k), k=1..M):
series(t1,x,M-1);
seriestolist(%);
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
      `if`(m=0, add(b(n-j, j), j=1..n),
      add(b(n-j, min(n-j, m)), j=1..min(n, m))))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, May 01 2014

nn=36;CoefficientList[Series[Sum[x^i/(1-(x-x^(i+1))/(1-x)),{i,0,nn}],{x,0,nn}],x]  (* Geoffrey Critzer, Mar 12 2013 *)
b[n_, m_] := b[n, m] = If[n==0, 1, If[m==0, Sum[b[n-j, j], {j, 1, n}], Sum[ b[n-j, Min[n-j, m]], {j, 1, Min[n, m]}]]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 23 2015, after Alois P. Heinz *)

G.f.: (1-z) * Sum_{k>=0} z^k/(1 - 2*z + z^(k+1)).
a(n) = A048888(n) - 1.
This is a subsequence of A067399: a(n) = A067399(2^n-1).
G.f.: -((1 + x^2 + 1/(x-1))/x)*( 1 + x*(x-1)^3*(1-x+x^3)/( Q(0) - x*(x-1)^3*(1-x+x^3)) ), where Q(k) = (x+1)*(2*x-1)*(1-x)^2 + x^(k+2)*(x+x^2+x^3-2*x^4-1 - x^(k+3) + x^(k+5)) - x*(-1+2*x-x^(k+3))*(1-2*x+x^2+x^(k+4)-x^(k+5))*(-1+4*x-5*x^2+2*x^3 - x^(k+2)- x^(k+5) + 2*x^(k+3) - x^(2*k+5) + x^(2*k+6))/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Dec 14 2013
a(n) = Sum_{j=1..n} F(j, n+1-j), where F(n,k) is the n-th k-generalized Fibonacci number A092921(k,n). - Gregory L. Simay, Aug 21 2022

Offset corrected by N. J. A. Sloane, Feb 23 2011
More terms from N. J. A. Sloane, Feb 24 2011
Further edits (required in order to clarify the definition - is the first part >= the rest. or only > the rest? Answer: the former; for the latter, see A007059) by N. J. A. Sloane, May 08 2011

cp's OEIS Frontend

A002033 Number of perfect partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A000669 Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

A067824 a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A167865 Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica