A306201 -id:A306201 - cp's OEIS frontend

A111299 Numbers whose Matula tree is a binary tree (i.e., root has degree 2 and all nodes except root and leaves have degree 3).

4, 14, 49, 86, 301, 454, 886, 1589, 1849, 3101, 3986, 6418, 9761, 13766, 13951, 19049, 22463, 26798, 31754, 48181, 51529, 57026, 75266, 85699, 93793, 100561, 111139, 128074, 137987, 196249, 199591, 203878, 263431, 295969, 298154, 302426, 426058, 448259, 452411

Offset: 1

Keith Briggs, Nov 02 2005

nonn

This sequence should probably start with 1. Then a number k is in the sequence iff k = 1 or k = prime(x) * prime(y) with x and y already in the sequence. - Gus Wiseman, May 04 2021

			From _Gus Wiseman_, May 04 2021: (Start)
The sequence of trees (starting with 1) begins:
     1: o
     4: (oo)
    14: (o(oo))
    49: ((oo)(oo))
    86: (o(o(oo)))
   301: ((oo)(o(oo)))
   454: (o((oo)(oo)))
   886: (o(o(o(oo))))
  1589: ((oo)((oo)(oo)))
  1849: ((o(oo))(o(oo)))
  3101: ((oo)(o(o(oo))))
  3986: (o((oo)(o(oo))))
  6418: (o(o((oo)(oo))))
  9761: ((o(oo))((oo)(oo)))
(End)

Kevin Ryde, Table of n, a(n) for n = 1..5000 (terms 1..186 from Charles R Greathouse IV)
Keith Briggs, Matula numbers and rooted trees
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Kevin Ryde, PARI/GP Code
Index entries for sequences related to Matula-Goebel numbers

Cf. A245824 (by number of leaves).
Cf. A005517, A005518, A061773, A245824.
These trees are counted by 2*A001190 - 1.
The semi-binary version is A292050 (counted by A001190).
The semi-identity case is A339193 (counted by A063895).
A000081 counts unlabeled rooted trees with n nodes.
A007097 ranks rooted chains.
A276625 ranks identity trees, counted by A004111.
A306202 ranks semi-identity trees, counted by A306200.
A306203 ranks balanced semi-identity trees, counted by A306201.
A331965 ranks lone-child avoiding semi-identity trees, counted by A331966.
Cf. A036656, A061775, A196050, A291636, A320230, A331935, A331965.

nn=20000;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
binQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]===2,And@@binQ/@m]]];
Select[Range[2,nn],binQ] (* Gus Wiseman, Aug 28 2017 *)

i(n)=n==2 || is(primepi(n))
is(n)=if(n<14,return(n==4)); my(f=factor(n),t=#f[,1]); if(t>1, t==2 && f[1,2]==1 && f[2,2]==1 && i(f[1,1]) && i(f[2,1]), f[1,2]==2 && i(f[1,1])) \\ Charles R Greathouse IV, Mar 29 2013

list(lim)=my(v=List(), t); forprime(p=2, sqrt(lim), t=p; forprime(q=p, lim\t, if(i(p)&&i(q), listput(v, t*q)))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Mar 29 2013

PARI
```
\\ Also see links.
```

The Matula tree of k is defined as follows:
matula(k):
    create a node labeled k
    for each prime factor m of k:
       add the subtree matula(prime(m)), by an edge labeled m
    return the node

Definition corrected by Charles R Greathouse IV, Mar 29 2013

a(27)-a(39) from Charles R Greathouse IV, Mar 29 2013

A306200 Number of unlabeled rooted semi-identity trees with n nodes.

Original entry on oeis.org

0, 1, 1, 2, 4, 8, 18, 41, 98, 237, 591, 1488, 3805, 9820, 25593, 67184, 177604, 472177, 1261998, 3388434, 9136019, 24724904, 67141940, 182892368, 499608724, 1368340326, 3756651116, 10336434585, 28499309291, 78727891420, 217870037932, 603934911859, 1676720329410

Offset: 0

Gus Wiseman, Jan 29 2019

nonn

A rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees.

			The a(1) = 1 through a(7) = 8 trees:
  o  (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)))   ((o)(oo))
                          ((((o))))  ((o(oo)))
                                     ((oo(o)))
                                     (o((oo)))
                                     (o(o(o)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o(o))))
                                     ((o)((o)))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))

Alois P. Heinz, Table of n, a(n) for n = 0..2166

Cf. A000081, A004111, A276625, A301700, A306201, A316471, A316474, A317708, A317712, A317718.

b:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
      add(b(n-i*j, i-1)*binomial(a(i), j), j=0..n/i))
    end:
a:= n-> `if`(n=0, 0, b(n-1$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Jan 29 2019

ursit[n_]:=Join@@Table[Select[Union[Sort/@Tuples[ursit/@ptn]],UnsameQ@@DeleteCases[#,{}]&],{ptn,IntegerPartitions[n-1]}];
Table[Length[ursit[n]],{n,10}]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0 || i == 1, 1,
     Sum[b[n - i*j, i - 1]*Binomial[a[i], j], {j, 0, n/i}]];
a[n_] := If[n == 0, 0, b[n - 1, n - 1]];
a /@ Range[0, 35] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

More terms from Alois P. Heinz, Jan 29 2019

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)))...

Original entry on oeis.org

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

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]

A306203 Matula-Goebel numbers of balanced rooted semi-identity trees.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 11, 16, 17, 19, 21, 31, 32, 53, 57, 59, 64, 67, 73, 85, 127, 128, 131, 133, 159, 241, 256, 269, 277, 311, 331, 335, 365, 367, 371, 393, 399, 439, 512, 649, 709, 719, 739, 751, 917, 933, 937, 1007, 1024, 1113, 1139, 1205, 1241, 1345, 1523

Offset: 1

Gus Wiseman, Jan 29 2019

nonn

A rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees. It is balanced if all leaves are the same distance from the root. The only balanced rooted identity trees are rooted paths.

			The sequence of all unlabeled balanced rooted semi-identity trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: ((oo))
   8: (ooo)
  11: ((((o))))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  21: ((o)(oo))
  31: (((((o)))))
  32: (ooooo)
  53: ((oooo))
  57: ((o)(ooo))
  59: ((((oo))))
  64: (oooooo)
  67: (((ooo)))
  73: (((o)(oo)))
  85: (((o))((oo)))

Cf. A000081, A004111, A007097, A048816, A184155, A276625, A306200, A306201, A306202, A316467, A317710.

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]];
mgtree[n_]:=If[n==1,{},mgtree/@primeMS[n]];
Select[Range[100],And[psidQ[#],SameQ@@Length/@Position[mgtree[#],{}]]&]

A339193 Matula-Goebel numbers of unlabeled binary rooted semi-identity trees.

Original entry on oeis.org

1, 4, 14, 86, 301, 886, 3101, 3986, 13766, 13951, 19049, 48181, 57026, 75266, 85699, 199591, 263431, 295969, 298154, 302426, 426058, 882899

Offset: 1

Gus Wiseman, Mar 14 2021

nonn

Definition: A positive integer belongs to the sequence iff it is 1, 4, or a squarefree semiprime whose prime indices both 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.
In a semi-identity tree, only the non-leaf branches of any given vertex are distinct. Alternatively, a rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees.
The Matula-Goebel number of an unlabeled rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.

			The sequence of terms together with the corresponding unlabeled rooted trees begins:
      1: o
      4: (oo)
     14: (o(oo))
     86: (o(o(oo)))
    301: ((oo)(o(oo)))
    886: (o(o(o(oo))))
   3101: ((oo)(o(o(oo))))
   3986: (o((oo)(o(oo))))
  13766: (o(o(o(o(oo)))))
  13951: ((oo)((oo)(o(oo))))
  19049: ((o(oo))(o(o(oo))))
  48181: ((oo)(o(o(o(oo)))))
  57026: (o((oo)(o(o(oo)))))
  75266: (o(o((oo)(o(oo)))))
  85699: ((o(oo))((oo)(o(oo))))

Gus Wiseman, The sequence of all unlabeled binary rooted semi-identity trees by Matula-Goebel number.

Counting these trees by number of nodes gives A063895.
A000081 counts unlabeled rooted trees with n nodes.
A111299 ranks binary trees, counted by A001190.
A276625 ranks identity trees, counted by A004111.
A306202 ranks semi-identity trees, counted by A306200.
A306203 ranks balanced semi-identity trees, counted by A306201.
A331965 ranks lone-child avoiding semi-identity trees, counted by A331966.
Cf. A007097, A061775, A196050, A291636, A331963, A331964.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
mgbiQ[n_]:=Or[n==1,n==4,SquareFreeQ[n]&&PrimeOmega[n]==2&&And@@mgbiQ/@primeMS[n]];
Select[Range[1000],mgbiQ]

A306269 Regular triangle read by rows where T(n,k) is the number of unlabeled balanced rooted semi-identity trees with n >= 1 nodes and depth 0 <= k < n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 2, 1, 1, 1, 0, 1, 2, 2, 1, 1, 1, 0, 1, 3, 3, 2, 1, 1, 1, 0, 1, 3, 4, 3, 2, 1, 1, 1, 0, 1, 5, 6, 5, 3, 2, 1, 1, 1, 0, 1, 5, 9, 7, 5, 3, 2, 1, 1, 1, 0, 1, 7, 12, 12, 8, 5, 3, 2, 1, 1, 1, 0, 1, 8, 17, 17, 13, 8, 5, 3, 2, 1, 1, 1

Offset: 1

Gus Wiseman, Feb 01 2019

A rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees. It is balanced if all leaves are the same distance from the root.

			Triangle begins:
  1
  0  1
  0  1  1
  0  1  1  1
  0  1  1  1  1
  0  1  2  1  1  1
  0  1  2  2  1  1  1
  0  1  3  3  2  1  1  1
  0  1  3  4  3  2  1  1  1
  0  1  5  6  5  3  2  1  1  1
  0  1  5  9  7  5  3  2  1  1  1
  0  1  7 12 12  8  5  3  2  1  1  1
  0  1  8 17 17 13  8  5  3  2  1  1  1
  0  1 10 25 26 20 14  8  5  3  2  1  1  1
  0  1 12 34 39 31 21 14  8  5  3  2  1  1  1
The postpositive terms of row 9 {3, 4, 3, 2} count the following trees:
  ((ooooooo))   (((oooooo)))    ((((ooooo))))    (((((oooo)))))
  ((o)(ooooo))  (((o)(oooo)))   ((((o)(ooo))))   (((((o)(oo)))))
  ((oo)(oooo))  (((oo)(ooo)))   ((((o))((oo))))
                (((o))((ooo)))

Alois P. Heinz, Rows n = 1..200, flattened
Gus Wiseman, Unlabeled balanced rooted semi-identity trees with 12 nodes, organized by depth.

Row sums give A306201.
T(2n-1,n) gives A306274.
Cf. A000081, A004111, A048816, A079500, A120803, A184155, A276625, A306200, A306202, A306203, A320222, A320270.

ubk[n_,k_]:=Select[Join@@Table[Select[Union[Sort/@Tuples[ubk[#,k-1]&/@ptn]],UnsameQ@@DeleteCases[#,{}]&],{ptn,IntegerPartitions[n-1]}],SameQ[k,##]&@@Length/@Position[#,{}]&];
Table[Length[ubk[n,k]],{n,1,10},{k,0,n-1}]

A343663 Number of unlabeled binary rooted semi-identity plane trees with 2*n - 1 nodes.

Original entry on oeis.org

1, 1, 2, 4, 12, 34, 108, 344, 1136, 3796, 12920, 44442, 154596, 542336, 1917648, 6825464, 24439008, 87962312, 318087216, 1155090092, 4210494616, 15400782912, 56508464736, 207935588586, 767162495940, 2837260332472, 10516827106016, 39063666532784, 145378611426512

Offset: 1

Gus Wiseman, May 05 2021

nonn

In a semi-identity tree, only the non-leaf branches of any given vertex are required to be distinct. Alternatively, a rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees.

			The a(1) = 1 through a(5) = 12 trees:
  o  (oo)  ((oo)o)  (((oo)o)o)  ((((oo)o)o)o)
           (o(oo))  ((o(oo))o)  (((o(oo))o)o)
                    (o((oo)o))  (((oo)o)(oo))
                    (o(o(oo)))  ((o((oo)o))o)
                                ((o(o(oo)))o)
                                ((o(oo))(oo))
                                ((oo)((oo)o))
                                ((oo)(o(oo)))
                                (o(((oo)o)o))
                                (o((o(oo))o))
                                (o(o((oo)o)))
                                (o(o(o(oo))))

Andrew Howroyd, Table of n, a(n) for n = 1..500
Samuele Giraudo, The combinator M and the Mockingbird lattice, arXiv:2204.03586 [math.CO], 2022.
Samuele Giraudo, Mockingbird lattices, Séminaire Lotharingien de Combinatoire XX, Proceedings of the 34th Conf. on Formal Power, Series and Algebraic Combinatorics (Bangalore, India, 2022).

The not necessarily semi-identity version is A000108.
The non-plane version is A063895, ranked by A339193.
The Matula-Goebel numbers in the non-plane case are A339193.
The not-necessarily binary version is A343937.
A000081 counts unlabeled rooted trees with n nodes.
2*A001190 - 1 counts binary trees, ranked by A111299.
A001190 counts semi-binary trees, ranked by A292050.
A004111 counts identity trees, ranked by A276625.
A306200 counts semi-identity trees, ranked by A306202.
A306201 counts balanced semi-identity trees, ranked by A306203.
A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
Cf. A001678, A320230, A331934, A331963, A331964.

crsiq[n_]:=Join@@Table[Select[Union[Tuples[crsiq/@ptn]],#=={}||#=={{},{}}||Length[#]==2&&(UnsameQ@@DeleteCases[#,{}])&],{ptn,Join@@Permutations/@IntegerPartitions[n-1]}];
Table[Length[crsiq[n]],{n,1,11,2}]
(* Second program: *)
m = 29; p[_] = 1;
Do[p[x_] = 1 + x + x (p[x]^2 - p[x^2]) + O[x]^m // Normal, {m}];
CoefficientList[p[x], x] (* Jean-François Alcover, May 09 2021, after Andrew Howroyd *)

seq(n)={my(p=O(1)); for(n=1, n, p=1 + x + x*(p^2-subst(p,x,x^2))); Vec(p)} \\ Andrew Howroyd, May 07 2021

G.f.: x*A(x) where A(x) satisfies A(x) = 1 + x + x*(A(x)^2 - A(x^2)). - Andrew Howroyd, May 07 2021

Terms a(13) and beyond from Andrew Howroyd, May 07 2021

A343937 Number of unlabeled semi-identity plane trees with n nodes.

Original entry on oeis.org

1, 1, 2, 5, 13, 38, 117, 375, 1224, 4095, 13925, 48006, 167259, 588189, 2084948, 7442125, 26725125, 96485782, 350002509, 1275061385, 4662936808, 17111964241, 62996437297, 232589316700, 861028450579, 3195272504259, 11884475937910, 44295733523881, 165420418500155

Offset: 1

Gus Wiseman, May 07 2021

nonn

In a semi-identity tree, only the non-leaf branches of any given vertex are required to be distinct. Alternatively, a rooted tree is a semi-identity tree iff the non-leaf branches of the root are all distinct and are themselves semi-identity trees.

			The a(1) = 1 through a(5) = 13 trees are the following. The number of nodes is the number of o's plus the number of brackets (...).
  o  (o)  (oo)   (ooo)    (oooo)
          ((o))  ((o)o)   ((o)oo)
                 ((oo))   ((oo)o)
                 (o(o))   ((ooo))
                 (((o)))  (o(o)o)
                          (o(oo))
                          (oo(o))
                          (((o))o)
                          (((o)o))
                          (((oo)))
                          ((o(o)))
                          (o((o)))
                          ((((o))))

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

The not necessarily semi-identity version is A000108.
The non-plane binary version is A063895, ranked by A339193.
The non-plane version is A306200, ranked by A306202.
The binary case is A343663.
A000081 counts unlabeled rooted trees with n nodes.
A001190*2 - 1 counts binary trees, ranked by A111299.
A001190 counts semi-binary trees, ranked by A292050.
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, A320230, A331934, A331963, A331964.

arsiq[n_]:=Join@@Table[Select[Union[Tuples[arsiq/@ptn]],#=={}||(UnsameQ@@DeleteCases[#,{}])&],{ptn,Join@@Permutations/@IntegerPartitions[n-1]}];
Table[Length[arsiq[n]],{n,10}]

F(p)={my(n=serprec(p,x)-1, q=exp(x*y + O(x*x^n))*prod(k=2, n, (1 + y*x^k + O(x*x^n))^polcoef(p,k,x)) ); sum(k=0, n, k!*polcoef(q,k,y))}
seq(n)={my(p=O(x)); for(n=1, n, p=x*F(p)); Vec(p)} \\ Andrew Howroyd, May 08 2021

G.f.: A(x) satisfies A(x) = x*Sum_{j>=0} j!*[y^j] exp(x*y - Sum_{k>=1} (-y)^k*(A(x^k) - x^k)/k). - Andrew Howroyd, May 08 2021

Terms a(17) and beyond from Andrew Howroyd, May 08 2021

cp's OEIS Frontend

A111299 Numbers whose Matula tree is a binary tree (i.e., root has degree 2 and all nodes except root and leaves have degree 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A306200 Number of unlabeled rooted semi-identity trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A306203 Matula-Goebel numbers of balanced rooted semi-identity trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A339193 Matula-Goebel numbers of unlabeled binary rooted semi-identity trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A306269 Regular triangle read by rows where T(n,k) is the number of unlabeled balanced rooted semi-identity trees with n >= 1 nodes and depth 0 <= k < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica