#####
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
*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*>=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: