|
%I #5 Jun 21 2019 22:45:48
%S 1,1,2,5,14,41,123,374,1147,3538,10958,34042,105997
%N Number of non-capturing set partitions of {1..n}.
%C Conjectured to be equal to A054391.
%C A set partition is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and y > t or x > z and 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.
%F a(n) = A000110(n) - A326243(n).
%e The a(0) = 1 through a(4) = 14 non-capturing set partitions:
%e {} {{1}} {{1,2}} {{1,2,3}} {{1,2,3,4}}
%e {{1},{2}} {{1},{2,3}} {{1},{2,3,4}}
%e {{1,2},{3}} {{1,2},{3,4}}
%e {{1,3},{2}} {{1,2,3},{4}}
%e {{1},{2},{3}} {{1,2,4},{3}}
%e {{1,3},{2,4}}
%e {{1,3,4},{2}}
%e {{1},{2},{3,4}}
%e {{1},{2,3},{4}}
%e {{1,2},{3},{4}}
%e {{1},{2,4},{3}}
%e {{1,3},{2},{4}}
%e {{1,4},{2},{3}}
%e {{1},{2},{3},{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&&y>t||x>z&&y<t];
%t Table[Length[Select[sps[Range[n]],!capXQ[#]&]],{n,0,5}]
%Y Capturing set partitions are A326243.
%Y Non-crossing set partitions are A000108.
%Y Cf. A000110, A001519, A016098, A054391, A058681, A099947, A122880.
%Y Cf. A326212, A326237, A326245, A326246, A326249, A326255, A326256, A326260.
%K nonn,more
%O 0,3
%A _Gus Wiseman_, Jun 20 2019
|
