A316475 -id:A316475 - cp's OEIS frontend

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

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

A317787 Number of locally nonintersecting rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 4, 8, 18, 40, 95, 227, 557, 1382, 3485, 8865, 22790, 59022, 153972, 404066, 1066236, 2826885, 7527411, 20121154

Offset: 1

Gus Wiseman, Aug 07 2018

An unlabeled rooted tree is locally nonintersecting if there is no common subbranch to all branches directly under any given node.

			The a(6) = 18 locally nonintersecting rooted trees:
  (((((o)))))
  ((((oo))))
  (((o(o))))
  ((o((o))))
  (o(((o))))
  ((o)((o)))
  (((ooo)))
  ((o(oo)))
  ((oo(o)))
  (o((oo)))
  (o(o(o)))
  (oo((o)))
  (o(o)(o))
  ((oooo))
  (o(ooo))
  (oo(oo))
  (ooo(o))
  (ooooo)
Missing from this list are (((o)(o))) and ((o)(oo)).

Cf. A000081, A276625, A301700, A316473, A316475, A316501, A316502, A317708, A317785, A317789.

rurt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[rurt/@ptn]],Or[Length[#]==1,Intersection@@#=={}]&],{ptn,IntegerPartitions[n-1]}]];
Table[Length[rurt[n]],{n,10}]

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

A316501 Number of unlabeled rooted trees with n nodes in which the branches of any node with more than one distinct branch have empty intersection.

Original entry on oeis.org

1, 1, 2, 4, 9, 19, 45, 103, 250, 611, 1528, 3853, 9875, 25481, 66382, 174085, 459541, 1219462

Offset: 1

Gus Wiseman, Jul 05 2018

			The a(6) = 19 rooted trees:
  (((((o)))))
  ((((oo))))
  (((o(o))))
  (((ooo)))
  ((o((o))))
  ((o(oo)))
  (((o)(o)))
  ((oo(o)))
  ((oooo))
  (o(((o))))
  (o((oo)))
  (o(o(o)))
  (o(ooo))
  ((o)((o)))
  (oo((o)))
  (oo(oo))
  (o(o)(o))
  (ooo(o))
  (ooooo)

Cf. A000081, A007562, A289509, A302796, A316470, A316473, A316475, A316500, A316502.

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

A317616 Numbers whose prime multiplicities are not pairwise indivisible.

Original entry on oeis.org

12, 18, 20, 24, 28, 40, 44, 45, 48, 50, 52, 54, 56, 60, 63, 68, 75, 76, 80, 84, 88, 90, 92, 96, 98, 99, 104, 112, 116, 117, 120, 124, 126, 132, 135, 136, 140, 144, 147, 148, 150, 152, 153, 156, 160, 162, 164, 168, 171, 172, 175, 176, 180, 184, 188, 189, 192

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

The numbers of terms that do not exceed 10^k, for k = 2, 3, ..., are 26, 344, 3762, 38711, 390527, 3915874, 39192197, 392025578, 3920580540, ... . Apparently, the asymptotic density of this sequence exists and equals 0.392... . - Amiram Eldar, Sep 25 2024

			72 = 2^3 * 3^2 is not in the sequence because 3 and 2 are pairwise indivisible.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A118914, A124010, A285572, A285573, A303362, A304713, A316475, A317101, A317102.

Select[Range[100],!Select[Tuples[Last/@FactorInteger[#],2],And[UnsameQ@@#,Divisible@@#]&]=={}&]

is(k) = if(k == 1, 0, my(e = Set(factor(k)[,2])); if(vecmax(e) == 1, 0, for(i = 1, #e, for(j = 1, i-1, if(!(e[i] % e[j]), return(1)))); 0)); \\ Amiram Eldar, Sep 25 2024

A317785 Number of locally connected rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 4, 7, 8, 12, 14, 21, 24, 34, 42, 55, 67, 91, 109, 144, 177, 228, 281, 366, 448, 579, 720, 916, 1142

Offset: 1

Gus Wiseman, Aug 06 2018

An unlabeled rooted tree is locally connected if the branches directly under any given node are connected as a hypergraph.

			The a(11) = 12 locally connected rooted trees:
  ((((((((((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)(o))

Gus Wiseman, All 42 locally connected rooted trees with 16 nodes.

Cf. A000081, A276625, A286518, A286520, A301700, A304714, A316473, A316475, A317077, A317078, A317708, A317787.

multijoin[mss__]:=Join@@Table[Table[x, {Max[Count[#, x]&/@{mss}]}], {x, Union[mss]}];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],multijoin@@s[[c[[1]]]]]]]]];
rurt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[rurt/@ptn]],Or[Length[#]==1,Length[csm[#]]==1]&],{ptn,IntegerPartitions[n-1]}]];
Table[Length[rurt[n]],{n,10}]

A317101 Numbers whose prime multiplicities are pairwise indivisible.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 46, 47, 49, 51, 53, 55, 57, 58, 59, 61, 62, 64, 65, 66, 67, 69, 70, 71, 72, 73, 74, 77, 78, 79, 81, 82, 83, 85, 86, 87

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

			72 = 2^3 * 3^2 is in the sequence because 3 and 2 are pairwise indivisible.

Cf. A118914, A124010, A285572, A285573, A303362, A304713, A316475, A317102, A317616.

Select[Range[100],Select[Tuples[Last/@FactorInteger[#],2],And[UnsameQ@@#,Divisible@@#]&]=={}&]

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

A316768 Number of series-reduced locally stable rooted trees whose leaves form an integer partition of n.

Original entry on oeis.org

1, 2, 4, 11, 29, 91, 284, 950, 3235, 11336, 40370, 146095, 534774, 1977891, 7377235, 27719883

Offset: 1

Gus Wiseman, Jul 12 2018

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally stable if no branch is a submultiset of any other branch of the same root.

			The a(5) = 29 trees:
  5,
  (14),
  (23),
  (1(13)), (3(11)), (113),
  (1(22)), (2(12)), (122),
  (1(1(12))), (1(2(11))), (1(112)), (2(1(11))), (2(111)), ((11)(12)), (11(12)), (12(11)), (1112),
  (1(1(1(11)))), (1(1(111))), (1((11)(11))), (1(11(11))), (1(1111)), ((11)(1(11))), (11(1(11))), (11(111)), (1(11)(11)), (111(11)), (11111).
Missing from this list but counted by A141268 is ((11)(111)).

Cf. A000081, A000669, A001678, A141268, A292504, A316468, A316475, A316651, A316652, A316655.

submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{_,x_,W___}}/;submultisetQ[{Z},{W}]]];
stableQ[u_]:=Apply[And,Outer[#1==#2||!submultisetQ[#1,#2]&&!submultisetQ[#2,#1]&,u,u,1],{0,1}];
nms[n_]:=nms[n]=Prepend[Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],stableQ],{ptn,Rest[IntegerPartitions[n]]}],{n}];
Table[Length[nms[n]],{n,10}]

a(15)-a(16) from Robert Price, Sep 16 2018

A319286 Number of series-reduced locally disjoint rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.

Original entry on oeis.org

1, 2, 9, 67, 573, 6933, 97147, 1666999

Offset: 1

Gus Wiseman, Sep 16 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 branch of the same root.

			The a(3) = 9 trees:
  (1(11))
   (111)
  (1(12))
  (2(11))
   (112)
  (1(23))
  (2(13))
  (3(12))
   (123)
Examples of rooted trees that are not locally disjoint are ((11)(12)) and ((12)(13)).

Cf. A000081, A007562, A316473, A316475, A316494, A316495, A316496, A316497.

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
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]]]];
gro[m_]:=gro[m]=If[Length[m]==1,{m},Select[Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])],disjointQ]];
Table[Sum[Length[gro[m]],{m,Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n]}],{n,5}]

A316767 Number of series-reduced locally stable rooted trees whose leaves form the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 5, 1, 3, 1, 3, 1, 1, 1, 8, 1, 1, 2, 3, 1, 4, 1, 10, 1, 1, 1, 12, 1, 1, 1, 8, 1, 4, 1, 3, 3, 1, 1, 24, 1, 3, 1, 3, 1, 8, 1, 8, 1, 1, 1, 17, 1, 1, 3, 24, 1, 4, 1, 3, 1, 4, 1, 39, 1, 1, 3, 3, 1, 4, 1, 24, 5, 1, 1, 17

Offset: 1

Gus Wiseman, Jul 12 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally stable if no branch is a submultiset of any other branch of the same root.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The a(24) = 8 trees:
  (1(1(12)))
  (1(2(11)))
  (2(1(11)))
  (1(112))
  (2(111))
  (11(12))
  (12(11))
  (1112)

Cf. A000081, A000669, A001678, A056239, A141268, A292504, A296150, A316475, A316651, A316652, A316655.

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]]]];
stableQ[u_]:=Apply[And,Outer[#1==#2||Complement[#2,#1]=!={}&,u,u,1],{0,1}];
gro[m_]:=gro[m]=If[Length[m]==1,List/@m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
Table[Length[Select[gro[If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]],And@@Cases[#,q:{__List}:>stableQ[q],{0,Infinity}]&]],{n,100}]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A317787 Number of locally nonintersecting rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A316501 Number of unlabeled rooted trees with n nodes in which the branches of any node with more than one distinct branch have empty intersection.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A317616 Numbers whose prime multiplicities are not pairwise indivisible.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A317785 Number of locally connected rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A317101 Numbers whose prime multiplicities are pairwise indivisible.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A316768 Number of series-reduced locally stable rooted trees whose leaves form an integer partition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A319286 Number of series-reduced locally disjoint rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.

Views

Author

Keywords