A316471 -id:A316471 - cp's OEIS frontend

A316473 Number of locally disjoint rooted trees with n nodes, meaning no branch overlaps any other (unequal) branch of the same root.

1, 1, 2, 4, 9, 19, 44, 99, 233, 554, 1346, 3300, 8219, 20635, 52300, 133488, 343033, 886360, 2302133, 6005835

Offset: 1

Gus Wiseman, Jul 04 2018

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

Gus Wiseman, The a(6) = 19 locally disjoint rooted trees.

Cf. A000081, A285573, A302696, A304713, A316468, A316470, A316471, A316475, A316495.

strut[n_]:=strut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1],Select[Tuples[#,2],UnsameQ@@#&&(Intersection@@#=!={})&]=={}&]];
Table[Length[strut[n]],{n,15}]

a(20) from Jinyuan Wang, Jun 20 2020

A306200 Number of unlabeled rooted semi-identity trees with n nodes.

Original entry on oeis.org

0, 1, 1, 2, 4, 8, 18, 41, 98, 237, 591, 1488, 3805, 9820, 25593, 67184, 177604, 472177, 1261998, 3388434, 9136019, 24724904, 67141940, 182892368, 499608724, 1368340326, 3756651116, 10336434585, 28499309291, 78727891420, 217870037932, 603934911859, 1676720329410

Offset: 0

Gus Wiseman, Jan 29 2019

nonn

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(7) = 8 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))))  ((o(oo)))
                                     ((oo(o)))
                                     (o((oo)))
                                     (o(o(o)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o(o))))
                                     ((o)((o)))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))

Alois P. Heinz, Table of n, a(n) for n = 0..2166

Cf. A000081, A004111, A276625, A301700, A306201, A316471, A316474, A317708, A317712, A317718.

b:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
      add(b(n-i*j, i-1)*binomial(a(i), j), j=0..n/i))
    end:
a:= n-> `if`(n=0, 0, b(n-1$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Jan 29 2019

ursit[n_]:=Join@@Table[Select[Union[Sort/@Tuples[ursit/@ptn]],UnsameQ@@DeleteCases[#,{}]&],{ptn,IntegerPartitions[n-1]}];
Table[Length[ursit[n]],{n,10}]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0 || i == 1, 1,
     Sum[b[n - i*j, i - 1]*Binomial[a[i], j], {j, 0, n/i}]];
a[n_] := If[n == 0, 0, b[n - 1, n - 1]];
a /@ Range[0, 35] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

More terms from Alois P. Heinz, Jan 29 2019

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

Original entry on oeis.org

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

A316697 Number of series-reduced locally disjoint rooted trees with n unlabeled leaves.

Original entry on oeis.org

1, 1, 2, 5, 10, 24, 49, 112, 241, 548, 1218, 2839, 6547, 15572, 37179, 90555, 222065, 552576, 1384820, 3506475, 8936121, 22941280

Offset: 1

Gus Wiseman, Jul 10 2018

A rooted tree is series-reduced 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.

			The a(5) = 10 trees:
  (o(o(o(oo))))
  (o(o(ooo)))
  (o((oo)(oo)))
  (o(oo(oo)))
  (o(oooo))
  (oo(o(oo)))
  (oo(ooo))
  (o(oo)(oo))
  (ooo(oo))
  (ooooo)
Missing from this list but counted by A000669 are ((oo)(o(oo))) and ((oo)(ooo)).

Cf. A000081, A000669, A001678, A141268, A316471, A316471, A316475, A316495.

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

a(18)-a(22) from Robert Price, Sep 14 2018

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}]

A331679 Number of lone-child-avoiding locally disjoint rooted trees whose leaves are positive integers summing to n, with no two distinct leaves directly under the same vertex.

Original entry on oeis.org

1, 2, 3, 8, 16, 48, 116, 341, 928, 2753, 7996, 24254, 73325, 226471, 702122

Offset: 1

Gus Wiseman, Jan 25 2020

A tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other unequal child of the same vertex. It is lone-child-avoiding if there are no unary branchings.

			The a(1) = 1 through a(5) = 16 trees:
  1  2     3        4           5
     (11)  (111)    (22)        (11111)
           (1(11))  (1111)      ((11)3)
                    (2(11))     (1(22))
                    (1(111))    (2(111))
                    (11(11))    (1(1111))
                    ((11)(11))  (11(111))
                    (1(1(11)))  (111(11))
                                (1(2(11)))
                                (2(1(11)))
                                (1(1(111)))
                                (1(11)(11))
                                (1(11(11)))
                                (11(1(11)))
                                (1((11)(11)))
                                (1(1(1(11))))

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 non-locally disjoint version is A141268.
Locally disjoint trees counted by vertices are A316473.
The case where all leaves are 1's is A316697.
Number of trees counted by A331678 with all atoms equal to 1.
Matula-Goebel numbers of locally disjoint rooted trees are A316495.
Unlabeled lone-child-avoiding locally disjoint rooted trees are A331680.
Cf. A000081, A000669, A001678, A005804, A060356, A300660, A316471, A316694, A316696, A319312, A330465, A331681.

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
usot[n_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[usot/@ptn]],disjointQ[DeleteCases[#,_?AtomQ]]&&SameQ@@Select[#,AtomQ]&],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}],n];
Table[Length[usot[n]],{n,12}]

A331680 Number of lone-child-avoiding locally disjoint unlabeled rooted trees with n vertices.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 6, 9, 16, 26, 45, 72, 124, 201, 341, 561, 947, 1571, 2651, 4434, 7496, 12631, 21423, 36332, 61910, 105641, 180924, 310548, 534713, 923047

Offset: 1

Gus Wiseman, Jan 25 2020

First differs from A320268 at a(11) = 45, A320268(11) = 44.

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.

			The a(1) = 1 through a(9) = 16 trees (empty column indicated by 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))
                                        ((oo)(oo))  (oooo(oo))   (oooo(ooo))
                                        (o(o(oo)))  (o(o(ooo)))  (ooooo(oo))
                                                    (o(oo)(oo))  ((ooo)(ooo))
                                                    (o(oo(oo)))  (o(o(oooo)))
                                                    (oo(o(oo)))  (o(oo(ooo)))
                                                                 (o(ooo(oo)))
                                                                 (oo(o(ooo)))
                                                                 (oo(oo)(oo))
                                                                 (oo(oo(oo)))
                                                                 (ooo(o(oo)))
                                                                 (o((oo)(oo)))
                                                                 (o(o(o(oo))))

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 enriched version is A316696.
The Matula-Goebel numbers of these trees are A331871.
The non-locally disjoint version is A001678.
These trees counted by number of leaves are A316697.
The semi-lone-child-avoiding version is A331872.
Cf. A000081, A000669, A005804, A060356, A141268, A300660, A316471, A316473, A316694, A316495, A319312, A330465, A331679, A331681, A331683.

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

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

A316467 Matula-Goebel numbers of locally stable rooted identity trees, meaning no branch is a subset of any other branch of the same root.

Original entry on oeis.org

1, 2, 3, 5, 11, 15, 31, 33, 47, 55, 93, 127, 137, 141, 155, 165, 211, 257, 341, 381, 411, 465, 487, 633, 635, 709, 771, 773, 811, 907, 977, 1023, 1055, 1285, 1297, 1397, 1457, 1461, 1507, 1621, 1705, 1905, 2127, 2293, 2319, 2321, 2433, 2621, 2721, 2833, 2931

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 belongs to this sequence iff it is squarefree, its distinct prime indices are pairwise indivisible, and its prime indices also belong to this sequence.

			165 = prime(2)*prime(3)*prime(5) belongs to the sequence because it is squarefree, the indices {2,3,5} are pairwise indivisible, and each of them already belongs to the sequence.
Sequence of locally stable rooted identity trees preceded by their Matula-Goebel numbers begins:
    1: o
    2: (o)
    3: ((o))
    5: (((o)))
   11: ((((o))))
   15: ((o)((o)))
   31: (((((o)))))
   33: ((o)(((o))))
   47: (((o)((o))))
   55: (((o))(((o))))
   93: ((o)((((o)))))
  127: ((((((o))))))
  137: (((o)(((o)))))
  141: ((o)((o)((o))))
  155: (((o))((((o)))))
  165: ((o)((o))(((o))))

Cf. A000081, A004111, A007097, A276625, A277098, A285572, A285573, A302796, A303362, A304713, A316468, A316469, A316471, A316474, A316476, A316494.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
ain[n_]:=And[Select[Tuples[primeMS[n],2],UnsameQ@@#&&Divisible@@#&]=={},SquareFreeQ[n],And@@ain/@primeMS[n]];
Select[Range[100],ain]

A316474 Number of locally stable rooted identity trees with n nodes, meaning no branch is a subset of any other branch of the same root.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 5, 8, 14, 23, 42, 73, 133, 241, 442, 812, 1508, 2802, 5247, 9842, 18554, 35045, 66453, 126249

Offset: 1

Gus Wiseman, Jul 04 2018

			The a(9) = 8 locally stable rooted identity trees:
((((((((o))))))))
(((((o)((o))))))
((((o)(((o))))))
(((o)((((o))))))
((((o))(((o)))))
((o)(((((o))))))
((o)((o)((o))))
(((o))((((o)))))

Gus Wiseman, The a(10) = 14 locally stable rooted identity trees with 10 nodes.

Cf. A000081, A004111, A276625, A277098, A285572, A285573, A303362, A304713, A316467, A316471, A316471, A316475.

strut[n_]:=strut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1],UnsameQ@@#&&Select[Tuples[#,2],UnsameQ@@#&&Complement@@#=={}&]=={}&]];
Table[Length[strut[n]],{n,20}]

cp's OEIS Frontend

A316473 Number of locally disjoint rooted trees with n nodes, meaning no branch overlaps any other (unequal) branch of the same root.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A306200 Number of unlabeled rooted semi-identity trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

A316697 Number of series-reduced locally disjoint rooted trees with n unlabeled leaves.

Views

Author

Keywords

Comments

Examples

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

A331679 Number of lone-child-avoiding locally disjoint rooted trees whose leaves are positive integers summing to n, with no two distinct leaves directly under the same vertex.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A331680 Number of lone-child-avoiding locally disjoint unlabeled rooted trees with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links