ON PARTITIONS AVOIDING 3-CROSSINGS

By Mireille Bousquet-Mélou, Guoce Xin. 2005

50 citations recorded by the source corpus.

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 = 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.

Subfields: Algebra and Number Theory, Discrete Mathematics and Combinatorics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/e2c433c4c5567cffd8f1d7276754c979832ed3e3

Citations in the corpus

• Walks with small steps in the quarter plane (2008, unknown): “Ever since it was imported from probability theory to combinatorics, this group has proved useful (in several disguises, like the obstinate, algebraic, or iterated kernel method) to solve various enumeration problems, dealing with walks [11, 13, 15, 33, 40, 41], but also with other objects, like per”