A050381 -id:A050381 - cp's OEIS frontend

A331933 Number of semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex.

1, 1, 1, 2, 4, 6, 12, 18, 33, 52, 90, 142, 242, 384, 639, 1028, 1688, 2716, 4445, 7161, 11665, 18839, 30595, 49434, 80199, 129637, 210079, 339750, 550228, 889978, 1440909, 2330887, 3772845, 6103823, 9878357, 15982196, 25863454, 41845650, 67713550, 109559443

Offset: 1

Gus Wiseman, Feb 03 2020

nonn

A rooted tree is semi-lone-child-avoiding if there are no vertices with exactly one child unless the child is an endpoint/leaf.

			The a(1) = 1 through a(8) = 18 trees:
  o  (o)  (oo)  (ooo)   (oooo)    (ooooo)    (oooooo)
                (o(o))  (o(oo))   (o(ooo))   (o(oooo))
                        (oo(o))   (oo(oo))   (oo(ooo))
                        ((o)(o))  (ooo(o))   (ooo(oo))
                                  (o(o)(o))  (oooo(o))
                                  (o(o(o)))  ((oo)(oo))
                                             (o(o(oo)))
                                             (o(oo(o)))
                                             (oo(o)(o))
                                             (oo(o(o)))
                                             ((o)(o)(o))
                                             (o((o)(o)))

Andrew Howroyd, Table of n, a(n) for n = 1..1000
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.
Gus Wiseman, The a(11) = 90 semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex.

Not requiring lone-child-avoidance gives A320222.
The non-semi version is A320268.
Matula-Goebel numbers of these trees are A331936.
Achiral trees are A003238.
Semi-identity trees are A306200.
Numbers S with at most one distinct prime index in S are A331912.
Semi-lone-child-avoiding rooted trees are A331934.
Cf. A000081, A001678, A004111, A050381, A214577, A291636, A320230, A320269, A331784, A331872, A331914, A331935, A331966.

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

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sum(i=2, n-2, ((n-1)\i)*v[i])); v} \\ Andrew Howroyd, Feb 09 2020

a(n) = 1 + Sum_{i=2..n-2} floor((n-1)/i)*a(i). - Andrew Howroyd, Feb 09 2020

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

A331871 Matula-Goebel numbers of lone-child-avoiding locally disjoint rooted trees.

Original entry on oeis.org

1, 4, 8, 14, 16, 28, 32, 38, 49, 56, 64, 76, 86, 98, 106, 112, 128, 152, 172, 196, 212, 214, 224, 256, 262, 304, 326, 343, 344, 361, 392, 424, 428, 448, 454, 512, 524, 526, 608, 622, 652, 686, 688, 722, 766, 784, 848, 856, 886, 896, 908, 1024, 1042, 1048, 1052

Offset: 1

Gus Wiseman, Feb 02 2020

nonn

First differs from A320269 in having 1589, the Matula-Goebel number of the tree ((oo)((oo)(oo))).
First differs from A331683 in having 49.
A rooted tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other (inequivalent) child of the same vertex.
Lone-child-avoiding means there are no unary branchings.
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 and all nonprime numbers whose distinct prime indices are pairwise coprime and already belong to the sequence, where a singleton is always considered to be pairwise coprime. A prime index of n is a number m such that prime(m) divides n.

			The sequence of all lone-child-avoiding locally disjoint rooted trees together with their Matula-Goebel numbers begins:
    1: o
    4: (oo)
    8: (ooo)
   14: (o(oo))
   16: (oooo)
   28: (oo(oo))
   32: (ooooo)
   38: (o(ooo))
   49: ((oo)(oo))
   56: (ooo(oo))
   64: (oooooo)
   76: (oo(ooo))
   86: (o(o(oo)))
   98: (o(oo)(oo))
  106: (o(oooo))
  112: (oooo(oo))
  128: (ooooooo)
  152: (ooo(ooo))
  172: (oo(o(oo)))
  196: (oo(oo)(oo))
The sequence of terms together with their prime indices begins:
     1: {}                  212: {1,1,16}
     4: {1,1}               214: {1,28}
     8: {1,1,1}             224: {1,1,1,1,1,4}
    14: {1,4}               256: {1,1,1,1,1,1,1,1}
    16: {1,1,1,1}           262: {1,32}
    28: {1,1,4}             304: {1,1,1,1,8}
    32: {1,1,1,1,1}         326: {1,38}
    38: {1,8}               343: {4,4,4}
    49: {4,4}               344: {1,1,1,14}
    56: {1,1,1,4}           361: {8,8}
    64: {1,1,1,1,1,1}       392: {1,1,1,4,4}
    76: {1,1,8}             424: {1,1,1,16}
    86: {1,14}              428: {1,1,28}
    98: {1,4,4}             448: {1,1,1,1,1,1,4}
   106: {1,16}              454: {1,49}
   112: {1,1,1,1,4}         512: {1,1,1,1,1,1,1,1,1}
   128: {1,1,1,1,1,1,1}     524: {1,1,32}
   152: {1,1,1,8}           526: {1,56}
   172: {1,1,14}            608: {1,1,1,1,1,8}
   196: {1,1,4,4}           622: {1,64}

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.

Not requiring local disjointness gives A291636.
Not requiring lone-child avoidance gives A316495.
A superset of A320269.
These trees are counted by A331680.
The semi-identity tree version is A331683.
The version containing 2 is A331873.
Cf. A001678, A007097, A050381, A061775, A196050, A302569, A302696, A316473, A316694, A316696, A316697, A331682, A331686, A331687, A331872, A331935.

msQ[n_]:=n==1||!PrimeQ[n]&&(PrimePowerQ[n]||CoprimeQ@@PrimePi/@First/@FactorInteger[n])&&And@@msQ/@PrimePi/@First/@FactorInteger[n];
Select[Range[1000],msQ]

Intersection of A291636 and A316495.

A331991 Number of semi-lone-child-avoiding achiral rooted trees with n vertices.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 4, 1, 5, 1, 5, 4, 4, 1, 7, 1, 7, 5, 6, 1, 7, 3, 7, 5, 7, 1, 13, 1, 8, 6, 6, 6, 10, 1, 9, 7, 9, 1, 15, 1, 12, 12, 8, 1, 12, 4, 13, 6, 11, 1, 15, 7, 13, 9, 9, 1, 17, 1, 15, 15, 9, 8, 21, 1, 13, 8, 16, 1, 18, 1, 12, 16, 11, 8, 21, 1

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 a(n) trees for n = 2, 3, 5, 7, 11, 13:
  (o)  (oo)  (oooo)    (oooooo)     (oooooooooo)        (oooooooooooo)
             ((o)(o))  ((oo)(oo))   ((oooo)(oooo))      ((ooooo)(ooooo))
                       ((o)(o)(o))  ((o)(o)(o)(o)(o))   ((ooo)(ooo)(ooo))
                                    (((o)(o))((o)(o)))  ((oo)(oo)(oo)(oo))
                                                        ((o)(o)(o)(o)(o)(o))

Seiichi Manyama, Table of n, a(n) for n = 1..10000
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.

Matula-Goebel numbers of these trees are A331992.
The fully lone-child-avoiding case is A167865.
The semi-achiral version is A331933.
Not requiring achirality gives A331934.
The identity tree version is A331964.
The semi-identity tree version is A331993.
Achiral rooted trees are counted by A003238.
Lone-child-avoiding semi-achiral trees are A320268.
Cf. A000081, A004111, A050381, A001678, A214577, A289079, A320222, A331912, A331935, A331936, A331963, A331967, A331994.

ab[n_]:=If[n<=2,1,Sum[ab[d],{d,Most[Divisors[n-1]]}]];
Array[ab,100]

a(1) = a(2) = 1; a(n + 1) = Sum_{d|n, d 1.

G.f. A(x) satisfies: A(x) = x * (1 + (1/(1 + x)) * Sum_{k>=1} A(x^k)). - Ilya Gutkovskiy, Feb 25 2020

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

Original entry on oeis.org

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

A318187 Number of totally transitive rooted trees with n leaves.

Original entry on oeis.org

2, 2, 4, 8, 16, 32, 62, 122, 234, 451, 857, 1630, 3068, 5772, 10778, 20093, 37259

Offset: 1

Gus Wiseman, Aug 20 2018

A rooted tree is totally transitive if every branch of the root is totally transitive and every branch of a branch of the root is also a branch of the root.

			The a(5) = 16 totally transitive rooted trees with 5 leaves:
  (o(o)(o(o)(o)))
  (o(o)(o)(o(o)))
  (o(o)(o)(o)(o))
  (o(o)(oo(o)))
  (oo(o)(o(o)))
  (o(o)(o)(oo))
  (oo(o)(o)(o))
  (o(o)(ooo))
  (o(oo)(oo))
  (oo(o)(oo))
  (ooo(o)(o))
  (o(oooo))
  (oo(ooo))
  (ooo(oo))
  (oooo(o))
  (ooooo)

Cf. A000081, A000669, A001678, A004111, A050381, A279861, A290689, A290760, A290822, A318185, A318186.

totralv[n_]:=totralv[n]=If[n==1,{{},{{}}},Join@@Table[Select[Union[Sort/@Tuples[totralv/@c]],Complement[Union@@#,#]=={}&],{c,Select[IntegerPartitions[n],Length[#]>1&]}]];
Table[Length[totralv[n]],{n,8}]

A031148 Number of series-reduced planted trees with n leaves of 2 colors and no symmetries.

Original entry on oeis.org

2, 1, 2, 5, 14, 43, 138, 455, 1540, 5305, 18546, 65616, 234546, 845683, 3072350, 11235393, 41326470, 152793376, 567518950, 2116666670, 7924062430, 29765741831, 112157686170, 423809991041, 1605622028100

Offset: 1

Christian G. Bower

N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Essentially the same as A052301. Cf. A000669, A001678, A038075, A050381.

Doubles (index 2+) under WEIGH transform.

A319377 Number of series-reduced rooted trees with n leaves of exactly two colors.

Original entry on oeis.org

1, 6, 30, 146, 719, 3590, 18283, 94648, 497757, 2652898, 14307845, 77958746, 428588051, 2374676854, 13247984959, 74357762790, 419604029622, 2379243477538, 13549087798391, 77458553063930, 444383895880897, 2557639072274418, 14763596994726379, 85449948037167684

Offset: 2

Andrew Howroyd, Sep 17 2018

nonn

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

Column 2 of A319376.

Cf. A000669, A050381.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
a:= n-> A(n, 2) -2*A(n, 1):
seq(a(n), n=2..30);  # Alois P. Heinz, Sep 18 2018

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n*k, b[n, n - 1, k]];
a[n_] := A[n, 2] - 2*A[n, 1];
a /@ Range[2, 30] (* Jean-François Alcover, Sep 24 2019, after Alois P. Heinz *)

\\ here R(n,k) is k-th column of A319254.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v}
seq(n)={(R(n,2)-2*R(n,1))[2..n]}

a(n) = A050381(n) - 2*A000669(n).

A339646 Number of inequivalent leaf colorings of series-reduced planted trees with n leaves using at most 2 colors.

Original entry on oeis.org

1, 2, 5, 22, 85, 402, 1885, 9453, 48090, 251476, 1333517, 7177585, 39048327, 214523186, 1188037961, 6626311639, 37186187183, 209826251622, 1189699762371, 6774803376279, 38730124684829, 222194778028278, 1278828889503773, 7381829822338301, 42725078403203912

Offset: 1

Andrew Howroyd, Dec 16 2020

nonn

Equivalence is up to permutation of the colors.

			a(1) = 1: 1.
a(2) = 2: (11), (12).
a(3) = 5: (111), (112), (1(11)), (1(12)), (1(22)).

The case that colors may not be interchanged is A050381.

Cf. A000669, A339645, A339647.

\\ See A339645 for cycleIndexSeries and InequivalentColoringsSeq.
InequivalentColoringsSeq(cycleIndexSeries(20),2)

a(n) = A339647(n) - A000669(n).

cp's OEIS Frontend

A331933 Number of semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A331871 Matula-Goebel numbers of lone-child-avoiding locally disjoint rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A331991 Number of semi-lone-child-avoiding achiral rooted trees with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A318187 Number of totally transitive rooted trees with n leaves.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A031148 Number of series-reduced planted trees with n leaves of 2 colors and no symmetries.

Views

Author

Keywords

Links

Crossrefs

Formula

A319377 Number of series-reduced rooted trees with n leaves of exactly two colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A339646 Number of inequivalent leaf colorings of series-reduced planted trees with n leaves using at most 2 colors.

Views

Author

Keywords

Comments

Examples