cp's OEIS Frontend

A326336 Number of set partitions of {1..n} whose capturing blocks are connected.

%I A326336 #6 Jun 28 2019 21:14:48
%S A326336 1,1,1,1,2,7,24,100,458,2279,12270
%N A326336 Number of set partitions of {1..n} whose capturing blocks are connected.
%C A326336 Two blocks are capturing if they are of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. A set partition has its capturing blocks connected if the graph whose vertices are the blocks and whose edges are capturing pairs of blocks is connected.
%e A326336 The a(0) = 1 through a(6) = 24 set partitions:
%e A326336   {}  {1}  {12}  {123}  {1234}    {12345}    {123456}
%e A326336                         {14}{23}  {125}{34}  {1236}{45}
%e A326336                                   {134}{25}  {1245}{36}
%e A326336                                   {135}{24}  {1246}{35}
%e A326336                                   {14}{235}  {125}{346}
%e A326336                                   {145}{23}  {1256}{34}
%e A326336                                   {15}{234}  {126}{345}
%e A326336                                              {134}{256}
%e A326336                                              {1345}{26}
%e A326336                                              {1346}{25}
%e A326336                                              {135}{246}
%e A326336                                              {1356}{24}
%e A326336                                              {136}{245}
%e A326336                                              {14}{2356}
%e A326336                                              {145}{236}
%e A326336                                              {1456}{23}
%e A326336                                              {146}{235}
%e A326336                                              {15}{2346}
%e A326336                                              {156}{234}
%e A326336                                              {16}{2345}
%e A326336                                              {15}{26}{34}
%e A326336                                              {16}{23}{45}
%e A326336                                              {16}{24}{35}
%e A326336                                              {16}{25}{34}
%t A326336 capXQ[stn_]:=MatchQ[stn,{___,{___,x_,___,y_,___},___,{___,z_,___,t_,___},___}/;x<z<t<y||z<x<y<t];
%t A326336 csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
%t A326336 captcmpts[stn_]:=csm[Union[List/@stn,Select[Subsets[stn,{2}],capXQ]]];
%t A326336 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A326336 Table[Length[Select[sps[Range[n]],Length[captcmpts[#]]<=1&]],{n,0,6}]
%Y A326336 Simple graphs whose capturing blocks are connected are A326330.
%Y A326336 Set partitions whose crossing blocks are connected are A099947.
%Y A326336 Set partitions whose nesting blocks are connected are A326335.
%Y A326336 Cf. A000110, A001519, A016098, A122880, A324173, A326243, A326248, A326293, A326331, A326337.
%K A326336 nonn,more
%O A326336 0,5
%A A326336 _Gus Wiseman_, Jun 28 2019