A004111 -id:A004111 - cp's OEIS frontend

A063895 Start with x, xy; then concatenate each word in turn with all preceding words, getting x xy xxy xxxy xyxxy xxxxy xyxxxy xxyxxxy ...; sequence gives number of words of length n. Also binary trees by degree: x (x,y) (x,(x,y)) (x,(x,(x,y))) ((x,y),(x,(x,y)))...

1, 1, 1, 1, 2, 3, 6, 11, 22, 43, 88, 179, 372, 774, 1631, 3448, 7347, 15713, 33791, 72923, 158021, 343495, 749102, 1638103, 3591724, 7893802, 17387931, 38379200, 84875596, 188036830, 417284181, 927469845, 2064465341, 4601670625, 10270463565, 22950838755

Offset: 1

Claude Lenormand (claude.lenormand(AT)free.fr), Aug 29 2001

Also binary rooted identity trees (those with no symmetries, cf. A004111).
From Gus Wiseman, May 04 2021: (Start)
Also the number of unlabeled binary rooted semi-identity trees with 2*n - 1 nodes. In a semi-identity tree, only the non-leaf branches directly under any given vertex are required to be distinct. Alternatively, an unlabeled rooted tree is a semi-identity tree iff the non-leaf branches of the root are all distinct and are themselves semi-identity trees. For example, the a(3) = 1 through a(6) = 6 trees are:
  (o(oo))  (o(o(oo)))  ((oo)(o(oo)))  ((oo)(o(o(oo))))  ((o(oo))(o(o(oo))))
                       (o(o(o(oo))))  (o((oo)(o(oo))))  ((oo)((oo)(o(oo))))
                                      (o(o(o(o(oo)))))  ((oo)(o(o(o(oo)))))
                                                        (o((oo)(o(o(oo)))))
                                                        (o(o((oo)(o(oo)))))
                                                        (o(o(o(o(o(oo))))))
The a(8) = 11 trees with 15 nodes:
  ((o(oo))((oo)(o(oo))))
  ((o(oo))(o(o(o(oo)))))
  ((oo)((oo)(o(o(oo)))))
  ((oo)(o((oo)(o(oo)))))
  ((oo)(o(o(o(o(oo))))))
  (o((o(oo))(o(o(oo)))))
  (o((oo)((oo)(o(oo)))))
  (o((oo)(o(o(o(oo))))))
  (o(o((oo)(o(o(oo))))))
  (o(o(o((oo)(o(oo))))))
  (o(o(o(o(o(o(oo)))))))
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Index entries for sequences related to rooted trees

Cf. A063894, A036774.
The non-semi-identity version is 2*A001190(n)-1, ranked by A111299.
Semi-binary trees are also counted by A001190, but ranked by A292050.
The not necessarily binary version is A306200, ranked A306202.
The Matula-Goebel numbers of these trees are A339193.
The plane tree version is A343663.
A000081 counts unlabeled rooted trees with n nodes.
A004111 counts identity trees, ranked by A276625.
A306201 counts balanced semi-identity trees, ranked by A306203.
A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
Cf. A001678, A331934, A331963, A331964.

a:= proc(n) option remember; `if`(n<3, n*(3-n)/2, add(a(i)*a(n-i),
      i=1..(n-1)/2)+`if`(irem(n, 2, 'r')=0, (p->(p-1)*p/2)(a(r)), 0))
    end:
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 02 2013

a[n_] := a[n] = If[n<3, n*(3-n)/2, Sum[a[i]*a[n-i], {i, 1, (n-1)/2}]+If[{q, r} = QuotientRemainder[n, 2]; r == 0, (a[q]-1)*a[q]/2, 0]]; Table[a[n], {n, 1, 36}] (* Jean-François Alcover, Feb 25 2014, after Alois P. Heinz *)
ursiq[n_]:=Join@@Table[Select[Union[Sort/@Tuples[ursiq/@ptn]],#=={}||#=={{},{}}||Length[#]==2&&(UnsameQ@@DeleteCases[#,{}])&],{ptn,IntegerPartitions[n-1]}];Table[Length[ursiq[n]],{n,1,15,2}] (* Gus Wiseman, May 04 2021 *)

{a(n)=local(A, m); if(n<1, 0, m=1; A=O(x); while( m<=n, m*=2; A=1-sqrt(1-2*x-2*x^2+subst(A, x, x^2))); polcoeff(A, n))}

a(n) = (sum a(i)*a(j), i+j=n, i2. a(1)=a(2)=1.
G.f. A(x) = 1-sqrt(1-2x-2x^2+A(x^2)) satisfies x+x^2-A(x)+(A(x)^2-A(x^2))/2=0, A(0)=0. - Michael Somos, Sep 06 2003
a(n) ~ c * d^n / n^(3/2), where d = 2.33141659246516873904600076533362924695..., c = 0.2873051160895040470174351963... . - Vaclav Kotesovec, Sep 11 2014

Additional comments and g.f. from Christian G. Bower, Nov 29 2001

A298426 Regular triangle where T(n,k) is number of k-ary rooted trees with n nodes.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 3, 0, 1, 0, 0, 0, 1, 0, 1, 0, 2, 0, 0, 0, 0, 0, 1, 0, 1, 6, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 11, 4, 2, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 23, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Gus Wiseman, Jan 19 2018

Row sums are A298422.

			Triangle begins:
1
0  1
0  1  1
0  1  0  1
0  1  1  0  1
0  1  0  0  0  1
0  1  2  1  0  0  1
0  1  0  0  0  0  0  1
0  1  3  0  1  0  0  0  1
0  1  0  2  0  0  0  0  0  1
0  1  6  0  0  1  0  0  0  0  1
0  1  0  0  0  0  0  0  0  0  0  1
0  1  11 4  2  0  1  0  0  0  0  0  1
0  1  0  0  0  0  0  0  0  0  0  0  0  1
0  1  23 0  0  0  0  1  0  0  0  0  0  0  1
0  1  0  8  0  2  0  0  0  0  0  0  0  0  0  1

Alois P. Heinz, Rows n = 1..200, flattened

Cf. A000005, A000081, A000598, A001190, A001678, A003238, A004111, A067538, A143773, A289078, A289079, A295461, A298118, A298422, A298423, A298424.

nn=16;
arut[n_,k_]:=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[arut[#,k]&/@c]]]/@Select[IntegerPartitions[n-1],Length[#]===k&]]
Table[arut[n,k]//Length,{n,nn},{k,0,n-1}]

A038081 Number of rooted identity trees of height n. Sets of rank n.

Original entry on oeis.org

1, 1, 2, 12, 65520

Offset: 0

Christian G. Bower, Jan 04 1999

Next term is 2^65536 - 65536.

Eric Weisstein's World of Mathematics, Rank.
Index entries for sequences related to rooted trees

Cf. A004111, A038082-A038093, A048828.
Differences of A014221.
Column sums of A227819.

A050383 Permutation rooted trees with n nodes.

Original entry on oeis.org

1, 1, 3, 8, 25, 77, 262, 897, 3208, 11658, 43243, 162477, 618219, 2374699, 9200541, 35903017, 140997527, 556798525, 2209685939, 8807924914, 35248187347, 141564134395, 570402287162, 2305138038036, 9340981510156, 37946616550787

Offset: 1

Christian G. Bower, Nov 15 1999

Vaclav Kotesovec, Table of n, a(n) for n = 1..240
C. G. Bower, Transforms (2)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 773
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A004111, A005355, A091865, A308368.

m = 26; A[_] = 0;
Do[A[x_] = 1/Product[1 - x^n A[x^n], {n, 1, m}] + O[x]^m // Normal, {m}];
CoefficientList[A[x], x] (* Jean-François Alcover, Oct 02 2019 *)

{a(n)=local(A=1+x); for(i=1, n, A=1/prod(k=1, n, (1-x^k*subst(A,x,x^k+x*O(x^n))))); polcoeff(A, n)} /* Paul D. Hanna */

G.f. (with offset 0) satisfies: A(x) = 1/Product_{n>=1} (1 - x^n*A(x^n)). - Paul D. Hanna, Sep 28 2011
Shifts left under transform T where Ta is EULER(CIK(a)).
a(n) ~ c * d^n / n^(3/2), where d = 4.313133937842504228... and c = 0.153549235191409889... - Vaclav Kotesovec, Nov 05 2021

A255517 Number A(n,k) of rooted identity trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 1, 3, 5, 2, 0, 0, 1, 4, 12, 18, 3, 0, 0, 1, 5, 22, 64, 66, 6, 0, 0, 1, 6, 35, 156, 363, 266, 12, 0, 0, 1, 7, 51, 310, 1193, 2214, 1111, 25, 0, 0, 1, 8, 70, 542, 2980, 9748, 14043, 4792, 52, 0, 0, 1, 9, 92, 868, 6273, 30526, 82916, 91857, 21124, 113, 0

Offset: 0

Alois P. Heinz, Feb 24 2015

From Vaclav Kotesovec, Feb 24 2015: (Start)
k    Limit n->infinity A(n,k)^(1/n)
  2.517540352632003890795354598463447277335981266803... = A246169
  5.249032491228170579164952216184309265343086337648... = A246312
  7.969494030514425004826375511986491746399264355846...
 10.688492754969652458452048798468242930479212456958...
 13.407087472537747579787047072702638639945914705837...
 16.125529360448558670505097146631763969697822205298...
 18.843901825822305757579605844910623225182677164912...
 21.562238702430237066018783115405680041128676137631...
 24.280555694806692616578932533497629224907619468796...
26.998860838916733933849490675388336975888308433826...
271.64425688361559470587959030374804709717287744789...
Conjecture: For big k the limit asymptotically approaches k*exp(1).
(End)

			A(3,2) = 5:
  o    o    o    o      o
  |    |    |    |     / \
  1    1    2    2    1   2
  |    |    |    |
  1    2    1    2
Square array A(n,k) begins:
  0,  0,   0,    0,    0,     0,     0, ...
  1,  1,   1,    1,    1,     1,     1, ...
  0,  1,   2,    3,    4,     5,     6, ...
  0,  1,   5,   12,   22,    35,    51, ...
  0,  2,  18,   64,  156,   310,   542, ...
  0,  3,  66,  363, 1193,  2980,  6273, ...
  0,  6, 266, 2214, 9748, 30526, 77262, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=1-10 give: A004111, A005753, A052757, A052772, A052797, A255518, A255519, A255520, A255521, A255522.
Rows n=0-4 give: A000004, A000012, A001477, A000326, 2*A051662(k-1) for k>0.
Lower diagonal gives A255523.
Cf. A242249, A256068.

with(numtheory):
A:= proc(n, k) option remember; `if`(n<2, n, add(A(n-j, k)*add(
      k*A(d, k)*d*(-1)^(j/d+1), d=divisors(j)), j=1..n-1)/(n-1))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..14);

A[n_, k_] := A[n, k] = If[n<2, n, Sum[A[n-j, k]*Sum[k*A[d, k]*d*(-1)^(j/d + 1), {d, Divisors[j]}], {j, 1, n-1}]/(n-1)]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)

A306202 Matula-Goebel numbers of rooted semi-identity trees.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 47, 48, 51, 52, 53, 55, 56, 57, 58, 59, 60, 62, 64, 65, 66, 67, 68, 70, 71, 73, 74, 76, 77, 78, 79, 80, 82, 84, 85

Offset: 1

Gus Wiseman, Jan 29 2019

nonn

Definition: A positive integer belongs to the sequence iff its prime indices greater than 1 are distinct and already belong to the sequence. A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The sequence of all unlabeled rooted semi-identity trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   6: (o(o))
   7: ((oo))
   8: (ooo)
  10: (o((o)))
  11: ((((o))))
  12: (oo(o))
  13: ((o(o)))
  14: (o(oo))
  15: ((o)((o)))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  20: (oo((o)))
  21: ((o)(oo))
  22: (o(((o))))
  24: (ooo(o))
  26: (o(o(o)))
  28: (oo(oo))
  29: ((o((o))))
  30: (o(o)((o)))

Index entries for sequences related to Matula-Goebel numbers

Cf. A000081, A004111, A007097, A276625, A277098, A306200, A306201, A316467.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
psidQ[n_]:=And[UnsameQ@@DeleteCases[primeMS[n],1],And@@psidQ/@primeMS[n]];
Select[Range[100],psidQ]

A317707 Number of powerful rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 11, 13, 22, 29, 46, 57, 94, 115, 180, 230, 349, 435, 671, 830, 1245, 1572, 2320, 2894, 4287, 5328, 7773, 9752, 14066, 17547, 25328, 31515, 45010, 56289, 79805, 99467, 140778, 175215, 246278, 307273, 429421, 534774, 745776, 927776, 1287038

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

An unlabeled rooted tree is powerful if either it is a single node or a single node with a single powerful tree as a branch, or if the branches of the root all appear with multiplicities greater than 1 and are themselves powerful trees.

			The a(7) = 11 powerful rooted trees:
  ((((((o))))))
  (((((oo)))))
  ((((ooo))))
  ((((o)(o))))
  (((oooo)))
  ((ooooo))
  (((o))((o)))
  ((oo)(oo))
  ((o)(o)(o))
  (oo(o)(o))
  (oooooo)

Alois P. Heinz, Table of n, a(n) for n = 1..8000

Cf. A000081, A001190, A001694, A004111, A301700, A303431, A317102.

Cf. A317705, A317708, A317709, A317710, A317711, A317712, A317718, A317719.

h:= proc(n, k, t) option remember; `if`(k=0, binomial(n+t, t),
      `if`(n=0, 0, add(h(n-1, k-j, t+1), j=2..k)))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)*h(a(i), j, 0), j=0..n/i)))
    end:
a:= proc(n) option remember; `if`(n<2, n, b(n-1$2)+a(n-1)) end:
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 31 2018

purt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]],Or[Length[#]==1,Min@@Length/@Split[#]>1]&],{ptn,IntegerPartitions[n-1]}]];
Table[Length[purt[n]],{n,10}]
(* Second program: *)
h[n_, k_, t_] := h[n, k, t] = If[k == 0, Binomial[n + t, t], If[n == 0, 0, Sum[h[n - 1, k - j, t + 1], {j, 2, k}]]];
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, i - 1]* h[a[i], j, 0], {j, 0, n/i}]]];
a[n_] := a[n] = If[n < 2, n, b[n - 1, n - 1] + a[n - 1]];
Array[a, 50] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

a(27)-a(45) from Alois P. Heinz, Aug 31 2018

A323795 Number of non-isomorphic weight-n sets of non-overlapping sets of sets.

Original entry on oeis.org

1, 1, 3, 8, 27, 82, 310, 1163

Offset: 0

Gus Wiseman, Jan 28 2019

Also the number of non-isomorphic set partitions of set-systems of weight n.
All sets and multisets must be finite, and only the outermost may be empty.
The weight of an atom is 1, and the weight of a multiset is the sum of weights of its elements, counting multiplicity.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 27 multiset partitions:
  {{1}}  {{12}}      {{123}}          {{1234}}
         {{1}{2}}    {{1}{12}}        {{1}{123}}
         {{1}}{{2}}  {{1}{23}}        {{12}{13}}
                     {{1}}{{12}}      {{1}{234}}
                     {{1}}{{23}}      {{12}{34}}
                     {{1}{2}{3}}      {{1}}{{123}}
                     {{1}}{{2}{3}}    {{1}{2}{12}}
                     {{1}}{{2}}{{3}}  {{1}{2}{13}}
                                      {{12}}{{13}}
                                      {{1}}{{234}}
                                      {{1}{2}{34}}
                                      {{12}}{{34}}
                                      {{1}}{{2}{12}}
                                      {{12}}{{1}{2}}
                                      {{1}}{{2}{13}}
                                      {{12}}{{1}{3}}
                                      {{1}}{{2}{34}}
                                      {{1}{2}{3}{4}}
                                      {{12}}{{3}{4}}
                                      {{2}}{{1}{13}}
                                      {{1}}{{2}}{{12}}
                                      {{1}}{{2}}{{13}}
                                      {{1}}{{2}}{{34}}
                                      {{1}}{{2}{3}{4}}
                                      {{1}{2}}{{3}{4}}
                                      {{1}}{{2}}{{3}{4}}
                                      {{1}}{{2}}{{3}}{{4}}

Cf. A004111, A007716, A049311, A050326, A050343, A283877, A306186, A318566.

Cf. A323787, A323788, A323789, A323790, A323791, A323792, A323793, A323794.

A358377 Numbers k such that the k-th standard ordered rooted tree is a generalized Bethe tree (counted by A003238).

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 9, 11, 16, 17, 32, 37, 43, 64, 128, 129, 137, 171, 256, 257, 293, 512, 529, 683, 1024, 1025, 2048, 2185, 2341, 2731, 4096, 8192, 10923, 16384, 16913, 18725, 32768, 32769, 32897, 34953, 43691, 65536, 65537, 131072, 131329, 149797, 174763

Offset: 1

Gus Wiseman, Nov 14 2022

nonn

We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

A generalized Bethe tree is an unlabeled rooted tree where all branches directly under the same root are equal.

			The terms together with their corresponding ordered rooted trees begin:
    1: o
    2: (o)
    3: ((o))
    4: (oo)
    5: (((o)))
    8: (ooo)
    9: ((oo))
   11: ((o)(o))
   16: (oooo)
   17: ((((o))))
   32: (ooooo)
   37: (((o))((o)))
   43: ((o)(o)(o))
   64: (oooooo)
  128: (ooooooo)
  129: ((ooo))
  137: ((oo)(oo))
  171: ((o)(o)(o)(o))

Gus Wiseman, Statistics, classes, and transformations of standard compositions

These trees are counted by A003238.
The unordered version is A214577, also counted by A003238.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358371 and A358372 count leaves and nodes in standard ordered rooted trees.
A358374 ranks ordered identity trees, counted by A032027.
Cf. A001263, A004111, A004249, A005043, A063895, A276625, A331490, A358373, A358375, A358376.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[1000],FreeQ[srt[#],[_]?(!SameQ@@#&)]&]

A001679 Number of series-reduced rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 0, 2, 2, 4, 6, 12, 20, 39, 71, 137, 261, 511, 995, 1974, 3915, 7841, 15749, 31835, 64540, 131453, 268498, 550324, 1130899, 2330381, 4813031, 9963288, 20665781, 42947715, 89410092, 186447559, 389397778, 814447067, 1705775653, 3577169927

Offset: 0

N. J. A. Sloane

nonn

Also known as homeomorphically irreducible rooted trees, or rooted trees without nodes of degree 2.

A rooted tree is lone-child-avoiding if no vertex has exactly one child, and topologically series-reduced if no vertex has degree 2. This sequence counts unlabeled topologically series-reduced rooted trees with n vertices. Lone-child-avoiding rooted trees with n - 1 vertices are counted by A001678. - Gus Wiseman, Jan 21 2020

			G.f. = 1 + x + x^2 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 12*x^8 + 20*x^9 + ...
From _Gus Wiseman_, Jan 21 2020: (Start)
The a(1) = 1 through a(8) = 12 unlabeled topologically series-reduced rooted trees with n nodes (empty n = 3 column shown as dot) are:
  o  (o)  .  (ooo)   (oooo)   (ooooo)    (oooooo)    (ooooooo)
             ((oo))  ((ooo))  ((oooo))   ((ooooo))   ((oooooo))
                              (oo(oo))   (oo(ooo))   (oo(oooo))
                              ((o(oo)))  (ooo(oo))   (ooo(ooo))
                                         ((o(ooo)))  (oooo(oo))
                                         ((oo(oo)))  ((o(oooo)))
                                                     ((oo(ooo)))
                                                     ((ooo(oo)))
                                                     (o(oo)(oo))
                                                     (oo(o(oo)))
                                                     (((oo)(oo)))
                                                     ((o(o(oo))))
(End)

D. G. Cantor, personal communication.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Eq. (3.3.9).
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, Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See p. 155. - _N. J. A. Sloane_, Apr 18 2014
F. Harary, G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math. 101 (1959) 141-162, W(x,y) equation (9a).
N. J. A. Sloane, Illustration of initial terms
Eric Weisstein's World of Mathematics, Series-Reduced Tree.
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Apart from initial term, same as A059123.
Cf. A000055 (trees by nodes), A000014 (homeomorphically irreducible trees by nodes), A000669 (homeomorphically irreducible planted trees by leaves), A000081 (rooted trees by nodes).
Cf. A246403.
The labeled version is A060313, with unrooted case A005512.
Matula-Goebel numbers of these trees are given by A331489.
Lone-child-avoiding rooted trees are counted by A001678(n + 1).
Cf. A004111, A060356, A198518, A254382, A291636, A330951, A331488, A331578.

with(powseries): with(combstruct): n := 30: Order := n+3: sys := {B = Prod(C,Z), S = Set(B,1 <= card), C = Union(Z,S)}:
G001678 := (convert(gfseries(sys,unlabeled,x)[S(x)], polynom)) * x^2: G0temp := G001678 + x^2:
G001679 := G0temp / x + G0temp - (G0temp^2+eval(G0temp,x=x^2))/(2*x): A001679 := 0,seq(coeff(G001679,x^i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)
# adapted for Maple 16 or higher version by Vaclav Kotesovec, Jun 26 2014

terms = 37; (* F = G001678 *) F[] = 0; Do[F[x] = (x^2/(1 + x))*Exp[Sum[ F[x^k]/(k*x^k), {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms + 1}];
G[x_] = 1 + ((1 + x)/x)*F[x] - (F[x]^2 + F[x^2])/(2*x) + O[x]^terms;
CoefficientList[G[x], x] (* Jean-François Alcover, Jan 12 2018 *)
urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[urt[n],Length[#]!=2&&FreeQ[Z@@#,{}]&]],{n,15}] (* _Gus Wiseman, Jan 21 2020 *)

{a(n) = local(A); if( n<3, n>0, A = x / (1 - x^2) + x * O(x^n); for(k=3, n-1, A /= (1 - x^k + x * O(x^n))^polcoeff(A, k)); polcoeff( (1 + x)*A - x*(A^2 + subst(A, x, x^2)) / 2, n))};

G.f. = 1 + ((1+x)*f(x) - (f(x)^2+f(x^2))/2)/x where f(x) is g.f. for A001678 (homeomorphically irreducible planted trees by nodes).
a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711... and c = 0.4213018528699249210965028... . - Vaclav Kotesovec, Jun 26 2014
For n > 1, this sequence counts lone-child-avoiding rooted trees with n nodes and more than two branches, plus lone-child-avoiding rooted trees with n - 1 nodes. So for n > 1, a(n) = A331488(n) + A001678(n). - Gus Wiseman, Jan 21 2020

Additional comments from Michael Somos, Oct 10 2003

cp's OEIS Frontend

A063895 Start with x, xy; then concatenate each word in turn with all preceding words, getting x xy xxy xxxy xyxxy xxxxy xyxxxy xxyxxxy ...; sequence gives number of words of length n. Also binary trees by degree: x (x,y) (x,(x,y)) (x,(x,(x,y))) ((x,y),(x,(x,y)))...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A298426 Regular triangle where T(n,k) is number of k-ary rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A038081 Number of rooted identity trees of height n. Sets of rank n.

Views

Author

Keywords

Comments

Links

Crossrefs

A050383 Permutation rooted trees with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A255517 Number A(n,k) of rooted identity trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A306202 Matula-Goebel numbers of rooted semi-identity trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A317707 Number of powerful rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A323795 Number of non-isomorphic weight-n sets of non-overlapping sets of sets.

Views

Author

Keywords

Comments

Examples