A192128 Number of set partitions of {1, ..., n} that avoid 7-nestings

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899321, 1382958475, 10480139391, 82864788832, 682074818390, 5832698911490

Offset

0,3

Comments

This is equal to the number of set partitions of {1, ..., n} that avoid 7-crossings.

The first 14 terms coincide with terms of A000110. Without avoidance of 7-crossings, the two sequences would be identical. [Alexander R. Povolotsky, Sep 19 2011]

Links

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

M. Bousquet-Mélou and G. Xin, On partitions avoiding 3-crossings, arXiv:math/0506551 [math.CO], 2005-2006.

Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to k-nonnesting partitions and permutations, arXiv preprint arXiv:1108.5615 [math.CO], 2011.

W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.

M. Mishna and L. Yen, Set partitions with no k-nesting, arXiv:1106.5036 [math.CO], 2011-2012.

Example

There are 190899322 partitions of 14 elements, but a(14)=190899321 because the partition {1,14}{2,13}{3,12}{4,11}{5,10}{6,9}{7,8} has a 7-nesting.

Crossrefs

Cf. A000110.

Sequence in context: A203642 A192867 A203643 * A203644 A203645 A203646

Adjacent sequences: A192125 A192126 A192127 * A192129 A192130 A192131

Keyword

nonn,more

Author

Marni Mishna, Jun 23 2011

Status

approved