A316769
Number of series-reduced locally stable rooted trees with n unlabeled leaves.
Original entry on oeis.org
1, 1, 2, 5, 11, 29, 74, 205, 578, 1683, 4978, 15000, 45672, 140600, 436421, 1364876, 4295403, 13594685, 43238514
Offset: 1
The a(5) = 11 trees:
(o(o(o(oo))))
(o(o(ooo)))
(o((oo)(oo)))
(o(oo(oo)))
(o(oooo))
((oo)(o(oo)))
(oo(o(oo)))
(oo(ooo))
(o(oo)(oo))
(ooo(oo))
(ooooo)
Missing from this list but counted by A000669 is ((oo)(ooo)).
-
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]=If[n==1,{{1}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],stableQ],{ptn,Rest[IntegerPartitions[n]]}]];
Table[Length[nms[n]],{n,12}]
A319285
Number of series-reduced locally stable 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, 69, 619, 7739, 109855, 1898230
Offset: 1
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 stable are ((11)(111)), ((11)(112)), ((12)(112)), ((12)(123)).
-
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}];
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&])],stableQ]];
Table[Sum[Length[gro[m]],{m,Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n]}],{n,5}]
A319291
Number of series-reduced locally disjoint rooted trees with n leaves spanning an initial interval of positive integers.
Original entry on oeis.org
1, 2, 12, 107, 1299, 20764, 412957, 9817743
Offset: 1
The a(3) = 12 series-reduced locally disjoint rooted trees:
(1(11))
(111)
(1(22))
(2(12))
(122)
(1(12))
(2(11))
(112)
(1(23))
(2(13))
(3(12))
(123)
The trees counted by A316651(4) but not by a(4):
((11)(12))
((12)(13))
((12)(22))
((12)(23))
((13)(23))
Cf.
A000081,
A007562,
A301700,
A316473,
A316475,
A316495,
A316651,
A316694,
A316695,
A316696,
A316697,
A319286.
-
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]];
allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Sum[Length[gro[m]],{m,allnorm[n]}],{n,5}]
A319292
Number of series-reduced locally nonintersecting rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.
Original entry on oeis.org
1, 1, 6, 48, 455, 5700, 83138, 1454870
Offset: 1
The a(3) = 6 trees are: (1(12)), (112), (1(23)), (2(13)), (3(12)), (123). Missing from this list but counted by A316651 are: (1(11)), (2(11)), (111).
-
nonintQ[u_]:=Intersection@@u=={};
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&])],nonintQ]];
Table[Sum[Length[gro[m]],{m,Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n]}],{n,5}]
Comments