A331783 -id:A331783 - cp's OEIS frontend

A316694 Number of lone-child-avoiding locally disjoint rooted identity trees whose leaves form an integer partition of n.

1, 1, 2, 3, 6, 13, 28, 62, 143, 338, 804, 1948, 4789, 11886, 29796, 75316, 191702, 491040, 1264926, 3274594, 8514784, 22229481, 58243870

Offset: 1

Gus Wiseman, Jul 10 2018

A rooted tree is lone-child-avoiding if every non-leaf node has at least two branches. It is locally disjoint if no branch overlaps any other (unequal) branch of the same root. It is an identity tree if no branch appears multiple times under the same root.

			The a(7) = 28 rooted trees:
  7,
  (16),
  (25),
  (1(15)),
  (34),
  (1(24)), (2(14)), (4(12)), (124),
  (1(1(14))),
  (3(13)),
  (2(23)),
  (1(1(23))), (1(2(13))), (1(3(12))), (1(123)), (2(1(13))), (3(1(12))), (12(13)), (13(12)),
  (1(1(1(13)))),
  (2(2(12))),
  (1(1(2(12)))), (1(2(1(12)))), (1(12(12))), (2(1(1(12)))), (12(1(12))),
  (1(1(1(1(12))))).
Missing from this list but counted by A300660 are ((12)(13)) and ((12)(1(12))).

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Cf. A000081, A000669, A001678, A141268, A292504, A316653, A316654, A316656.
The semi-identity tree version is A212804.
Not requiring local disjointness gives A300660.
The non-identity tree version is A316696.
This is the case of A331686 where all leaves are singletons.
Rooted identity trees are A004111.
Locally disjoint rooted identity trees are A316471.
Lone-child-avoiding locally disjoint rooted trees are A331680.
Locally disjoint enriched identity p-trees are A331684.
Cf. A306200, A316697, A331678, A331679, A331681, A331683, A331783, A331874.

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
nms[n_]:=nms[n]=Prepend[Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],And[UnsameQ@@#,disjointQ[#]]&],{ptn,Rest[IntegerPartitions[n]]}],{n}];
Table[Length[nms[n]],{n,10}]

a(21)-a(23) from Robert Price, Sep 16 2018

Updated with corrected terminology by Gus Wiseman, Feb 06 2020

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

Original entry on oeis.org

1, 2, 4, 8, 17, 41, 103, 280, 793, 2330, 6979, 21291

Offset: 1

Gus Wiseman, Jan 31 2020

A rooted tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other (unequal) child of the same vertex. Lone-child-avoiding means there are no unary branchings. In an identity tree, all branches of any given vertex are distinct.

			The a(1) = 1 through a(5) = 17 trees:
  (1)  (2)   (3)       (4)            (5)
       (11)  (12)      (13)           (14)
             (111)     (22)           (23)
             ((1)(2))  (112)          (113)
                       (1111)         (122)
                       ((1)(3))       (1112)
                       ((2)(11))      (11111)
                       ((1)((1)(2)))  ((1)(4))
                                      ((2)(3))
                                      ((1)(22))
                                      ((3)(11))
                                      ((2)(111))
                                      ((1)((1)(3)))
                                      ((2)((1)(2)))
                                      ((11)((1)(2)))
                                      ((1)((2)(11)))
                                      ((1)((1)((1)(2))))

The non-identity version is A331678.
The case where the leaves are all singletons is A316694.
Identity trees are A004111.
Locally disjoint identity trees are A316471.
Locally disjoint enriched identity p-trees are A331684.
Lone-child-avoiding locally disjoint rooted semi-identity trees are A212804.
Cf. A000669, A001678, A005804, A141268, A300660, A316697, A319312, A331679, A331683, A331783, A331874, A331875.

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]],UnsameQ@@#&&disjointQ[#]&],{p,Select[mps[m],Length[#]>1&]}],m];
Table[Sum[Length[mpti[m]],{m,Sort/@IntegerPartitions[n]}],{n,8}]

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

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 5, 9, 16, 30, 55, 105, 200, 388, 754, 1483, 2923, 5807, 11575, 23190, 46608, 94043, 190287, 386214, 785831, 1602952, 3276845, 6712905, 13778079, 28330583, 58350582, 120370731, 248676129, 514459237, 1065696295, 2210302177, 4589599429, 9540623926

Offset: 1

Gus Wiseman, Feb 05 2020

nonn

Lone-child-avoiding means there are no unary branchings.

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

			The a(1) = 1 through a(9) = 16 trees (empty column shown as dot):
  o  .  (oo)  (ooo)  (oooo)   (ooooo)   (oooooo)    (ooooooo)    (oooooooo)
                     (o(oo))  (o(ooo))  (o(oooo))   (o(ooooo))   (o(oooooo))
                              (oo(oo))  (oo(ooo))   (oo(oooo))   (oo(ooooo))
                                        (ooo(oo))   (ooo(ooo))   (ooo(oooo))
                                        (o(o(oo)))  (oooo(oo))   (oooo(ooo))
                                                    ((oo)(ooo))  (ooooo(oo))
                                                    (o(o(ooo)))  ((oo)(oooo))
                                                    (o(oo(oo)))  (o(o(oooo)))
                                                    (oo(o(oo)))  (o(oo)(ooo))
                                                                 (o(oo(ooo)))
                                                                 (o(ooo(oo)))
                                                                 (oo(o(ooo)))
                                                                 (oo(oo(oo)))
                                                                 (ooo(o(oo)))
                                                                 ((oo)(o(oo)))
                                                                 (o(o(o(oo))))

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

The non-semi case is A000007.
Lone-child-avoiding rooted trees are A001678.
The locally disjoint case is A212804.
Not requiring lone-child-avoidance gives A306200.
Matula-Goebel numbers of these trees are A331965.
The semi-lone-child-avoiding version is A331993.
Cf. A000081, A004111, A291636, A300660, A306202, A316694, A331683, A331686, A331783, A331875, A331964, A331994.

ssb[n_]:=If[n==1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[ssb/@c]],UnsameQ@@DeleteCases[#,{}]&]]/@Rest[IntegerPartitions[n-1]]];
Table[Length[ssb[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, 0]); for(n=2, n-1, v=concat(v, 1 + vecsum(WeighT(v)) - v[n])); v[1]=1; v} \\ Andrew Howroyd, Feb 09 2020

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

A331681 One, two, and all numbers of the form 2^k * prime(j) where k > 0 and j already belongs to the sequence.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 14, 16, 24, 26, 28, 32, 38, 48, 52, 56, 64, 74, 76, 86, 96, 104, 106, 112, 128, 148, 152, 172, 178, 192, 202, 208, 212, 214, 224, 256, 262, 296, 304, 326, 344, 356, 384, 404, 416, 424, 428, 446, 448, 478, 512, 524, 526, 592, 608, 622, 652

Offset: 1

Gus Wiseman, Jan 26 2020

nonn

Also Matula-Goebel numbers of semi-lone-child-avoiding locally disjoint rooted semi-identity trees. 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 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. Note that these conditions together imply that there is at most one non-leaf branch under any given vertex.
Also Matula-Goebel numbers of semi-lone-child-avoiding rooted trees with at most one non-leaf branch under any given vertex.
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 semi-lone-child-avoiding rooted trees with at most one non-leaf branch under any given vertex, together with their Matula-Goebel numbers, begins:
   1: o
   2: (o)
   4: (oo)
   6: (o(o))
   8: (ooo)
  12: (oo(o))
  14: (o(oo))
  16: (oooo)
  24: (ooo(o))
  26: (o(o(o)))
  28: (oo(oo))
  32: (ooooo)
  38: (o(ooo))
  48: (oooo(o))
  52: (oo(o(o)))
  56: (ooo(oo))
  64: (oooooo)
  74: (o(oo(o)))
  76: (oo(ooo))
  86: (o(o(oo)))

Robert Israel, Table of n, a(n) for n = 1..4000

The enumeration of these trees by nodes is A324969 (essentially A000045).
The enumeration of these trees by leaves appears to be A090129(n + 1).
The (non-semi) lone-child-avoiding version is A331683.
Matula-Goebel numbers of rooted semi-identity trees are A306202.
Lone-child-avoiding locally disjoint rooted trees by leaves are A316697.
The set S of numbers with at most one prime index in S is A331784.
Matula-Goebel numbers of locally disjoint rooted trees are A316495.
Cf. A000081, A000669, A001678, A007097, A061775, A196050, A291636, A316470, A316473, A331679, A331680, A331682, A331687, A331783, A331785, A331873.

N:= 1000: # for terms <= N
S:= {1,2}:
with(queue):
Q:= new(1,2):
while not empty(Q) do
  r:= dequeue(Q);
  p:= ithprime(r);
  newS:= {seq(2^i*p,i=1..ilog2(N/p))} minus S;
  S:= S union newS;
  for s in newS do enqueue(Q,s) od:
od:
sort(convert(S,list)); # Robert Israel, Feb 05 2020

uryQ[n_]:=n==1||MatchQ[FactorInteger[n],({{2,},{p,1}}/;uryQ[PrimePi[p]])|{{2,_}}];
Select[Range[100],uryQ]

Intersection of A306202 (semi-identity), A316495 (locally disjoint), and A331935 (semi-lone-child-avoiding). - Gus Wiseman, Jun 09 2020

A331875 Number of enriched identity p-trees of weight n.

Original entry on oeis.org

1, 1, 2, 3, 6, 14, 32, 79, 198, 522, 1368, 3716, 9992, 27612, 75692, 212045, 589478, 1668630, 4690792, 13387332, 37980664, 109098556, 311717768, 900846484, 2589449032, 7515759012, 21720369476, 63305262126, 183726039404, 537364221200, 1565570459800, 4592892152163

Offset: 1

Gus Wiseman, Jan 31 2020

nonn

An enriched identity p-tree of weight n is either the number n itself or a finite sequence of distinct enriched identity p-trees whose weights are weakly decreasing and sum to n.

			The a(1) = 1 through a(6) = 14 enriched p-trees:
  1  2  3     4        5           6
        (21)  (31)     (32)        (42)
              ((21)1)  (41)        (51)
                       ((21)2)     (321)
                       ((31)1)     ((21)3)
                       (((21)1)1)  ((31)2)
                                   ((32)1)
                                   (3(21))
                                   ((41)1)
                                   ((21)21)
                                   (((21)1)2)
                                   (((21)2)1)
                                   (((31)1)1)
                                   ((((21)1)1)1)

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

The orderless version is A300660.
The locally disjoint case is A331684.
Identity trees are A004111.
P-trees are A196545.
Enriched p-trees are A289501.
Cf. A000669, A141268, A306200, A316471, A331683, A331685, A331686, A331783.

eptrid[n_]:=Prepend[Select[Join@@Table[Tuples[eptrid/@p],{p,Rest[IntegerPartitions[n]]}],UnsameQ@@#&],n];
Table[Length[eptrid[n]],{n,10}]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(prod(k=1, n-1, sum(j=0, n\k, j!*binomial(v[k],j)*x^(k*j)) + O(x*x^n)), n)); v} \\ Andrew Howroyd, Feb 09 2020

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

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]

A331684 Number of locally disjoint enriched identity p-trees of weight n.

Original entry on oeis.org

1, 1, 2, 3, 6, 14, 30, 68, 157, 379, 901, 2229, 5488, 13846, 34801, 89368, 228186, 592943, 1533511, 4026833

Offset: 1

Gus Wiseman, Jan 31 2020

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

			The a(1) = 1 through a(6) = 14 enriched p-trees:
  1  2  3     4        5           6
        (21)  (31)     (32)        (42)
              ((21)1)  (41)        (51)
                       ((21)2)     (321)
                       ((31)1)     ((21)3)
                       (((21)1)1)  ((31)2)
                                   ((32)1)
                                   (3(21))
                                   ((41)1)
                                   ((21)21)
                                   (((21)1)2)
                                   (((21)2)1)
                                   (((31)1)1)
                                   ((((21)1)1)1)

The orderless version is A316694.
The non-identity version is A331687.
Identity trees are A004111.
P-trees are A196545.
Enriched p-trees are A289501.
Locally disjoint identity trees are A316471.
Enriched identity p-trees are A331875, with locally disjoint case A331687.
Cf. A000669, A005804, A141268, A300660, A316696, A316697, A331678, A331679, A331680, A331683, A331686, A331783, A331874.

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

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

cp's OEIS Frontend

A316694 Number of lone-child-avoiding locally disjoint rooted identity trees whose leaves form an integer partition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A331681 One, two, and all numbers of the form 2^k * prime(j) where k > 0 and j already belongs to the sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A331875 Number of enriched identity p-trees of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

A331684 Number of locally disjoint enriched identity p-trees of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments