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

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

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

Formula

a(n) = A000110(n) - A326254(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 A326254.

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

Author

Gus Wiseman, Jun 19 2019

Extensions

a(12)-a(17) from Christian Sievers, Aug 23 2024

Status

approved