A169584 The number of 2-noncrossing permutations of n elements.

1, 10, 76, 543, 3904, 29034, 225753, 1839540, 15679886, 139301291, 1284533342, 12245397495, 120245889336, 1212468083104, 12519738044138, 132078590232613, 1420721507725546, 15554949957165428

Offset

3,2

Comments

2nd column of table on p.4 of Burrill, Mishna, and Post. Table 2. Column 1 is the Catalan numbers A000108. "The number of permutations of S_n with crossing number k. A crossing number of 1 is equivalent to non-crossing."

Links

Table of n, a(n) for n=3..20.

Sophie Burrill, Marni Mishna and Jacob Post, On k-crossings and k-nestings of permutations, arXiv:0912.0239 [math.CO], 2009.

William Y. C. Chen, Eva Y. P. Deng, Rosena R. X. Du, Richard P. Stanley, and Catherine H. Yan, Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc., 359(4):1555-1575 (electronic), 2007.

Sylvie Corteel, Crossings and alignments of permutations, Adv. Appl. Math 38 (2007) 149-163.

Anna de Mier, k-Noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams, arXiv:math/0602195 [math.CO], 2006.

Anna de Mier, k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams, Combinatorica, 27(6), 699-720, 2007.

Formula

a(n) = A193938(n) - A000108(n). - Andrei Zabolotskii, Oct 31 2025

Crossrefs

Cf. A000108, A193938.

Sequence in context: A351132 A198692 A215465 * A107903 A075489 A184273

Adjacent sequences: A169581 A169582 A169583 * A169585 A169586 A169587

Keyword

nonn,more

Author

Jonathan Vos Post, Dec 02 2009

Extensions

Terms a(10)-a(20) using the formula added by Andrei Zabolotskii, Oct 31 2025

Status

approved