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,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.

Links

Table of n, a(n) for n=0..54.

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

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.

Sequence in context: A047766 A336881 A369449 * A005078 A284446 A270030

Adjacent sequences: A324320 A324321 A324322 * A324324 A324325 A324326

Keyword

nonn,tabl,more

Author

Gus Wiseman, Feb 22 2019

Status

approved