Bousquet-Mélou, Mireille; Xin, Guoce On partitions avoiding 3-crossings. (English) Zbl 1087.05009 Sémin. Lothar. Comb. 54, B54e, 21 p. (2005). Summary: A partition on \([n]\) has a crossing if there exists \(i_1<i_2<j_1<j_2\) such that \(i_1\) and \(j_1\) are in the same block, \(i_2\) and \(j_2\) are in the same block, but \(i_1\) and \(i_2\) are not in the same block. Recently, Chen et al. refined this classical notion by introducing \(k\)-crossings, for any integer \(k\). In this new terminology, a classical crossing is a 2-crossing. The number of partitions of \([n]\) avoiding \(2\)-crossings is well known to be the \(n\)th Catalan number \(C_n={\binom {2n} n}/(n+1)\). This raises the question of counting \(k\)-noncrossing partitions for \(k\geq 3\). We prove that the sequence counting \(3\)-noncrossing partitions is P-recursive, that is, satisfies a linear recurrence relation with polynomial coefficients. We give explicitly such a recursion. However, we conjecture that \(k\)-noncrossing partitions are not P-recursive, for \(k\geq 4\). We obtain similar results for partitions avoiding enhanced \(3\)-crossings. Cited in 19 Documents MSC: 05A18 Partitions of sets Keywords:D-finite series PDFBibTeX XMLCite \textit{M. Bousquet-Mélou} and \textit{G. Xin}, Sémin. Lothar. Comb. 54, B54e, 21 p. (2005; Zbl 1087.05009) Full Text: arXiv EuDML EMIS Online Encyclopedia of Integer Sequences: Number of set partitions of {1, ..., n} that avoid 3-crossings. Number of set partitions of {1, ..., n} that avoid 4-crossings. Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings). Number of set partitions of {1, ..., n} that avoid 5-nestings. Number of set partitions of {1, ..., n} that avoid 6-nestings. Number of set partitions of {1, ..., n} that avoid 7-nestings Number of set partitions of {1, ..., n} that avoid enhanced 4-crossings (or enhanced 4-nestings) Number of set partitions of {1,...,n} that avoid enhanced 5-crossings (or 5-nestings) Number of set partitions of {1, ..., n} that avoid enhanced 6-crossings (or enhanced 6-nestings). Number of set partitions of {1, ..., n} that avoid enhanced 7-crossings (or enhanced 7-nestings)