A000081 -id:A000081 - cp's OEIS frontend

A319312 Number of series-reduced rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.

1, 3, 7, 22, 67, 242, 885, 3456, 13761, 56342, 234269, 989335, 4225341, 18231145, 79321931, 347676128, 1533613723, 6803017863, 30328303589, 135808891308, 610582497919, 2755053631909, 12472134557093, 56630659451541, 257841726747551, 1176927093597201

Offset: 1

Gus Wiseman, Sep 17 2018

nonn

Also the number of orderless tree-factorizations of Heinz numbers of integer partitions of n.

Also the number of phylogenetic trees on a multiset of labels summing to n.

			The a(3) = 7 trees:
  (3)    (21)        (111)
       ((1)(2))    ((1)(11))
                  ((1)(1)(1))
                 ((1)((1)(1)))

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

Cf. A000081, A000311, A000669, A001678, A005804, A141268, A292504, A300660, A316653, A316654, A316656.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
phyfacs[n_]:=Prepend[Join@@Table[Union[Sort/@Tuples[phyfacs/@f]],{f,Select[facs[n],Length[#]>1&]}],n];
Table[Sum[Length[phyfacs[Times@@Prime/@m]],{m,IntegerPartitions[n]}],{n,6}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(v=[]); for(n=1, n, v=concat(v, numbpart(n) + EulerT(concat(v,[0]))[n])); v} \\ Andrew Howroyd, Sep 18 2018

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

A000625 Number of n-node steric rooted ternary trees; number of n carbon alkyl radicals C(n)H(2n+1) taking stereoisomers into account.

Original entry on oeis.org

1, 1, 1, 2, 5, 11, 28, 74, 199, 551, 1553, 4436, 12832, 37496, 110500, 328092, 980491, 2946889, 8901891, 27012286, 82300275, 251670563, 772160922, 2376294040, 7333282754, 22688455980, 70361242924, 218679264772, 681018679604, 2124842137550, 6641338630714, 20792003301836

Offset: 0

N. J. A. Sloane

Nodes are unlabeled, each node has out-degree <= 3.
Steric, or including stereoisomers, means that the children of a node are taken in a certain cyclic order. If the children are rotated it is still the same tree, but any other permutation yields a different tree. See A000598 for the analogous sequence with stereoisomers not counted.
Other descriptions of this sequence: steric planted trees with n nodes; total number of monosubstituted alkanes C(n)H(2n+1)-X with n carbon atoms.
Let the entries in the nine columns of Blair and Henze's Table I (JACS 54 (1932), p. 1098) be denoted by Ps(n), Pn(n), Ss(n), Sn(n), Ts(n), Tn(n), As(n), An(n), T(n) respectively (here P = Primary, S = Secondary, T = Tertiary, s = stereoisomers, n = non-stereoisomers and the last column T(n) gives total).
Then Ps (and As) = A000620, Pn (and An, Sn) = A000621, Ss = A000622, Ts = A000623, Tn = A000624, T = this sequence. Recurrences generating these sequences are given in the Maple program in A000620.

J. K. Percus, Combinatorial Methods, Lecture Notes, 1967-1968, Courant Institute, New York University, 212pp. See pp. 64-65.
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).

Vaclav Kotesovec, Table of n, a(n) for n = 0..1930 (first 200 terms from T. D. Noe)
C. M. Blair and H. R. Henze, The number of stereoisomeric and non-stereoisomeric mono-substitution products of the paraffins, J. Amer. Chem. Soc., 54 (3) (1932), 1098-1106.
C. M. Blair and H. R. Henze, The number of stereoisomeric and non-stereoisomeric mono-substitution products of the paraffins, J. Amer. Chem. Soc., 54 (3) (1932), 1098-1105. (Annotated scanned copy)
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443, Eq. (25).
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443, Eq. (25). (Annotated scanned copy)
R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [Annotated scanned copy] See p. 44.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355-361
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355-361. (Annotated scanned copy)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000598, A000602, A000620-A000624, A000628, A010732, A010733, A086194, A086200, A239803, A239810.

A := 1; f := proc(n) global A; coeff(series( 1+(1/3)*x*(A^3+2*subs(x=x^3,A)), x, n+1), x, n); end; for n from 1 to 50 do A := series(A+f(n)*x^n,x,n +1); od: A;
A000625 := proc(n)
    local j,i,a ;
    option remember;
    if n <= 1 then
        1 ;
    else
        a :=0 ;
        for j from 1 to n-1 do
            a := a+ j*procname(j)*add(procname(i)*procname(n-j-i-1),i=0..n-j-1) ;
        end do:
        if modp(n-1,3) = 0 then
            a := a+2*(n-1)*procname((n-1)/3)/3 ;
        end if;
        a/ (n-1) ;
    end if;
end proc:
seq(A000625(n),n=0..30) ;

m = 31; c[0] = 1; gf[x_] = Sum[c[k] x^k, {k, 0, m}]; cc = Array[c, m]; coes = CoefficientList[ Series[gf[x] - 1 - (x*(gf[x]^3 + 2*gf[x^3])/3), {x, 0, m}], x] // Rest; Prepend[cc /. Solve[ Thread[ coes == 0], cc][[1]], 1]
(* Jean-François Alcover, Jun 24 2011 *)
a[0] = a[1] = 1; a[n_Integer] := a[n] = (Sum[j*a[j]*Sum[a[i]*a[n-i-j-1], {i, 0, n-j-1}], {j, 1, n-1}] + (2/3)*(n-1)*a[(n-1)/3])/(n-1); a[] = 0; Table[a[n], {n, 0, 31}] (* _Jean-François Alcover, Apr 21 2016, after Emeric Deutsch *)
terms = 32; A[] = 0; Do[A[x] = Normal[1 + x*(A[x]^3 + 2*A[x^3])/3 + O[x]^terms], terms]; CoefficientList[A[x], x] (* Jean-François Alcover, Apr 22 2016, updated Jan 11 2018 *)

a(n) = if(n, my(v=vector(n+1)); v[1]=1; v[2]=1; for(k=1, n-1, v[k+2] = sum(j=1, k, j*v[j+1]*(sum(i=0, k-j, v[i+1]*v[k-j-i+1])))/k + (2/3)*if(k%3, 0, v[k/3+1])); v[n+1], 1) \\ Jianing Song, Feb 17 2019

G.f. A(x) = 1 + x + x^2 + 2*x^3 + 5*x^4 + 11*x^5 + 28*x^6 + ... satisfies A(x) = 1 + x*(A(x)^3 + 2*A(x^3))/3.
a(0) = a(1) = 1; a(n+1) = 2*a(n/3)/3 + (Sum_{j=1..n} j*a(j)*(Sum_{i=1..n-j} a(i)*a(n-j-i)))/n for n >= 1, where a(k) = 0 if k not an integer (essentially eq (4) in the Robinson et al. paper). - Emeric Deutsch, May 16 2004
a(n) ~ c * b^n / n^(3/2), where b = 3.287112055584474991259... (see A239803), c = 0.346304267394183622435... (see A239810). - Vaclav Kotesovec, Mar 27 2014

Additional comments from Bruce Corrigan, Nov 04 2002

A317713 Number of distinct terminal subtrees of the rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 3, 2, 3, 4, 5, 3, 4, 3, 4, 2, 4, 3, 3, 4, 4, 5, 4, 3, 4, 4, 3, 3, 5, 4, 6, 2, 5, 4, 5, 3, 4, 3, 4, 4, 5, 4, 4, 5, 4, 4, 5, 3, 3, 4, 5, 4, 3, 3, 5, 3, 4, 5, 5, 4, 4, 6, 4, 2, 5, 5, 4, 4, 4, 5, 5, 3, 5, 4, 4, 3, 6, 4, 6, 4, 3, 5, 5, 4, 6, 4, 5, 5, 4, 4, 5, 4, 6, 5, 5, 3, 5, 3, 5, 4, 5, 5, 4, 4, 5, 3, 4, 3

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

			20 is the Matula-Goebel number of the tree (oo((o))), which has 4 distinct terminal subtrees: {(oo((o))), ((o)), (o), o}. So a(20) = 4.
See also illustrations in A061773.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to Matula-Göbel numbers

One more than A324923.

Cf. A000081, A007097, A049076, A061773, A061775, A076146, A109082, A109129, A206491, A303431, A316476.

ids[n_]:=Union@@FixedPointList[Union@@(Cases[If[#==1,{},FactorInteger[#]],{p_,_}:>PrimePi[p]]&/@#)&,{n}];
Table[Length[ids[n]],{n,100}]

A006530(n) = if(1==n, n, my(f=factor(n)); f[#f~, 1]);
A324923(n) = { my(lista = List([]), gpf, i); while(n > 1, gpf=A006530(n); i = primepi(gpf); n /= gpf; n *= i; listput(lista,i)); #Set(lista); }; \\ Antti Karttunen, Oct 23 2023
A317713(n) = (1+A324923(n)); \\ Antti Karttunen, Oct 23 2023

a(n) = 1+A324923(n). - Antti Karttunen, Oct 23 2023

Data section extended up to a(108) by Antti Karttunen, Oct 23 2023

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 14, 34, 95, 280, 854, 2694, 8714, 28640, 95640, 323396, 1105335, 3813798, 13269146, 46509358, 164107650, 582538732, 2079165208, 7457847082, 26873059986, 97239032056, 353218528324, 1287658723550, 4709785569184

Offset: 0

N. J. A. Sloane

Noncrossing handshakes of 2(n-1) people (each using only one hand) on round table, up to rotations - Antti Karttunen, Sep 03 2000
Equivalently, the number of noncrossing partitions up to rotation composed of n-1 blocks of size 2. - Andrew Howroyd, May 04 2018
a(n), n>2, is also the number of oriented cacti on n-1 unlabeled nodes with all cutpoints of separation degree 2, i.e. ones shared only by two (cyclic) blocks. These are digraphs (without loops) that have a unique Eulerian tour. Such digraphs with labeled nodes are enumerated by A102693. - Valery A. Liskovets, Oct 19 2005
Labeled plane trees are counted by A006963. - David Callan, Aug 19 2014
This sequence is similar to A000055 but those trees are not embedded in a plane. - Michael Somos, Aug 19 2014

			G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 14*x^7 + 34*x^8 + 95*x^9 + ...
a(7) = 14 = 11 + 3 because there are 11 trees with 7 nodes but three of them can be embedded in a plane in two ways. These three trees have degree sequences 4221111, 3321111, 3222111, where there are two trees with each degree sequence but in the first, the two nodes of degree two are adjacent, in the second, the two nodes of degree three are adjacent, and in the third, the node of degree three is adjacent to two nodes of degree two. - _Michael Somos_, Aug 19 2014

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 304.
A. Errera, De quelques problèmes d'analysis situs, Comptes Rend. Congr. Nat. Sci. Bruxelles, (1930), 106-110.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.26).
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..200
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 285 (4.1.26), 291 (4.1.48)
CombOS - Combinatorial Object Server, Generate free plane trees
R. Cori and M. Marcus, Counting non-isomorphic chord diagrams, Theor. Comp. Sci. 204 (1998) 55-75, Corollary 5.2.
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Errera, Reviews of two articles on Analysis Situs, from Fortschritte [Annotated scanned copy]
D. Feldman, Counting plane trees, Unpublished manuscript, 1992. (Annotated scanned copy)
Bernold Fiedler, Scalar polynomial vector fields in real and complex time, arXiv:2410.05043 [math.DS], 2024. See pp. 21, 50.
Bernold Fiedler, Real-time blow-up and connection graphs of rational vector fields on the Riemann sphere, arXiv:2504.20503 [math.DS], 2025. See p. 23.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335. (Annotated scanned copy)
G. Labelle, Sur la symétrie et l'asymétrie des structures combinatoires, Theor. Comput. Sci. 117, No. 1-2, 3-22 (1993).
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Torsten Mütze, Proof of the middle levels conjecture, arXiv preprint arXiv:1404.4442 [math.CO], 2014.
Torsten Mütze, A book proof of the middle levels theorem, arXiv:2306.13019 [math.CO], 2023.
Torsten Mütze and Franziska Weber, Construction of 2-factors in the middle layer of the discrete cube, arXiv preprint arXiv:1111.2413 [math.CO], 2011.
Torsten Mütze and F. Weber, Construction of 2-factors in the middle layer of the discrete cube, Journal of Combinatorial Theory, Series A, 119(8) (2012), 1832-1855.
J. Sawada, Generating rooted and free plane trees, ACM Transactions on Algorithms, Vol. 2 No. 1 (2006), 1-13.
Seunghyun Seo and Heesung Shin, Two involutions on vertices of ordered trees, FPSAC'02 (2002). (see p_n).
Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233. See Table 1.
D. W. Walkup, The number of plane trees, Mathematika, vol. 19, No. 2 (1972), 200-204.
Index entries for sequences related to trees

Column k=2 of A303694 and A303864.

Cf. A000055, A000108, A002996, A003239, A005354, A057502, A061417, A064640.

with (powseries): with (combstruct): n := 27: Order := n+2: sys := {C = Cycle(B), B = Union(Z,Prod(B,B))}: G003239 := (convert(gfseries(sys,unlabeled,x) [C(x)], polynom)) / x: G000108 := convert(taylor((1-sqrt(1-4*x)) / (2*x),x),polynom): G002995 := 1 + G003239 + (eval(G000108,x=x^2) - G000108^2)/2: A002995 := 1,1,1,seq(coeff(G002995,x^i),i=1..n); # Ulrich Schimke, Apr 05 2002
with(combinat): with(numtheory): m := 2: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od : # Zerinvary Lajos, Dec 01 2006

a[0] = a[1] = 1; a[n_] := (1/(2*(n-1)))*Sum[ EulerPhi[(n-1)/d]*Binomial[2*d, d], {d, Divisors[n-1]}] - CatalanNumber[n-1]/2 + If[ EvenQ[n], CatalanNumber[n/2-1]/2, 0]; Table[ a[n], {n, 0, 29}] (* Jean-François Alcover, Mar 07 2012, from formula *)

catalan(n) = binomial(2*n, n)/(n+1);
a(n) = if (n<2, 1, n--; sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/(2*n) - catalan(n)/2 + if ((n-1) % 2, 0, catalan((n-1)/2)/2)); \\ Michel Marcus, Jan 23 2016

G.f.: 1+B(x)+(C(x^2)-C(x)^2)/2 where B is g.f. of A003239 and C is g.f. of A000108(n-1).

a(n) = 1/(2*(n-1))*sum{d|(n-1)}(phi((n-1)/d)*binomial(2d, d)) - A000108(n-1)/2 + (if n is even) A000108(n/2-1)/2.

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

Name corrected ("labeled" --> "unlabeled") by David Callan, Aug 19 2014

A061773 Triangle in which n-th row lists Matula-Goebel numbers for all rooted trees with n nodes.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 19, 15, 18, 20, 21, 22, 23, 24, 26, 28, 29, 31, 32, 34, 37, 38, 41, 43, 53, 59, 67, 25, 27, 30, 33, 35, 36, 39, 40, 42, 44, 46, 47, 48, 49, 51, 52, 56, 57, 58, 61, 62, 64, 68, 71, 73, 74, 76, 79, 82, 83, 86, 89, 101, 106

Offset: 1

N. J. A. Sloane, Jun 22 2001

Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it.
n-th row has A000081(n) terms.
First entry in row n is A005517(n).
Last entry in row n is A005518(n).
The Maple program yields row n after defining F = A005517(n) and L = A005518(n).

			The labels for the rooted trees with at most 4 nodes are as follows (x is the root):
                                         o
                                         |
               o         o        o   o  o
               |          \        \ /   |
     o  o   o  o  o o o    o   o    o    o
     |   \ /   |   \|/      \ /     |    |
  x  x    x    x    x        x      x    x
  1  2    4    3    8        6      7    5 (label)
Triangle begins:
1;
2;
3,4;
5,6,7,8;
9,10,11,12,13,14,16,17,19;
15,18,20,21,22,23,24,26,28,29,31,32,34,37,38,41,43,53,59,67;
25,27,30,33,35,36,39,40,42,44,46,47,48,49,51,52,56,57,58,61,62,64,68,\
71,73,74,76,79,82,83,86,89,101,106,107,109,118,127,131,134,139,157,163,\
179,191,241,277,331;
...
Triangle of rooted trees represented as finitary multisets begins:
(),
(()),
((())), (()()),
(((()))), (()(())), ((()())), (()()()),
((())(())), (()((()))), ((((())))), (()()(())), ((()(()))), (()(()())), (()()()()), (((()()))), ((()()())). - _Gus Wiseman_, Dec 21 2016

Alois P. Heinz, Rows n = 1..12, flattened
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Kevin Ryde, PARI/GP code calculating rows
Gus Wiseman, Matula-Goebel trees triangle illustration n=1..6
Index entries for sequences related to Matula-Goebel numbers
Index entries for sequences that are permutations of the natural numbers
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A061775 (number of nodes), A000081 (row lengths), A005517 (row minimum), A005518 (row maximum), A214572 (row n=8).
Cf. A347620 (inverse permutation).
Cf. A276625, A279065, A279614.

n := 8: F := 45: L := 2221: with(numtheory): N := proc (m) local r, s: r := proc (m) options operator, arrow: op(1, factorset(m)) end proc: s := proc (m) options operator, arrow: m/r(m) end proc: if m = 1 then 1 elif bigomega(m) = 1 then 1+N(pi(m)) else N(r(m))+N(s(m))-1 end if end proc: A := {}: for k from F to L do if N(k) = n then A := `union`(A, {k}) else  end if end do: A;

F[n_] := F[n] = Which[n == 1, 1, n == 2, 2, Mod[n, 3] == 0, 3*5^(n/3-1), Mod[n, 3] == 1, 5^(n/3-1/3), True, 9*5^(n/3-5/3)]; L[n_] := L[n] = Switch[n, 1, 1, 2, 2, 3, 4, 4, 8, , Prime[L[n-1]]]; r[m] := FactorInteger[m][[1, 1]]; s[m_] := m/r[m]; NN[m_] := NN[m] = Which[m == 1, 1, PrimeOmega[m] == 1, 1+NN[PrimePi[m]], True, NN[r[m]]+NN[s[m]]-1]; row[n_] := Module[{A, k}, A = {}; For[k = F[n], k <= L[n], k++, If[NN[k] == n, A = Union[A, {k}]]]; A]; Table[row[n], {n, 1, 8}] // Flatten (* Jean-François Alcover, Mar 06 2014, after Maple *)
nn=8;MGweight[n_]:=If[n===1,1,1+Total[Cases[FactorInteger[n],{p_,k_}:>k*MGweight[PrimePi[p]]]]];
Take[GatherBy[Range[Switch[nn,1,1,2,2,3,4,,Nest[Prime,8,nn-4]]],MGweight],nn] (* _Gus Wiseman, Dec 21 2016 *)

PARI
```
\\ See links.
```

More terms from Emeric Deutsch, May 01 2004

A006963 Number of planar embedded labeled trees with n nodes: (2*n-3)!/(n-1)! for n >= 2, a(1) = 1.

Original entry on oeis.org

1, 1, 3, 20, 210, 3024, 55440, 1235520, 32432400, 980179200, 33522128640, 1279935820800, 53970627110400, 2490952020480000, 124903451312640000, 6761440164390912000, 393008709555221760000, 24412776311194951680000, 1613955767240110694400000

Offset: 1

Simon Plouffe and N. J. A. Sloane

For n>1: central terms of the triangle in A173333; cf. A001761, A001813. - Reinhard Zumkeller, Feb 19 2010
Can be obtained from the Vandermonde permanent of the first n positive integers; see A093883. - Clark Kimberling, Jan 02 2012
All trees can be embedded in the plane, but "planar embedded" means that orientation matters but rotation doesn't. For example, the n-star with n-1 edges has n! ways to label it, but rotation removes a factor of n-1. Another example, the n-path has n! ways to label it, but rotation removes a factor of 2. - Michael Somos, Aug 19 2014

			G.f. = x + x^2 + 3*x^3 + 20*x^4 + 210*x^5 + 3024*x^6 + 55440*x^7 + 1235520*x^8 + ...
a(5) = 210 = 30 + 60 + 120 where 30 is for the star, 60 for the path, and 120 for the tree with one trivalent vertex. - _Michael Somos_, Aug 19 2014

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..200
David Callan, A quick count of plane (or planar embedded) labeled trees.
Ali Chouria, Vlad-Florin Drǎgoi, and Jean-Gabriel Luque, On recursively defined combinatorial classes and labelled trees, arXiv:2004.04203 [math.CO], 2020.
Robert Coquereaux and Jean-Bernard Zuber, Maps, immersions and permutations, Journal of Knot Theory and Its Ramifications, Vol. 25, No. 8 (2016), 1650047; arXiv preprint, arXiv:1507.03163 [math.CO], 2015-2016.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 109.
Bradley Robert Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
Pierre Leroux and Brahim Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992), pp. 53-80.
Pierre Leroux and Brahim Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992), pp. 53-80. (Annotated scanned copy)
J. W. Moon, Counting Labelled Trees, Issue 1 of Canadian mathematical monographs, Canadian Mathematical Congress, 1970.
Ran J. Tessler, A Cayley-type identity for trees, arXiv:1809.00001 [math.CO], 2018.
Index entries for sequences related to trees.

Cf. A000407, A001761, A001813, A173333.

[1] cat [Factorial(2*n-3)/Factorial(n-1): n in [2..20]]; // Vincenzo Librandi, Nov 12 2011

1, seq((2*n-3)!/(n-1)!,n=2..30); # Robert Israel, Aug 20 2014

Join[{1},Table[(2n-3)!/(n-1)!,{n,2,20}]] (* Harvey P. Dale, Nov 03 2011 *)
a[ n_] := With[{m = n - 1}, If[m < 1, Boole[m == 0], m! SeriesCoefficient[ -Log[(1 + Sqrt[1 - 4 x]) / 2], {x, 0, m}]]] (* Michael Somos, Jul 01 2013 *)
a[ n_] := If[n < 2, Boole[n == 1], (2 n - 3)! / (n - 1)!]; (* Michael Somos, Aug 19 2014 *)
a[1] := 1; a[n_] := (-1)^(n - 1)*Sum[(-1)^k*Binomial[2*n - 3, n + k - 2]*StirlingS1[n + k - 1, k + 1], {k, 1, n - 1}]; Flatten[Table[a[n], {n, 1, 19}]] (* Detlef Meya, Jan 18 2024 *)

{a(n) = n--; if( n<1, n==0, n! * polcoeff( -log( (1 + sqrt(1 - 4*x + x * O(x^n))) / 2), n))}; /* Michael Somos, Jul 01 2013 */

def A006963(n): return 1 if n==1 else factorial(2*n-3)/factorial(n-1)
[A006963(n) for n in range(1,31)] # G. C. Greubel, May 23 2023

E.g.f. for a(n+1), n >= 1, log(c(x)); c(x) = g.f. for Catalan numbers A000108. - Wolfdieter Lang
Integral representation as n-th moment of a positive function on a positive half-axis, in Maple notation: a(n) = int(x^n * erfc(sqrt(x)/2)/2, x=0..infinity), n=0, 1..., where erfc(x) is the complementary error function. - Karol A. Penson, Sep 27 2001
a(n) ~ 2^(-5/2)*n^-2*2^(2*n)*e^-n*n^n. - Joe Keane (jgk(AT)jgk.org), Jun 06 2002
a(n+1) = (n+1)*(n+2)*...*(2n-1) for n>=2. - Jaroslav Krizek, Nov 09 2010
E.g.f. (A(x)-1) is reversion of exp(-x)-exp(-2*x). - Vladimir Kruchinin, Jan 30 2012
G.f.: 1 + x*G(0) where G(k) = 1 + x*(2*k+1)*(4*k+3)/(k + 1 - 4*x*(k+1)^2*(4*k+5)/(4*x*(k+1)*(4*k+5) + (2*k+3)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 02 2013
E.g.f.: 1 + x*E(0) where E(k) = 1 + x*(2*k+1)*(4*k+3)/(2*(k + 1)^2 - 8*x*(k+1)^3*(4*k+5)/(4*x*(k+1)*(4*k+5) + (2*k+3)^2/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 02 2013
E.g.f: sqrt(1-4*x)/4 - 1/4 + 3*x/2 - x*log((1+sqrt(1-4*x))/2). - Robert Israel, Aug 20 2014
D-finite with recurrence (-n+1)*a(n) +2*(2*n-3)*(n-2)*a(n-1)=0. - R. J. Mathar, Jan 03 2018
From Amiram Eldar, Apr 03 2022: (Start)
Sum_{n>=1} 1/a(n) = 3/2 + 3*exp(1/4)*sqrt(Pi)*erf(1/2)/4, where erf is the error function.
Sum_{n>=1} (-1)^(n+1)/a(n) = 1/2 - sqrt(Pi)*erfi(1/2)/(4*exp(1/4)), where erfi is the imaginary error function. (End)
a(n) = A000407(n-2)/(n-1). - R. J. Mathar, Mar 30 2023
a(1) = 1; a(n) = (-1)^(n - 1)*Sum_{k=1..n - 1} (-1)^k*binomial(2*n - 3, n + k - 2)*Stirling1(n + k - 1, k + 1). - Detlef Meya, Jan 18 2024

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

A324923 Number of distinct factors in the factorization of n into factors q(i) = prime(i)/i, i > 0.

Original entry on oeis.org

0, 1, 2, 1, 3, 2, 2, 1, 2, 3, 4, 2, 3, 2, 3, 1, 3, 2, 2, 3, 3, 4, 3, 2, 3, 3, 2, 2, 4, 3, 5, 1, 4, 3, 4, 2, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 4, 2, 2, 3, 4, 3, 2, 2, 4, 2, 3, 4, 4, 3, 3, 5, 3, 1, 4, 4, 3, 3, 3, 4, 4, 2, 4, 3, 3, 2, 5, 3, 5, 3, 2, 4, 4, 3, 5, 3, 4, 4, 3, 3, 4, 3, 5, 4, 4, 2, 4, 2, 4, 3, 4, 4, 3, 3, 4, 2, 3, 2

Offset: 1

Gus Wiseman, Mar 20 2019

nonn

Also the number of distinct proper terminal subtrees of the rooted tree with Matula-Goebel number n. See illustrations in A061773.

			The factorization 22 = q(1)^2 q(2) q(3) q(5) has four distinct factors, so a(22) = 4.

One less than A317713.
Cf. A000081, A003963, A061773, A061775, A109082, A109129, A120383, A196050.
Cf. A324850, A324922, A324924, A324925, A324931, A324934, A324935, A324936, A366385, A366386.

difac[n_]:=If[n==1,{},With[{i=PrimePi[FactorInteger[n][[1,1]]]},Sort[Prepend[difac[n*i/Prime[i]],i]]]];
Table[Length[Union[difac[n]]],{n,100}]

A006530(n) = if(1==n, n, my(f=factor(n)); f[#f~, 1]);
A324923(n) = { my(lista = List([]), gpf, i); while(n > 1, gpf=A006530(n); i = primepi(gpf); n /= gpf; n *= i; listput(lista,i)); #Set(lista); }; \\ Antti Karttunen, Oct 23 2023

a(n) = A317713(n) - 1.

a(n) = A196050(n) - A366386(n). - Antti Karttunen, Oct 23 2023

Data section extended up to a(108) by Antti Karttunen, Oct 23 2023

A007562 Number of planted trees where non-root, non-leaf nodes an even distance from root are of degree 2.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 137, 275, 541, 1098, 2208, 4521, 9240, 19084, 39451, 82113, 171240, 358794, 753460, 1587740, 3353192, 7100909, 15067924, 32044456, 68272854, 145730675, 311575140, 667221030, 1430892924, 3072925944, 6607832422, 14226665499

Offset: 1

N. J. A. Sloane

There is no planted tree on one node by definition.
Column k=2 of A144018. - Alois P. Heinz, Oct 17 2012
It appears that a(n) is also the number of locally non-intersecting unlabeled rooted trees with n nodes, where a tree is locally non-intersecting if the branches directly under of any non-leaf node have empty intersection. - Gus Wiseman, Aug 22 2018

			G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 10*x^7 + 20*x^8 + 36*x^9 + ...
From _Joerg Arndt_, Jun 23 2014: (Start)
The a(8) = 20 such trees have the following level sequences:
01:  [ 0 1 2 3 4 3 2 1 ]
02:  [ 0 1 2 3 3 3 2 1 ]
03:  [ 0 1 2 3 3 2 2 1 ]
04:  [ 0 1 2 3 3 2 1 1 ]
05:  [ 0 1 2 3 2 3 2 1 ]
06:  [ 0 1 2 3 2 2 2 1 ]
07:  [ 0 1 2 3 2 2 1 1 ]
08:  [ 0 1 2 3 2 1 2 1 ]
09:  [ 0 1 2 3 2 1 1 1 ]
10:  [ 0 1 2 2 2 2 2 1 ]
11:  [ 0 1 2 2 2 2 1 1 ]
12:  [ 0 1 2 2 2 1 2 1 ]
13:  [ 0 1 2 2 2 1 1 1 ]
14:  [ 0 1 2 2 1 2 2 1 ]
15:  [ 0 1 2 2 1 2 1 1 ]
16:  [ 0 1 2 2 1 1 1 1 ]
17:  [ 0 1 2 1 2 1 2 1 ]
18:  [ 0 1 2 1 2 1 1 1 ]
19:  [ 0 1 2 1 1 1 1 1 ]
20:  [ 0 1 1 1 1 1 1 1 ]
Successive levels change by at most 1 and the last level is 1, compare to the example in A000081.
(End)
From _Gus Wiseman_, Aug 22 2018: (Start)
The a(7) = 10 locally non-intersecting trees:
  (o(o(oo)))
  (o(oo(o)))
  (o(oooo))
  (oo(o(o)))
  (oo(ooo))
  (o(o)(oo))
  (ooo(oo))
  (oo(o)(o))
  (oooo(o))
  (oooooo)
(End)

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..1000
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A000081, A000837, A004111, A007560, A144018, A289509, A316470, A316473, A316475.

with(numtheory): etr:= proc(p) local b; b:= proc(n) option remember; if n=0 then 1 else (add(d*p(d), d=divisors(n)) +add(add(d*p(d), d= divisors(j)) *b(n-j), j=1..n-1))/n fi end end: b:= etr(a): a:= n-> `if`(n<=1, n, b(n-2)): seq(a(n), n=1..40);  # Alois P. Heinz, Sep 06 2008

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, (Sum[ Sum[ d*p[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}] + Sum[ d*p[d], {d, Divisors[n]}])/n]; b]; b = etr[a]; a[n_] := If[n <= 1, n, b[n-2]]; Table[a[n], {n, 1, 36}] (* Jean-François Alcover, Aug 01 2013, after Alois P. Heinz *)
purt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]],Intersection@@#=={}&],{ptn,IntegerPartitions[n-1]}]];
Table[Length[purt[n]],{n,10}] (* Gus Wiseman, Aug 22 2018 *)

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

Shifts left 2 places under Euler transform.
G.f.: x + x^2 / (Product_{k>0} (1 - x^k)^a(k)). - Michael Somos, Oct 06 2003
a(n) ~ c * d^n / n^(3/2), where d = 2.246066877341161662499621547921... and  c = 0.68490297576105466417608032... . - Vaclav Kotesovec, Jun 23 2014
G.f. A(x) satisfies: A(x) = x + x^2 * exp(A(x) + A(x^2)/2 + A(x^3)/3 + A(x^4)/4 + ...). - Ilya Gutkovskiy, Jun 11 2021

Better description from Christian G. Bower, May 15 1998

cp's OEIS Frontend

A319312 Number of series-reduced rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A000625 Number of n-node steric rooted ternary trees; number of n carbon alkyl radicals C(n)H(2n+1) taking stereoisomers into account.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A317713 Number of distinct terminal subtrees of the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A061773 Triangle in which n-th row lists Matula-Goebel numbers for all rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A006963 Number of planar embedded labeled trees with n nodes: (2*n-3)!/(n-1)! for n >= 2, a(1) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica