login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326243 Number of capturing set partitions of {1..n}. 21
0, 0, 0, 0, 1, 11, 80, 503, 2993, 17609, 105017, 644528 (list; graph; refs; listen; history; text; internal format)
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..11.

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 28 18:48 EDT 2021. Contains 346335 sequences. (Running on oeis4.)