A331965 -id:A331965 - cp's OEIS frontend

A331992 Matula-Goebel numbers of semi-lone-child-avoiding achiral rooted trees.

1, 2, 4, 8, 9, 16, 27, 32, 49, 64, 81, 128, 243, 256, 343, 361, 512, 529, 729, 1024, 2048, 2187, 2401, 2809, 4096, 6561, 6859, 8192, 10609, 12167, 16384, 16807, 17161, 19683, 32768, 51529, 59049, 65536, 96721, 117649, 130321, 131072, 148877, 175561, 177147

Offset: 1

Gus Wiseman, Feb 06 2020

nonn

A rooted tree is semi-lone-child-avoiding if there are no vertices with exactly one child unless that child is an endpoint/leaf.
In an achiral rooted tree, the branches of any given vertex are all equal.
The Matula-Goebel number of a 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.
Consists of one, two, and all numbers of the form prime(j)^k where k > 1 and j is already in the sequence.

			The sequence of all semi-lone-child-avoiding achiral rooted trees together with their Matula-Goebel numbers begins:
     1: o
     2: (o)
     4: (oo)
     8: (ooo)
     9: ((o)(o))
    16: (oooo)
    27: ((o)(o)(o))
    32: (ooooo)
    49: ((oo)(oo))
    64: (oooooo)
    81: ((o)(o)(o)(o))
   128: (ooooooo)
   243: ((o)(o)(o)(o)(o))
   256: (oooooooo)
   343: ((oo)(oo)(oo))
   361: ((ooo)(ooo))
   512: (ooooooooo)
   529: (((o)(o))((o)(o)))
   729: ((o)(o)(o)(o)(o)(o))
  1024: (oooooooooo)

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.
Gus Wiseman, The first 36 semi-lone-child-avoiding achiral rooted trees.

Except for two, a subset of A025475 (nonprime prime powers).
Not requiring achirality gives A331935.
The semi-achiral version is A331936.
The fully-chiral version is A331963.
The semi-chiral version is A331994.
The non-semi version is counted by A331967.
The enumeration of these trees by vertices is A331991.
Achiral rooted trees are counted by A003238.
MG-numbers of achiral rooted trees are A214577.
Cf. A001678, A007097, A050381, A061775, A167865, A196050, A276625, A280996, A291441, A291636, A320230, A320269, A331912, A331933, A331965.

msQ[n_]:=n<=2||!PrimeQ[n]&&Length[FactorInteger[n]]<=1&&And@@msQ/@PrimePi/@First/@FactorInteger[n];
Select[Range[10000],msQ]

Intersection of A214577 (achiral) and A331935 (semi-lone-child-avoiding).

A331993 Number of semi-lone-child-avoiding rooted semi-identity trees with n unlabeled vertices.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 22, 43, 90, 185, 393, 835, 1802, 3904, 8540, 18756, 41463, 92022, 205179, 459086, 1030917, 2321949, 5245104, 11878750, 26967957, 61359917, 139902251, 319591669, 731385621, 1676573854, 3849288924, 8850674950, 20378544752, 46982414535

Offset: 1

Gus Wiseman, Feb 05 2020

nonn

Semi-lone-child-avoiding means there are no vertices with exactly one child unless that child is an endpoint/leaf.

In a semi-identity tree, the non-leaf branches of any given vertex are distinct.

			The a(1) = 1 through a(7) = 11 trees:
  o  (o)  (oo)  (ooo)   (oooo)   (ooooo)    (oooooo)
                (o(o))  (o(oo))  (o(ooo))   (o(oooo))
                        (oo(o))  (oo(oo))   (oo(ooo))
                                 (ooo(o))   (ooo(oo))
                                 ((o)(oo))  (oooo(o))
                                 (o(o(o)))  ((o)(ooo))
                                            (o(o)(oo))
                                            (o(o(oo)))
                                            (o(oo(o)))
                                            (oo(o(o)))
                                            ((o)(o(o)))

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

Not requiring any lone-child-avoidance gives A306200.
The locally disjoint case is A324969 (essentially A000045).
Matula-Goebel numbers of these trees are A331994.
Lone-child-avoiding rooted identity trees are A000007.
Semi-lone-child-avoiding rooted trees are A331934.
Semi-lone-child-avoiding rooted identity trees are A331964.
Lone-child-avoiding rooted semi-identity trees are A331966.
Cf. A001678, A004111, A300660, A316694, A331683, A331686, A331783, A331875, A331933, A331963, A331965.

sssb[n_]:=Switch[n,1,{{}},2,{{{}}},_,Join@@Function[c,Select[Union[Sort/@Tuples[sssb/@c]],UnsameQ@@DeleteCases[#,{}]&]]/@Rest[IntegerPartitions[n-1]]];
Table[Length[sssb[n]],{n,10}]

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
seq(n)={my(v=[0]); for(n=1, n-1, v=concat(v, 1 + vecsum(WeighT(v)) - v[n])); v[1]=1; v} \\ Andrew Howroyd, Feb 09 2020

Terms a(26) and beyond from Andrew Howroyd, Feb 09 2020

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]

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

A331992 Matula-Goebel numbers of semi-lone-child-avoiding achiral rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A331993 Number of semi-lone-child-avoiding rooted semi-identity trees with n unlabeled vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions