A292050 -id:A292050 - cp's OEIS frontend

A303026 Matula-Goebel numbers of series-reduced anti-binary (no unary or binary branchings) rooted trees.

1, 8, 16, 32, 64, 76, 128, 152, 212, 256, 304, 424, 512, 524, 608, 722, 848, 1024, 1048, 1216, 1244, 1444, 1532, 1696, 2014, 2048, 2096, 2432, 2488, 2876, 2888, 3064, 3392, 3524, 4028, 4096, 4192, 4864, 4976, 4978, 5204, 5618, 5752, 5776, 6128, 6476, 6784

Offset: 1

Gus Wiseman, Aug 15 2018

nonn

			The sequence of series-reduced anti-binary rooted trees together with their Matula-Goebel numbers begins:
     1: o
     8: (ooo)
    16: (oooo)
    32: (ooooo)
    64: (oooooo)
    76: (oo(ooo))
   128: (ooooooo)
   152: (ooo(ooo))
   212: (oo(oooo))
   256: (oooooooo)
   304: (oooo(ooo))
   424: (ooo(oooo))
   512: (ooooooooo)
   524: (oo(ooooo))
   608: (ooooo(ooo))
   722: (o(ooo)(ooo))
   848: (oooo(oooo))
  1024: (oooooooooo)
  1048: (ooo(ooooo))
  1216: (oooooo(ooo))
  1244: (oo(oooooo))
  1444: (oo(ooo)(ooo))
  1532: (oo(oo(ooo)))
  1696: (ooooo(oooo))
  2014: (o(ooo)(oooo))
  2048: (ooooooooooo)

Cf. A000081, A000598, A001190, A001678, A007097, A061775, A102403, A111299, A292050, A298422, A298424.

Cf. A303022, A303023, A303024, A303025, A303027.

azQ[n_]:=Or[n==1,And[PrimeOmega[n]>2,And@@Cases[FactorInteger[n],{p_,_}:>azQ[PrimePi[p]]]]]
Select[Range[1000],azQ]

A320270 Number of unlabeled balanced semi-binary rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 6, 7, 10, 13, 19, 25, 35, 46, 65, 88, 124, 171, 242, 334, 470, 653, 921, 1287, 1822, 2565, 3640, 5144, 7311, 10360, 14734, 20918, 29781, 42361, 60389, 86069, 122893, 175479, 250922, 358863

Offset: 1

Gus Wiseman, Oct 08 2018

nonn

An unlabeled rooted tree is semi-binary if all out-degrees are <= 2, and balanced if all leaves are the same distance from the root. The number of semi-binary trees with n nodes is equal to the number of binary trees with n+1 leaves; see A001190.

			The a(1) = 1 through a(7) = 6 balanced semi-binary rooted trees:
  o  (o)  (oo)   ((oo))   (((oo)))   ((o)(oo))    ((oo)(oo))
          ((o))  (((o)))  ((o)(o))   ((((oo))))   (((o)(oo)))
                          ((((o))))  (((o)(o)))   (((((oo)))))
                                     (((((o)))))  ((((o)(o))))
                                                  (((o))((o)))
                                                  ((((((o))))))

Gus Wiseman, The a(13) = 35 balanced semi-binary rooted trees.
Gus Wiseman, The a(15) = 65 balanced semi-binary rooted trees.
Gus Wiseman, The a(16) = 88 balanced semi-binary rooted trees.
Gus Wiseman, The a(18) = 171 balanced semi-binary rooted trees.

Cf. A001190, A048816, A079500, A111299, A292050, A298204, A301345, A320271.

saur[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[saur/@ptn]],SameQ@@Length/@Position[#,{}]&],{ptn,Select[IntegerPartitions[n-1],Length[#]<=2&]}]];
Table[Length[saur[n]],{n,20}]

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

A298205 Matula-Goebel numbers of rooted trees in which all outdegrees are either 0, 1, or 3.

Original entry on oeis.org

1, 2, 3, 5, 8, 11, 12, 18, 19, 20, 27, 30, 31, 37, 44, 45, 50, 61, 66, 67, 71, 75, 76, 99, 103, 110, 113, 114, 124, 125, 127, 148, 157, 165, 171, 186, 190, 193, 197, 222, 229, 242, 244, 268, 275, 279, 283, 284, 285, 310, 317, 331, 333, 353, 363, 366, 370, 379

Offset: 1

Gus Wiseman, Jan 14 2018

nonn

			Sequence of rooted trees begins:
1  o
2  (o)
3  ((o))
5  (((o)))
8  (ooo)
11 ((((o))))
12 (oo(o))
18 (o(o)(o))
19 ((ooo))
20 (oo((o)))
27 ((o)(o)(o))
30 (o(o)((o)))
31 (((((o)))))
37 ((oo(o)))
44 (oo(((o))))
45 ((o)(o)((o)))
50 (o((o))((o)))

Cf. A000081, A000598, A014591, A026424, A032305, A061775, A111299, A276625, A292050, A295461, A297571, A298126, A298118, A298120, A298204, A298207.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
stQ[n_]:=Or[n===1,With[{m=primeMS[n]},MemberQ[{1,3},Length[m]]&&And@@stQ/@m]];
Select[Range[10000],stQ]

A317097 Number of rooted trees with n nodes where the number of distinct branches under each node is <= 2.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 46, 106, 248, 583, 1393, 3343, 8111, 19801, 48719, 120489, 299787, 749258, 1881216, 4741340, 11993672, 30436507, 77471471, 197726053, 505917729, 1297471092, 3334630086, 8587369072, 22155278381, 57259037225, 148222036272, 384272253397

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

There can be more than two branches as long as there are not three distinct branches.

			The a(5) = 9 trees:
  ((((o))))
  (((oo)))
  ((o(o)))
  ((ooo))
  (o((o)))
  (o(oo))
  ((o)(o))
  (oo(o))
  (oooo)

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

Cf. A000081, A000598, A001190, A003238, A055277, A111299, A292050, A298204, A301344, A317098.

semisameQ[u_]:=Length[Union[u]]<=2;
nms[n_]:=nms[n]=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],semisameQ],{ptn,IntegerPartitions[n-1]}]];
Table[Length[nms[n]],{n,10}]

seq(n)={my(v=vector(n)); v[1]=1; for(n=1, n-1, v[n+1]=sum(k=1, n-1, sumdiv(k, d, v[d])*sumdiv(n-k, d, v[d])/2) + sumdiv(n, d, v[n/d]*(1 - (d-1)/2)) ); v} \\ Andrew Howroyd, Aug 28 2018

Terms a(20) and beyond from Andrew Howroyd, Aug 28 2018

A317098 Number of series-reduced rooted trees with n unlabeled leaves where the number of distinct branches under each node is <= 2.

Original entry on oeis.org

1, 1, 2, 5, 12, 31, 80, 214, 576, 1595, 4448, 12625, 36146, 104662, 305251, 897417, 2654072, 7895394, 23601441, 70871693, 213660535, 646484951, 1962507610, 5975425743, 18243789556, 55841543003, 171320324878, 526738779846, 1622739134873, 5008518981670

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

There can be more than two branches as long as there are not three distinct branches.

			The a(5) = 12 trees:
  (o(o(o(oo))))
  (o(o(ooo)))
  (o((oo)(oo)))
  (o(oo(oo)))
  (o(oooo))
  ((oo)(o(oo)))
  ((oo)(ooo))
  (oo(o(oo)))
  (oo(ooo))
  (o(oo)(oo))
  (ooo(oo))
  (ooooo)

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

Cf. A000081, A000598, A001190, A055277, A111299, A292050, A298204, A301344, A317097.

semisameQ[u_]:=Length[Union[u]]<=2;
nms[n_]:=nms[n]=If[n==1,{{1}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],semisameQ],{ptn,Rest[IntegerPartitions[n]]}]];
Table[Length[nms[n]],{n,10}]

seq(n)={my(v=vector(n)); v[1]=1; for(n=2, n, v[n]=sum(k=1, n-1, sumdiv(k, d, v[d])*sumdiv(n-k, d, v[d])/2) + sumdiv(n, d, v[n/d]*(1 - (d-1)/2)) ); v} \\ Andrew Howroyd, Aug 19 2018

Terms a(21) and beyond from Andrew Howroyd, Aug 19 2018

A320271 Number of unlabeled semi-binary rooted trees with n nodes in which the non-leaf branches directly under any given node are all equal.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 17, 26, 46, 72, 124, 196, 329, 525, 871, 1396, 2293, 3689, 6028, 9717, 15817, 25534, 41475, 67009, 108680, 175689, 284698, 460387, 745610, 1205997, 1952478, 3158475, 5112349, 8270824, 13385466, 21656290, 35045445, 56701735, 91753208

Offset: 1

Gus Wiseman, Oct 08 2018

nonn

An unlabeled rooted tree is semi-binary if all out-degrees are <= 2. The number of semi-binary trees with n nodes is equal to the number of binary trees with n+1 leaves; see A001190.

			The a(1) = 1 through a(7) = 17 semi-binary rooted trees:
  o  (o)  (oo)   ((oo))   (o(oo))    ((o(oo)))    ((oo)(oo))
          ((o))  (o(o))   (((oo)))   (o((oo)))    (o(o(oo)))
                 (((o)))  ((o)(o))   (o(o(o)))    (((o(oo))))
                          ((o(o)))   ((((oo))))   ((o((oo))))
                          (o((o)))   (((o)(o)))   ((o(o(o))))
                          ((((o))))  (((o(o))))   (o(((oo))))
                                     ((o((o))))   (o((o)(o)))
                                     (o(((o))))   (o((o(o))))
                                     (((((o)))))  (o(o((o))))
                                                  (((((oo)))))
                                                  ((((o)(o))))
                                                  ((((o(o)))))
                                                  (((o))((o)))
                                                  (((o((o)))))
                                                  ((o(((o)))))
                                                  (o((((o)))))
                                                  ((((((o))))))

Cf. A001190, A003238, A111299, A126656, A292050, A298204, A301345, A317712, A320222, A320230, A320270.

crb[n_]:=Switch[n,1,1,2,1,3,2,?EvenQ,crb[n-1]+crb[n-2],?OddQ,crb[n-1]+crb[n-2]+crb[(n-1)/2]]
Array[crb,20]

       a(1) = 1,
       a(2) = 1,
       a(3) = 2,
  a(n even) = a(n-1) + a(n-2),
   a(n odd) = a(n-1) + a(n-2) + a((n-1)/2).

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

A303026 Matula-Goebel numbers of series-reduced anti-binary (no unary or binary branchings) rooted trees.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A320270 Number of unlabeled balanced semi-binary rooted trees with n nodes.

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

A298205 Matula-Goebel numbers of rooted trees in which all outdegrees are either 0, 1, or 3.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A317097 Number of rooted trees with n nodes where the number of distinct branches under each node is <= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A317098 Number of series-reduced rooted trees with n unlabeled leaves where the number of distinct branches under each node is <= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A320271 Number of unlabeled semi-binary rooted trees with n nodes in which the non-leaf branches directly under any given node are all equal.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples