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

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.

Links

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

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

Formula

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

Example

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}}

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_, ___}, ___}/; x<z&&y>t||x>z&&y<t];
Table[Length[Select[sps[Range[n]], capXQ[#]&]], {n, 0, 8}]

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.

Sequence in context: A026897 A021024 A127021 * A091098 A091115 A024146

Adjacent sequences: A326240 A326241 A326242 * A326244 A326245 A326246

Keyword

nonn

Author

Gus Wiseman, Jun 19 2019

Extensions

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

Status

approved