×

On partitions avoiding 3-crossings. (English) Zbl 1087.05009

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.

MSC:

05A18 Partitions of sets

Keywords:

D-finite series
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS