A326243 Number of capturing set partitions of {1..n}.

0, 0, 0, 0, 1, 11, 80, 503, 2993, 17609, 105017, 644528, 4107600, 27313805, 189866541, 1379728831, 10470032837, 82833202559, 681977545967, 5832430910181, 51723181525978, 474866750479993, 4506706112772881, 44151975623559477, 445958774322599940, 4638590033810841345

Offset: 0

Author

Gus Wiseman, Jun 19 2019

Keywords

• nonn

Comments

A set partition is capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. This is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

Examples

			The a(5) = 11 capturing set partitions:
  {{1,2,5},{3,4}}
  {{1,3,4},{2,5}}
  {{1,3,5},{2,4}}
  {{1,4},{2,3,5}}
  {{1,4,5},{2,3}}
  {{1,5},{2,3,4}}
  {{1},{2,5},{3,4}}
  {{1,4},{2,3},{5}}
  {{1,5},{2},{3,4}}
  {{1,5},{2,3},{4}}
  {{1,5},{2,4},{3}}
		

Links

• Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

Crossrefs

Non-capturing set partitions are A054391.

Crossing and nesting set partitions are (both) A016098.

Cf. A000108, A000110, A001519, A054391, A058681, A122880, A324170.

Cf. A326209, A326211, A326237, A326246, A326249, A326255, A326259.

Programs

Mathematica

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
capXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;xt||x>z&&y
				

Formula

a(n) = A000110(n) - A054391(n).

Extensions

a(12) and beyond from Christian Sievers, Aug 23 2024