A326249 - OEIS

%I #12 Oct 29 2024 19:54:10

%S 0,0,0,0,0,1,9,55,283,1324,5838,24744

%N Number of capturing set partitions of {1..n} that are not nesting.

%C Capturing is a weaker condition than nesting. A set partition is capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t, and nesting if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < t < y or z < x < y < t. For example, {{1,3,5},{2,4}} is capturing but not nesting, so is counted under a(5).

%e The a(6) = 9 set partitions:

%e   {{1},{2,4,6},{3,5}}

%e   {{1,3,5},{2,4},{6}}

%e   {{1,3,6},{2,4},{5}}

%e   {{1,3,6},{2,5},{4}}

%e   {{1,4,6},{2},{3,5}}

%e   {{1,4,6},{2,5},{3}}

%e   {{1,3,5},{2,4,6}}

%e   {{1,2,4,6},{3,5}}

%e   {{1,3,5,6},{2,4}}

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t capXQ[stn_]:=MatchQ[stn,{___,{___,x_,___,y_,___},___,{___,z_,___,t_,___},___}/;x<z<t<y||z<x<y<t];

%t nesXQ[stn_]:=MatchQ[stn,{___,{___,x_,y_,___},___,{___,z_,t_,___},___}/;x<z<t<y||z<x<y<t];

%t Table[Length[Select[sps[Range[n]],!nesXQ[#]&&capXQ[#]&]],{n,0,8}]

%Y MM-numbers of capturing, non-nesting multiset partitions are A326260.

%Y Nesting set partitions are A016098.

%Y Capturing set partitions are A326243.

%Y Non-crossing, nesting set partitions are A122880 (conjectured).

%Y Cf. A000110, A054391, A058681, A095661, A099947.

%Y Cf. A326212, A326237, A326245, A326246, A054391, A326255, A326256.

%K nonn,more

%O 0,7

%A _Gus Wiseman_, Jun 20 2019