Séminaire Lotharingien de Combinatoire, B54e (2006), 21 pp.

Mireille Bousquet-Mélou and Guoce Xin

On Partitions Avoiding 3-Crossings

Abstract. A partition on [n] has a crossing if there exists i1<i2<j1<j2 such that i1 and j1 are in the same block, i2 and j2 are in the same block, but i1 and i2 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 Cn=\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.

Received: June 27, 2005. Accepted: November 10, 2005. Final Version: February 3, 2006.

The following versions are available: