On partitions avoiding 3-crossings
| dc.creator | Bousquet-Mélou, Mireille | |
| dc.creator | Xin, Guoce | |
| dc.date | 2005-06-27 | |
| dc.date | 2006-01-21 | |
| dc.date.accessioned | 2026-07-07T12:33:15Z | |
| dc.date.available | 2026-07-07T12:33:15Z | |
| dc.description | 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={{2n}\choose n}/(n+1)$. This raises the question of counting $k$-noncrossing partitions for $k\ge 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\ge 4$. | |
| dc.identifier | https://arxiv.org/abs/math/0506551 | |
| dc.identifier | http://arxiv.org/abs/math/0506551 | |
| dc.identifier | Seminaire Lotharingien de Combinatoire 54 (2005) Paper B54e (21 pp.) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/217059 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A15 05A18 | |
| dc.title | On partitions avoiding 3-crossings | |
| dc.type | text |