A326335 - OEIS

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

%S 1,1,1,1,2,6,21,86,394,1974,10696

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

%C Two blocks are nesting 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 nesting blocks connected if the graph whose vertices are the blocks and whose edges are nesting pairs of blocks is connected.

%e The a(0) = 1 through a(6) = 21 set partitions:

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

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

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

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

%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[nestcmpts[#]]<=1&]],{n,0,5}]

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

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

%Y Set partitions whose capturing blocks are connected are A326336.

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

%K nonn,more

%O 0,5

%A _Gus Wiseman_, Jun 27 2019