OFFSET
0,18
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.
EXAMPLE
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}}
MATHEMATICA
croXQ[stn_]:=MatchQ[stn, {___, {___, x_, ___, y_, ___}, ___, {___, z_, ___, t_, ___}, ___}/; x<z<y<t||z<x<t<y];
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]]]]]]]]];
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}]
CROSSREFS
KEYWORD
AUTHOR
Gus Wiseman, Feb 22 2019
STATUS
approved