On non P-recursiveness of numbers of matchings (linear chord diagrams) with many crossings

Martin Klazar

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-26, 2001


The number $\mathrm{con}_n$ counts partitions $X$ of $\{1,2,\ldots,2n\}$ into $n$ two-element blocks such that the crossing graph of $X$ is connected. Similarly, $\mathrm{cro}_n$ counts partitions whose crossing graph has no isolated vertex. (If it has no edge, Catalan numbers arise.) We prove, using a more generally aplicable criterion, that the sequences $(\mathrm{con}_n)$ and $(\mathrm{cro}_n)$ are not P-recursive. They are even more ugly. On the other hand, we show that the residues of $\mathrm{con}_n$ and $\mathrm{cro}_n$ modulo any given power of 2 can be determined P-recursively. We consider also numbers $\mathrm{sco}_n$ of symmetric connected partitions. Unfortunately, their OGF satisfies a more complicated differential equation which we cannot handle.

Server START Conference Manager
Update Time 23 Feb 2001 at 08:48:02
Maintainer maylis@labri.u-bordeaux.fr.
Start Conference Manager
Conference Systems