Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings |
| |
Institution: | Department of Applied Mathematics (KAM) and Institute for Theoretical Computer Science (ITI), Charles University, Malostranské Náměstí 25, 118 00 Praha, Czech Republic |
| |
Abstract: | The number conn counts matchings X on {1,2,…,2n}, which are partitions into n two-element blocks, such that the crossing graph of X is connected. Similarly, cron counts matchings whose crossing graph has no isolated vertex. (If it has no edge, Catalan numbers arise.) We apply generating functions techniques and prove, using a more generally applicable criterion, that the sequences (conn) and (cron) are not P-recursive. On the other hand, we show that the residues of conn and cron modulo any fixed power of 2 can be determined P-recursively. We consider also the numbers scon of symmetric connected matchings. Unfortunately, their generating function satisfies a complicated differential equation which we cannot handle. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|