A005804 -id:A005804 - cp's OEIS frontend

A118376 Number of all trees of weight n, where nodes have positive integer weights and the sum of the weights of the children of a node is equal to the weight of the node.

1, 2, 6, 24, 112, 568, 3032, 16768, 95200, 551616, 3248704, 19389824, 117021824, 712934784, 4378663296, 27081760768, 168530142720, 1054464293888, 6629484729344, 41860283723776, 265346078982144, 1687918305128448, 10771600724946944, 68941213290561536

Offset: 1

Jeremy Johnson (jjohnson(AT)cs.drexel.edu), May 15 2006

nonn

The number of trees with leaf nodes equal to 1 is counted by the sequence A001003 of super-Catalan numbers. The number of binary trees is counted by the sequence A007317 and the number of binary trees with leaf nodes equal to 1 is counted by the sequence A000108 of Catalan numbers.
Also the number of series-reduced enriched plane trees of weight n. A series-reduced enriched plane tree of weight n is either the number n itself or a finite sequence of at least two series-reduced enriched plane trees, one of each part of an integer composition of n. For example, the a(3) = 6 trees are: 3, (21), (12), (111), ((11)1), (1(11)). - Gus Wiseman, Sep 11 2018
Conjectured to be the number of permutations of length n avoiding the partially ordered pattern (POP) {1>2, 1>3, 3>4, 3>5} of length 5. That is, conjectured to be the number of length n permutations having no subsequences of length 5 in which the first element is the largest, and the third element is larger than the fourth and fifth elements. - Sergey Kitaev, Dec 13 2020
This conjecture has been proven. It can be restated as the number of size n permutations avoiding 51423, 51432, 52413, 52431, 53412, 53421, 54312, 54321. There are twelve sets of permutations avoiding eight size five permutations that are known to match this sequence. A further four are conjectured to match this sequence. - Christian Bean, Jul 24 2024

			T(3) = 6 because there are six trees
  3    3      3     3     3       3
      2 1    2 1   1 2   1 2    1 1 1
            1 1           1 1
From _Gus Wiseman_, Sep 11 2018: (Start)
The a(4) = 24 series-reduced enriched plane trees:
  4,
  (31), (13), (22), (211), (121), (112), (1111),
  ((21)1), ((12)1), (1(21)), (1(12)), (2(11)), ((11)2),
  ((111)1), (1(111)), ((11)(11)), ((11)11), (1(11)1), (11(11)),
  (((11)1)1), ((1(11))1), (1((11)1)), (1(1(11))).
(End)

G. C. Greubel, Table of n, a(n) for n = 1..1000
Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, PermPAL database.
Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); arXiv preprint, arXiv:2312.07716 [math.CO], 2023.
Hadrien Cambazard and Nicolas Catusse, Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the Plane, arXiv preprint arXiv:1512.06649 [cs.DS], 2015.
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Pawel Hitczenko, Jeremy R. Johnson, and Hung-Jen Huang, Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform, Theoretical Computer Science, Vol. 352, 2006, pp. 8-30.
J. R. Johnson and M. Püschel, In search for the optimal Walsh-Hadamard transform, Proc. ICASSP, Vol. 4, 2000, pp. 3347-3350.
Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.

Cf. A000108, A000311, A001003, A005804, A007317, A007853, A032171, A032200, A143363, A289501, A317852.

T := proc(n) option remember; local C, s, p, tp, k, i; if n = 1 then return 1; else s := 1; for k from 2 to n do C := combinat[composition](n,k); for p in C do tp := map(T,p); s := s + mul(tp[i],i=1..nops(tp)); end do; end do; end if; return s; end;

Rest[CoefficientList[Series[(Sqrt[1-8*x+8*x^2]-1)/(4*x-4), {x, 0, 20}], x]] (* Vaclav Kotesovec, Feb 03 2014 *)
a[n_] := 1+Sum[Binomial[n-1, k-1]*Hypergeometric2F1[2-k, k+1, 2, -1], {k, 2, n}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Apr 03 2015, after Vladimir Kruchinin *)
urp[n_]:=Prepend[Join@@Table[Tuples[urp/@ptn],{ptn,Join@@Permutations/@Select[IntegerPartitions[n],Length[#]>1&]}],n];
Table[Length[urp[n]],{n,7}] (* Gus Wiseman, Sep 11 2018 *)

a(n):=sum((-1)^j*2^(n-j-1)*binomial(n,j)*binomial(2*n-2*j-2,n-2*j-1),j,0,(n-1)/2)/n; /* Vladimir Kruchinin, Sep 29 2020 */

x='x+O('x^25); Vec((sqrt(1-8*x+8*x^2) - 1)/(4*x-4)) \\ G. C. Greubel, Feb 08 2017

Recurrence: T(1) = 1; For n > 1, T(n) = 1 + Sum_{n=n1+...+nt} T(n1)*...*T(nt).
G.f.: (-1+(1-8*z+8*z^2)^(1/2))/(-4+4*z).
From Vladimir Kruchinin, Sep 03 2010: (Start)
O.g.f.: A(x) = A001003(x/(1-x)).
a(n) = Sum_{k=1..n} binomial(n-1,k-1)*A001003(k), n>0. (End)
D-finite with recurrence: n*a(n) + 3*(-3*n+4)*a(n-1) + 4*(4*n-9)*a(n-2) + 8*(-n+3)*a(n-3) = 0. - R. J. Mathar, Sep 27 2013
a(n) ~ sqrt(sqrt(2)-1) * 2^(n-1/2) * (2+sqrt(2))^(n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 03 2014
From Peter Bala, Jun 17 2015: (Start)
With offset 0, binomial transform of A001003.
O.g.f. A(x) = series reversion of x*(2*x - 1)/(2*x^2 - 1); 2*(1 - x)*A^2(x) - A(x) + x = 0.
A(x) satisfies the differential equation (x - 9*x^2 + 16*x^3 - 8*x^4)*A'(x) + x*(3 - 4*x)*A(x) + x*(2*x - 1) = 0. Extracting coefficients gives Mathar's recurrence above. (End)
a(n) = Sum_{j=0..(n-1)/2} (-1)^j*2^(n-j-1)*C(n,j)*C(2*n-2*j-2,n-2*j-1)/n. - Vladimir Kruchinin, Sep 29 2020

A320154 Number of series-reduced balanced rooted trees whose leaves form a set partition of {1,...,n}.

Original entry on oeis.org

1, 2, 5, 18, 92, 588, 4328, 35920, 338437, 3654751, 45105744, 625582147, 9539374171, 157031052142, 2757275781918, 51293875591794, 1007329489077804, 20840741773898303, 453654220906310222, 10380640686263467204, 249559854371799622350, 6301679967177242849680

Offset: 1

Gus Wiseman, Oct 06 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root.

Also the number of balanced phylogenetic rooted trees on n distinct labels.

			The a(1) = 1 through a(4) = 18 rooted trees:
  (1)  (12)      (123)        (1234)
       ((1)(2))  ((1)(23))    ((1)(234))
                 ((2)(13))    ((12)(34))
                 ((3)(12))    ((13)(24))
                 ((1)(2)(3))  ((14)(23))
                              ((2)(134))
                              ((3)(124))
                              ((4)(123))
                              ((1)(2)(34))
                              ((1)(3)(24))
                              ((1)(4)(23))
                              ((2)(3)(14))
                              ((2)(4)(13))
                              ((3)(4)(12))
                              ((1)(2)(3)(4))
                              (((1)(2))((3)(4)))
                              (((1)(3))((2)(4)))
                              (((1)(4))((2)(3)))

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

Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A292504, A300660, A319312.

Cf. A320155, A320160, A316624, A320169, A320173, A320176, A320179.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
gug[m_]:=Prepend[Join@@Table[Union[Sort/@Tuples[gug/@mtn]],{mtn,Select[sps[m],Length[#]>1&]}],m];
Table[Length[Select[gug[Range[n]],SameQ@@Length/@Position[#,_Integer]&]],{n,9}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n,k)={my(u=vector(n), v=vector(n)); u[1]=k; u=EulerT(u); while(u, v+=u; u=EulerT(u)-u); 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

Terms a(9) and beyond from Andrew Howroyd, Oct 26 2018

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

A331686 Number of lone-child-avoiding locally disjoint rooted identity trees whose leaves are integer partitions whose multiset union is an integer partition of n.

Original entry on oeis.org

1, 2, 4, 8, 17, 41, 103, 280, 793, 2330, 6979, 21291

Offset: 1

Gus Wiseman, Jan 31 2020

A rooted tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other (unequal) child of the same vertex. Lone-child-avoiding means there are no unary branchings. In an identity tree, all branches of any given vertex are distinct.

			The a(1) = 1 through a(5) = 17 trees:
  (1)  (2)   (3)       (4)            (5)
       (11)  (12)      (13)           (14)
             (111)     (22)           (23)
             ((1)(2))  (112)          (113)
                       (1111)         (122)
                       ((1)(3))       (1112)
                       ((2)(11))      (11111)
                       ((1)((1)(2)))  ((1)(4))
                                      ((2)(3))
                                      ((1)(22))
                                      ((3)(11))
                                      ((2)(111))
                                      ((1)((1)(3)))
                                      ((2)((1)(2)))
                                      ((11)((1)(2)))
                                      ((1)((2)(11)))
                                      ((1)((1)((1)(2))))

The non-identity version is A331678.
The case where the leaves are all singletons is A316694.
Identity trees are A004111.
Locally disjoint identity trees are A316471.
Locally disjoint enriched identity p-trees are A331684.
Lone-child-avoiding locally disjoint rooted semi-identity trees are A212804.
Cf. A000669, A001678, A005804, A141268, A300660, A316697, A319312, A331679, A331683, A331783, A331874, A331875.

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]]]];
disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
mpti[m_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[mpti/@p]],UnsameQ@@#&&disjointQ[#]&],{p,Select[mps[m],Length[#]>1&]}],m];
Table[Sum[Length[mpti[m]],{m,Sort/@IntegerPartitions[n]}],{n,8}]

A295279 Number of strict tree-factorizations of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 4, 2, 2, 1, 10, 1, 2, 2, 4, 1, 8, 1, 6, 2, 2, 2, 12, 1, 2, 2, 10, 1, 8, 1, 4, 4, 2, 1, 26, 1, 4, 2, 4, 1, 10, 2, 10, 2, 2, 1, 28, 1, 2, 4, 12, 2, 8, 1, 4, 2, 8, 1, 44, 1, 2, 4, 4, 2, 8, 1, 26, 3, 2, 1

Offset: 1

Gus Wiseman, Nov 19 2017

nonn

A strict tree-factorization of n is either (case 1) the number n itself or (case 2) a set of two or more strict tree-factorizations, one of each factor in a factorization of n into distinct factors greater than one.

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

			The a(30) = 8 strict tree-factorizations are: 30, (2*3*5), (2*15), (2*(3*5)), (3*10), (3*(2*5)), (5*6), (5*(2*3)).
The a(36) = 12 strict tree-factorizations are: 36, (2*3*6), (2*3*(2*3)), (2*18), (2*(2*9)), (2*(3*6)), (2*(3*(2*3))), (3*12), (3*(2*6)), (3*(2*(2*3))), (3*(3*4)), (4*9).

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

Cf. A005804, A045778, A273873, A281113 A281118, A292504, A294786, A295281.

sfs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sfs[n/d],Min@@#>d&]],{d,Rest[Divisors[n]]}]];
sft[n_]:=1+Total[Function[fac,Times@@sft/@fac]/@Select[sfs[n],Length[#]>1&]];
Array[sft,100]

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

a(product of n distinct primes) = A005804(n).
a(prime^n) = A273873(n).
Dirichlet g.f.: (Zeta(s) + Product_{n >= 2}(1 + a(n)/n^s))/2.

A316624 Number of balanced p-trees with n leaves.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 4, 8, 9, 16, 20, 40, 47, 83, 111, 201, 259, 454, 603, 1049, 1432, 2407, 3390, 6006, 8222, 13904, 20304, 34828, 50291, 85817, 126013, 217653, 317894, 535103, 798184, 1367585, 2008125, 3360067, 5048274, 8499942, 12623978, 21023718, 31552560, 52575257

Offset: 1

Gus Wiseman, Oct 07 2018

nonn

A p-tree of weight n is either a single node (if n = 1) or a finite sequence of p-trees whose weights are weakly decreasing and sum to n.

A tree is balanced if all leaves have the same height.

			The a(1) = 1 through a(7) = 4 balanced p-trees:
  o  (oo)  (ooo)  (oooo)      (ooooo)      (oooooo)        (ooooooo)
                  ((oo)(oo))  ((ooo)(oo))  ((ooo)(ooo))    ((oooo)(ooo))
                                           ((oooo)(oo))    ((ooooo)(oo))
                                           ((oo)(oo)(oo))  ((ooo)(oo)(oo))

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

Cf. A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A196545, A289501, A319312.

ptrs[n_]:=If[n==1,{"o"},Join@@Table[Tuples[ptrs/@p],{p,Rest[IntegerPartitions[n]]}]];
Table[Length[ptrs[n]],{n,12}]
Table[Length[Select[ptrs[n],SameQ@@Length/@Position[#,"o"]&]],{n,12}]

seq(n)={my(p=x + O(x*x^n), q=0); while(p, q+=p; p = 1/prod(k=1, n, 1 - polcoef(p,k)*x^k + O(x*x^n)) - 1 - p); Vec(q)} \\ Andrew Howroyd, Oct 26 2018

Terms a(17) and beyond from Andrew Howroyd, Oct 26 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

A331679 Number of lone-child-avoiding locally disjoint rooted trees whose leaves are positive integers summing to n, with no two distinct leaves directly under the same vertex.

Original entry on oeis.org

1, 2, 3, 8, 16, 48, 116, 341, 928, 2753, 7996, 24254, 73325, 226471, 702122

Offset: 1

Gus Wiseman, Jan 25 2020

A tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other unequal child of the same vertex. It is lone-child-avoiding if there are no unary branchings.

			The a(1) = 1 through a(5) = 16 trees:
  1  2     3        4           5
     (11)  (111)    (22)        (11111)
           (1(11))  (1111)      ((11)3)
                    (2(11))     (1(22))
                    (1(111))    (2(111))
                    (11(11))    (1(1111))
                    ((11)(11))  (11(111))
                    (1(1(11)))  (111(11))
                                (1(2(11)))
                                (2(1(11)))
                                (1(1(111)))
                                (1(11)(11))
                                (1(11(11)))
                                (11(1(11)))
                                (1((11)(11)))
                                (1(1(1(11))))

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.

The non-locally disjoint version is A141268.
Locally disjoint trees counted by vertices are A316473.
The case where all leaves are 1's is A316697.
Number of trees counted by A331678 with all atoms equal to 1.
Matula-Goebel numbers of locally disjoint rooted trees are A316495.
Unlabeled lone-child-avoiding locally disjoint rooted trees are A331680.
Cf. A000081, A000669, A001678, A005804, A060356, A300660, A316471, A316694, A316696, A319312, A330465, A331681.

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
usot[n_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[usot/@ptn]],disjointQ[DeleteCases[#,_?AtomQ]]&&SameQ@@Select[#,AtomQ]&],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}],n];
Table[Length[usot[n]],{n,12}]

A331680 Number of lone-child-avoiding locally disjoint unlabeled rooted trees with n vertices.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 6, 9, 16, 26, 45, 72, 124, 201, 341, 561, 947, 1571, 2651, 4434, 7496, 12631, 21423, 36332, 61910, 105641, 180924, 310548, 534713, 923047

Offset: 1

Gus Wiseman, Jan 25 2020

First differs from A320268 at a(11) = 45, A320268(11) = 44.

A rooted tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other unequal child of the same vertex. Lone-child-avoiding means there are no unary branchings.

			The a(1) = 1 through a(9) = 16 trees (empty column indicated by dot):
  o  .  (oo)  (ooo)  (oooo)   (ooooo)   (oooooo)    (ooooooo)    (oooooooo)
                     (o(oo))  (o(ooo))  (o(oooo))   (o(ooooo))   (o(oooooo))
                              (oo(oo))  (oo(ooo))   (oo(oooo))   (oo(ooooo))
                                        (ooo(oo))   (ooo(ooo))   (ooo(oooo))
                                        ((oo)(oo))  (oooo(oo))   (oooo(ooo))
                                        (o(o(oo)))  (o(o(ooo)))  (ooooo(oo))
                                                    (o(oo)(oo))  ((ooo)(ooo))
                                                    (o(oo(oo)))  (o(o(oooo)))
                                                    (oo(o(oo)))  (o(oo(ooo)))
                                                                 (o(ooo(oo)))
                                                                 (oo(o(ooo)))
                                                                 (oo(oo)(oo))
                                                                 (oo(oo(oo)))
                                                                 (ooo(o(oo)))
                                                                 (o((oo)(oo)))
                                                                 (o(o(o(oo))))

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.

The enriched version is A316696.
The Matula-Goebel numbers of these trees are A331871.
The non-locally disjoint version is A001678.
These trees counted by number of leaves are A316697.
The semi-lone-child-avoiding version is A331872.
Cf. A000081, A000669, A005804, A060356, A141268, A300660, A316471, A316473, A316694, A316495, A319312, A330465, A331679, A331681, A331683.

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
strut[n_]:=If[n==1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[strut/@c]]]/@Rest[IntegerPartitions[n-1]],disjointQ]];
Table[Length[strut[n]],{n,10}]

A319122 Number of phylogenetic plane trees on n labels.

Original entry on oeis.org

1, 3, 25, 387, 8521, 241683, 8383705, 343826787, 16273985641, 873119718963, 52360707915385, 3470858539699587, 252000934472119561, 19888355652445884243, 1695252683833578455065, 155208762048402360698787, 15190477481877333732410281, 1582657042668691276257233523

Offset: 1

Gus Wiseman, Sep 11 2018

nonn

A phylogenetic plane tree on n labels is either the set of labels itself or a finite sequence of at least two phylogenetic plane trees, one on each block of an ordered set partition of the labels.

			The a(2) = 3 phylogenetic plane trees are {1,2}, ({1},{2}), ({2},{1}).

Cf. A000108, A000670, A001003, A005804, A074206, A118376, A277130, A281118, A281119, A319137.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
t[n_]:=t[n]=1+Sum[Times@@t/@f,{f,Join@@Permutations/@Select[sps[Range[n]],Length[#]>1&]}];
Array[t,8]

cp's OEIS Frontend

A118376 Number of all trees of weight n, where nodes have positive integer weights and the sum of the weights of the children of a node is equal to the weight of the node.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

A320154 Number of series-reduced balanced rooted trees whose leaves form a set partition of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A331686 Number of lone-child-avoiding locally disjoint rooted identity trees whose leaves are integer partitions whose multiset union is an integer partition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A295279 Number of strict tree-factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A316624 Number of balanced p-trees with n leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI