A306551 Number of non-double-crossing set partitions of {1,...,n}.

1, 1, 2, 5, 15, 52, 202, 863, 3999, 19880, 105134, 587479, 3449505

Offset: 0

Author

Gus Wiseman, Feb 23 2019

Keywords

• nonn
• more

Comments

Two blocks of a set partitions double-cross each other if they are of the form {{...a...b...c...},{...x...y...z...}} for some a < x < b < y < c < z or x < a < y < b < z < c.

Examples

			Most small set partitions are not double-crossing. The smallest that is double-crossing is {{1,3,5},{2,4,6}}.
		

Links

• Kenneth J. Dykema, Generating functions for purely crossing partitions, arXiv:1602.03469 [math.CO], 2016.

Crossrefs

Cf. A000108, A000110, A001263, A002061, A005493, A007297, A016098, A054726, A099947, A324166, A324167, A324172, A324324.

Programs

Mathematica

nonXXQ[stn_]:=!MatchQ[stn,{_,{_,a_,_,b_,_,c_,_},_,{_,x_,_,y_,_,z_,_},_}/;a_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],nonXXQ]],{n,0,8}]