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=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/(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$.

References in corpus (1)

• Walks confined in a quadrant are not always D-finite

Cited by in corpus (18)

• Walks with small steps in the quarter plane
• Two Non-holonomic Lattice Walks in the Quarter Plane
• Families of prudent self-avoiding walks
• Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers
• Enumeration of bilaterally symmetric 3-noncrossing partitions
• Tableau sequences, open diagrams, and Baxter families
• A generating tree approach to k-nonnesting partitions and permutations
• A combinatorial framework for RNA tertiary interaction
• Set partitions with no m-nesting
• A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape
• On $k$-noncrossing partitions
• Crossings and nesting in tangled-diagrams
• Constructing Skolem sequences via generating trees
• On sequences associated to the invariant theory of rank two simple Lie algebras
• Random $k$-noncrossing partitions
• Random 3-noncrossing partitions
• Errata and Addenda to Mathematical Constants
• On k-crossings and k-nestings of permutations