A326245 - OEIS

%I #7 Oct 29 2024 19:54:31

%S 0,0,0,0,1,7,34,141,537,1941,6777,23096,77340

%N Number of crossing, non-capturing set partitions of {1..n}.

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

%H Eric Marberg, <a href="http://arxiv.org/abs/1203.5738">Crossings and nestings in colored set partitions</a>, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

%e The a(4) = 1 and a(5) = 7 set partitions:

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

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

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

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

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

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

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

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

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

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

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

%Y Crossing set partitions are A016098.

%Y Non-capturing set partitions are A054391.

%Y Crossing, capturing set partitions are A326246.

%Y Cf. A000108, A000110, A001519, A054391, A058681, A095661, A324170.

%Y Cf. A326212, A326237, A326243, A326248, A326249.

%K nonn,more

%O 0,6

%A _Gus Wiseman_, Jun 20 2019