A324323 Regular triangle read by rows where T(n,k) is the number of topologically connected set partitions of {1,...,n} with k blocks, 0 <= k <= n.

1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 5, 0, 0, 0, 0, 1, 16, 4, 0, 0, 0, 0, 1, 42, 42, 0, 0, 0, 0, 0, 1, 99, 258, 27, 0, 0, 0, 0, 0, 1, 219, 1222, 465, 0, 0, 0, 0, 0

Offset: 0

Author

Gus Wiseman, Feb 22 2019

Keywords

• nonn
• tabl
• more

Comments

A set partition of {1,...,n} is topologically connected if the graph whose vertices are the blocks and whose edges are crossing pairs of blocks is connected, where two blocks cross each other if they are of the form {{...x...y...},{...z...t...}} for some x < z < y < t or z < x < t < y.

Examples

			Triangle begins:
    1
    0    1
    0    1    0
    0    1    0    0
    0    1    1    0    0
    0    1    5    0    0    0
    0    1   16    4    0    0    0
    0    1   42   42    0    0    0    0
    0    1   99  258   27    0    0    0    0
    0    1  219 1222  465    0    0    0    0    0
Row n = 6 counts the following set partitions:
  {{123456}}  {{1235}{46}}  {{13}{25}{46}}
              {{124}{356}}  {{14}{25}{36}}
              {{1245}{36}}  {{14}{26}{35}}
              {{1246}{35}}  {{15}{24}{36}}
              {{125}{346}}
              {{13}{2456}}
              {{134}{256}}
              {{1345}{26}}
              {{1346}{25}}
              {{135}{246}}
              {{1356}{24}}
              {{136}{245}}
              {{14}{2356}}
              {{145}{236}}
              {{146}{235}}
              {{15}{2346}}
		

Crossrefs

Row sums are A099947. Row k = 2 is A002662.

Cf. A000108, A000110, A001263, A016098, A136653, A268814, A268815, A306438, A324011.

Cf. A324166, A324172, A324173, A324327, A324328.

Programs

Mathematica

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],Length[crosscmpts[#]]<=1&&Length[#]==k&]],{n,0,6},{k,0,n}]