A326336 - OEIS

%I #6 Jun 28 2019 21:14:48

%S 1,1,1,1,2,7,24,100,458,2279,12270

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

%C 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 The a(0) = 1 through a(6) = 24 set partitions:

%e   {}  {1}  {12}  {123}  {1234}    {12345}    {123456}

%e                         {14}{23}  {125}{34}  {1236}{45}

%e                                   {134}{25}  {1245}{36}

%e                                   {135}{24}  {1246}{35}

%e                                   {14}{235}  {125}{346}

%e                                   {145}{23}  {1256}{34}

%e                                   {15}{234}  {126}{345}

%e                                              {134}{256}

%e                                              {1345}{26}

%e                                              {1346}{25}

%e                                              {135}{246}

%e                                              {1356}{24}

%e                                              {136}{245}

%e                                              {14}{2356}

%e                                              {145}{236}

%e                                              {1456}{23}

%e                                              {146}{235}

%e                                              {15}{2346}

%e                                              {156}{234}

%e                                              {16}{2345}

%e                                              {15}{26}{34}

%e                                              {16}{23}{45}

%e                                              {16}{24}{35}

%e                                              {16}{25}{34}

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

%t 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 captcmpts[stn_]:=csm[Union[List/@stn,Select[Subsets[stn,{2}],capXQ]]];

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

%t Table[Length[Select[sps[Range[n]],Length[captcmpts[#]]<=1&]],{n,0,6}]

%Y Simple graphs whose capturing blocks are connected are A326330.

%Y Set partitions whose crossing blocks are connected are A099947.

%Y Set partitions whose nesting blocks are connected are A326335.

%Y Cf. A000110, A001519, A016098, A122880, A324173, A326243, A326248, A326293, A326331, A326337.

%K nonn,more

%O 0,5

%A _Gus Wiseman_, Jun 28 2019