On Partitions Avoiding 3-Crossings

Mireille Bousquet-Mélou ; Guoce Xin

Séminaire lotharingien de combinatoire, Tome 54 (2006-2007)

Résumé

A partition on [n] has a crossing if there exists i₁i₂j₁j₂ such that i₁ and j₁ are in the same block, i₂ and j₂ are in the same block, but i₁ and i₂ 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 nth Catalan number C_n=\binom {2n} {n} / (n+1). This raises the question of counting k-noncrossing partitions for k>=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>=4. We obtain similar results for partitions avoiding enhanced 3-crossings.