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

%I #8 Sep 15 2018 01:56:36

%S 1,1,2,3,6,13,30,72,180,458,1194,3160,8459,22881,62417,171526,474405,

%T 1319395,3687711,10352696,29178988

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

%C 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. It is an identity tree if no branch appears multiple times under the same root.

%e The a(6) = 13 trees:

%e 6,

%e (15),

%e (1(14)),

%e (1(1(13))),

%e (1(1(1(12)))),

%e (1(23)), (2(13)), (3(12)), (123),

%e (1(2(12))), (2(1(12))), (12(12)),

%e (24).

%e Example of non-stable trees are ((12)(123)) and ((12)(12(12))).

%t submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{___,x_,W___}}/;submultisetQ[{Z},{W}]]];

%t stableQ[u_]:=Apply[And,Outer[#1==#2||!submultisetQ[#1,#2]&&!submultisetQ[#2,#1]&,u,u,1],{0,1}];

%t nms[n_]:=nms[n]=Prepend[Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],And[UnsameQ@@#,stableQ[#]]&],{ptn,Rest[IntegerPartitions[n]]}],{n}];

%t Table[Length[nms[n]],{n,10}]

%Y Cf. A000081, A000669, A001678, A004111, A141268, A292504, A300660, A316467, A316474, A316653, A316654, A316656.

%K nonn,more

%O 1,3

%A _Gus Wiseman_, Jul 12 2018

%E a(18)-a(21) from _Robert Price_, Sep 14 2018