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: