A324173 - OEIS

%I #13 Feb 19 2019 00:09:00

%S 1,0,1,0,1,1,0,1,3,1,0,2,6,6,1,0,6,15,20,10,1,0,21,51,65,50,15,1,0,85,

%T 203,252,210,105,21,1,0,385,912,1120,938,560,196,28,1,0,1907,4527,

%U 5520,4620,2898,1302,336,36,1,0,10205,24370,29700,24780,15792,7812,2730,540,45,1

%N Regular triangle read by rows where T(n,k) is the number of set partitions of {1,...,n} with k topologically connected components.

%C A set partition is crossing if it contains a pair of blocks of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

%C The topologically connected components of a set partition correspond to the blocks of its minimal non-crossing coarsening.

%H FindStat, <a href="http://www.findstat.org/StatisticsDatabase/St000925">The number of topologically connected components of a set partition</a>.

%e Triangle begins:

%e      1

%e      0     1

%e      0     1     1

%e      0     1     3     1

%e      0     2     6     6     1

%e      0     6    15    20    10     1

%e      0    21    51    65    50    15     1

%e      0    85   203   252   210   105    21     1

%e      0   385   912  1120   938   560   196    28     1

%e      0  1907  4527  5520  4620  2898  1302   336    36     1

%e      0 10205 24370 29700 24780 15792  7812  2730   540    45     1

%e Row n = 4 counts the following set partitions:

%e   {{1234}}    {{1}{234}}  {{1}{2}{34}}  {{1}{2}{3}{4}}

%e   {{13}{24}}  {{12}{34}}  {{1}{23}{4}}

%e               {{123}{4}}  {{12}{3}{4}}

%e               {{124}{3}}  {{1}{24}{3}}

%e               {{134}{2}}  {{13}{2}{4}}

%e               {{14}{23}}  {{14}{2}{3}}

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

%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 crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];

%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[crosscmpts[#]]==k&]],{n,0,8},{k,0,n}]

%Y Row sums are A000110. Column k = 1 is A099947.

%Y Cf. A000108, A001263, A002061, A002662, A007297, A016098, A048993, A054726, A293510, A305078, A305079, A323818.

%Y Cf. A324166, A324167, A324169, A324170, A324171, A324172.

%K nonn,tabl

%O 0,9

%A _Gus Wiseman_, Feb 17 2019