A316495 -id:A316495 - cp's OEIS frontend

A331874 Number of semi-lone-child-avoiding locally disjoint rooted trees with n unlabeled leaves.

2, 3, 8, 24, 67, 214, 687, 2406, 8672, 32641, 125431, 493039, 1964611

Offset: 1

Gus Wiseman, Feb 02 2020

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

Locally disjoint means no child of any vertex has branches overlapping the branches of any other (inequivalent) child of the same vertex.

			The a(1) = 2 through a(4) = 24 trees:
  o    (oo)      (ooo)          (oooo)
  (o)  (o(o))    (o(oo))        (o(ooo))
       ((o)(o))  (oo(o))        (oo(oo))
                 (o(o)(o))      (ooo(o))
                 (o(o(o)))      ((oo)(oo))
                 ((o)(o)(o))    (o(o(oo)))
                 (o((o)(o)))    (o(oo(o)))
                 ((o)((o)(o)))  (oo(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)))
                                ((oo)((o)(o)))
                                (o((o)(o)(o)))
                                (o(o)((o)(o)))
                                (o(o((o)(o))))
                                ((o)((o)(o)(o)))
                                ((o)(o)((o)(o)))
                                (o((o)((o)(o))))
                                (((o)(o))((o)(o)))
                                ((o)((o)((o)(o))))

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 A050381.
The non-semi version is A316697.
The same trees counted by number of vertices are A331872.
The Matula-Goebel numbers of these trees are A331873.
Lone-child-avoiding rooted trees counted  by leaves are A000669.
Semi-lone-child-avoiding rooted trees counted by vertices are A331934.
Cf. A000081, A001678, A300660, A316473, A316495, A316696, A331678, A331679, A331680, A331682, A331687, A331871, A331935.

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
slaurt[n_]:=If[n==1,{o,{o}},Join@@Table[Select[Union[Sort/@Tuples[slaurt/@ptn]],disjointQ[Select[#,!AtomQ[#]&]]&],{ptn,Rest[IntegerPartitions[n]]}]];
Table[Length[slaurt[n]],{n,8}]

A316494 Matula-Goebel numbers of locally disjoint rooted identity trees, meaning no branch overlaps any other branch of the same root.

Original entry on oeis.org

1, 2, 3, 5, 6, 10, 11, 13, 15, 22, 26, 29, 30, 31, 33, 41, 47, 55, 58, 62, 66, 79, 82, 93, 94, 101, 109, 110, 113, 123, 127, 137, 141, 143, 145, 155, 158, 165, 179, 186, 202, 205, 211, 218, 226, 246, 254, 257, 271, 274, 282, 286, 290, 293, 310, 317, 327, 330

Offset: 1

Gus Wiseman, Jul 04 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A number is in the sequence iff either it is equal to 1, it is a prime number whose prime index already belongs to the sequence, or its prime indices are pairwise coprime, distinct, and already belong to the sequence.

			The sequence of all locally disjoint rooted identity trees preceded by their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   5: (((o)))
   6: (o(o))
  10: (o((o)))
  11: ((((o))))
  13: ((o(o)))
  15: ((o)((o)))
  22: (o(((o))))
  26: (o(o(o)))
  29: ((o((o))))
  30: (o(o)((o)))
  31: (((((o)))))

Cf. A000081, A004111, A007097, A276625, A277098, A302696, A303362, A304713, A316467, A316471, A316474, A316495.

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

A331678 Number of lone-child-avoiding locally disjoint rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.

Original entry on oeis.org

1, 3, 6, 18, 44, 149, 450, 1573, 5352, 19283, 69483, 257206

Offset: 1

Gus Wiseman, Jan 25 2020

Lone-child-avoiding means there are no unary branchings. Locally disjoint means no child of any vertex has branches overlapping the branches of any other unequal child of the same vertex.

			The a(1) = 1 through a(4) = 18 trees:
  (1)  (2)       (3)            (4)
       (11)      (12)           (13)
       ((1)(1))  (111)          (22)
                 ((1)(2))       (112)
                 ((1)(1)(1))    (1111)
                 ((1)((1)(1)))  ((1)(3))
                                ((2)(2))
                                ((2)(11))
                                ((11)(11))
                                ((1)(1)(2))
                                ((1)((1)(2)))
                                ((2)((1)(1)))
                                ((1)(1)(1)(1))
                                ((11)((1)(1)))
                                ((1)((1)(1)(1)))
                                ((1)(1)((1)(1)))
                                (((1)(1))((1)(1)))
                                ((1)((1)((1)(1))))

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.

The case where all leaves are singletons is A316696.
The case where all leaves are (1) is A316697.
The non-locally disjoint version is A319312.
The case with all atoms equal to 1 is A331679.
The identity tree case is A331686.
Cf. A000081, A000669, A001678, A005804, A060356, A141268, A196545, A300660, A316471, A316694, A316495, A330465, A331680, A331687.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
mpti[m_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[mpti/@p]],disjointQ],{p,Select[mps[m],Length[#]>1&]}],m];
Table[Sum[Length[mpti[m]],{m,Sort/@IntegerPartitions[n]}],{n,8}]

A331687 Number of locally disjoint enriched p-trees of weight n.

Original entry on oeis.org

1, 2, 4, 12, 29, 93, 249, 803, 2337, 7480, 23130, 77372, 247598, 834507, 2762222

Offset: 1

Gus Wiseman, Jan 31 2020

A locally disjoint enriched p-tree of weight n is either the number n itself or a finite sequence of non-overlapping locally disjoint enriched p-trees whose weights are weakly decreasing and sum to n.

			The a(1) = 1 through a(4) = 12 enriched p-trees:
  1  2     3        4
     (11)  (21)     (22)
           (111)    (31)
           ((11)1)  (211)
                    (1111)
                    ((11)2)
                    ((21)1)
                    (2(11))
                    ((11)11)
                    ((111)1)
                    (((11)1)1)
                    ((11)(11))

The orderless version is A316696.
The identity case is A331684.
P-trees are A196545.
Enriched p-trees are A289501.
Locally disjoint identity trees are A316471.
Enriched identity p-trees are A331875.
Cf. A000669, A141268, A316473, A316495, A316694, A316697, A319312, A331678, A331679, A331680, A331686, A331871, A331874.

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
ldep[n_]:=Prepend[Select[Join@@Table[Tuples[ldep/@p],{p,Rest[IntegerPartitions[n]]}],disjointQ[DeleteCases[#,_Integer]]&],n];
Table[Length[ldep[n]],{n,10}]

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.

A316502 Matula-Goebel numbers of unlabeled rooted trees with n nodes in which the branches of any node with more than one branch have empty intersection.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 45, 47, 48, 50, 51, 52, 53, 54, 55, 56, 58, 59, 60, 61, 62, 64, 66, 67, 68, 70, 71, 72, 74, 75, 76, 77, 78, 79, 80

Offset: 1

Gus Wiseman, Jul 05 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A number is in the sequence iff it is 1, or either it is a prime or its prime indices are relatively prime, and its prime indices already belong to the sequence.

			Sequence of rooted trees preceded by 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)

Index entries for sequences related to Matula-Göbel numbers

Cf. A000081, A000837, A007097, A276625, A289509, A302796, A316468, A316470, A316495, A316501, A316502.

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

A331783 Number of locally disjoint rooted semi-identity trees with n unlabeled vertices.

Original entry on oeis.org

1, 1, 2, 4, 8, 17, 37, 83, 191, 450, 1076, 2610, 6404, 15875, 39676, 99880, 253016, 644524, 1649918, 4242226

Offset: 1

Gus Wiseman, Jan 31 2020

Locally disjoint means no branch of any vertex overlaps a different (unequal) branch of the same vertex. In a semi-identity tree, all non-leaf branches of any given vertex are distinct.

			The a(1) = 1 through a(6) = 17 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))))  ((oo(o)))
                                     (o((oo)))
                                     (o(o(o)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o(o))))
                                     ((o)((o)))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))

The lone-child-avoiding case is A212804.
The identity tree version is A316471.
The Matula-Goebel numbers of these trees are given by A331682.
Identity trees are A004111.
Semi-identity trees are A306200.
Locally disjoint rooted trees are A316473.
Matula-Goebel numbers of locally disjoint semi-identity trees are A316494.
Cf. A000081, A306202, A316475, A316495, A316694, A331683, A331684, A331686.

disjunsQ[u_]:=Length[u]==1||UnsameQ@@DeleteCases[u,{}]&&Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
ldrsi[n_]:=If[n==1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[ldrsi/@c]]]/@IntegerPartitions[n-1],disjunsQ]];
Table[Length[ldrsi[n]],{n,10}]

A331682 One and all numbers whose prime indices are pairwise coprime and already belong to the sequence, where a singleton is always considered to be coprime.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 37, 38, 40, 41, 43, 44, 47, 48, 51, 52, 53, 55, 56, 58, 59, 60, 62, 64, 66, 67, 68, 70, 71, 74, 76, 77, 79, 80, 82, 85, 86, 88, 89, 93, 94, 95, 96, 101

Offset: 1

Gus Wiseman, Jan 27 2020

nonn

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.

Also Matula-Goebel numbers of locally disjoint rooted semi-identity trees. Locally disjoint means no branch of any vertex overlaps a different (unequal) branch of the same vertex. 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 a rooted tree is the product of primes indexed by the Matula-Goebel numbers of its branches (of the root), which gives a bijective correspondence between positive integers and unlabeled rooted trees.

			The sequence of all locally disjoint 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)))
  22: (o(((o))))
  24: (ooo(o))

The non-semi identity tree case is A316494.
The enumeration of these trees by vertices is A331783.
Semi-identity trees are counted by A306200.
Matula-Goebel numbers of semi-identity trees are A306202.
Locally disjoint rooted trees are counted by A316473.
Matula-Goebel numbers of locally disjoint rooted trees are A316495.
Cf. A000081, A007097, A061775, A196050, A276625, A316470, A331681, A331683.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
deQ[n_]:=n==1||PrimeQ[n]&&deQ[PrimePi[n]]||CoprimeQ@@primeMS[n]&&And@@deQ/@primeMS[n];
Select[Range[100],deQ]

A331937 a(1) = 1; a(2) = 2; a(n + 1) = 2 * prime(a(n)).

Original entry on oeis.org

1, 2, 6, 26, 202, 2462, 43954, 1063462, 33076174, 1270908802, 58596709306, 3170266564862, 197764800466826, 14024066291995502, 1117378164606478094

Offset: 1

Gus Wiseman, Feb 07 2020

Also Matula-Goebel numbers of semi-lone-child-avoiding locally disjoint rooted identity trees. 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. It is semi-lone-child-avoiding if there are no vertices with exactly one child unless that child is an endpoint/leaf. In an identity tree, the branches of any given vertex are all distinct. 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.

			The sequence of terms together with their associated trees begins:
     1: o
     2: (o)
     6: (o(o))
    26: (o(o(o)))
   202: (o(o(o(o))))
  2462: (o(o(o(o(o)))))

The semi-identity tree version is A331681.
Not requiring an identity tree gives A331873.
Not requiring local disjointness gives A331963.
Not requiring lone-child-avoidance gives A316494.
MG-numbers of semi-lone-child-avoiding rooted trees are A331935.
Cf. A007097, A061775, A276625, A316471, A316495, A316694, A331679, A331683, A331686, A331872, A331934, A331936, A331964, A331965.

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

Intersection of A276625 (identity), A316495 (locally disjoint), and A331935 (semi-lone-child-avoiding).

a(14)-a(15) from Giovanni Resta, Feb 10 2020

A319271 Number of series-reduced locally non-intersecting aperiodic rooted trees with n nodes.

Original entry on oeis.org

1, 1, 0, 1, 1, 3, 3, 9, 12, 27, 42, 91, 151, 312, 550, 1099, 2026, 3999, 7527, 14804, 28336, 55641, 107737, 211851, 413508, 814971, 1600512, 3162761, 6241234

Offset: 1

Gus Wiseman, Sep 16 2018

A rooted tree is series-reduced if every non-leaf node has at least two branches, and aperiodic if the multiplicities in the multiset of branches directly under any given node are relatively prime, and locally non-intersecting if the branches directly under any given node with more than one branch have empty intersection.

			The a(8) = 9 rooted trees:
  (o(o(o(o))))
  (o(o(o)(o)))
  (o(ooo(o)))
  (oo(oo(o)))
  (o(o)(o(o)))
  (ooo(o(o)))
  (o(o)(o)(o))
  (ooo(o)(o))
  (ooooo(o))

Cf. A000081, A000837, A007562, A289509, A301700, A303431, A316470, A316473, A316475, A316495, A319270.

btrut[n_]:=btrut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[btrut/@c]]]/@IntegerPartitions[n-1],And[Intersection@@#=={},GCD@@Length/@Split[#]==1]&]];
Table[Length[btrut[n]],{n,30}]

cp's OEIS Frontend

A331874 Number of semi-lone-child-avoiding locally disjoint rooted trees with n unlabeled leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A316494 Matula-Goebel numbers of locally disjoint rooted identity trees, meaning no branch overlaps any other branch of the same root.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A331678 Number of lone-child-avoiding locally disjoint rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A331687 Number of locally disjoint enriched p-trees of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A316502 Matula-Goebel numbers of unlabeled rooted trees with n nodes in which the branches of any node with more than one branch have empty intersection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A331783 Number of locally disjoint rooted semi-identity trees with n unlabeled vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A331682 One and all numbers whose prime indices are pairwise coprime and already belong to the sequence, where a singleton is always considered to be coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A331937 a(1) = 1; a(2) = 2; a(n + 1) = 2 * prime(a(n)).

Views