# On the Number of k-Crossing Partitions

## Abstract

I introduce $$k$$-crossing paths and partitions and count the number of paths for each number of desired crossings $$k$$ for systems with $$11$$ points or less. I give some conjectures into the number of possible paths for certain numbers of crossings as a function of the number of points.

## Introduction

A order $$n$$ meandric partition is a set of the integers $$1\cdots n$$, such that a path from the south-west can weave through $$n$$ points labeled $$1\cdots n$$ without intersecting itself and finally heads east (examples are shown in Fig. 1). Counting the number of possible paths for $$n$$ points is a tricky problem, and no recursion relation, generating function or explicit formula for the number of order $$n$$ meandric partitions appears to have been found. This work is concerned with the number of paths that must intersect themselves exactly $$k$$ times, where when $$k$$ is $$0$$, we have the meandric paths. It is possible to draw a line that deliberately crosses itself as many times as required, because of this we only consider a path to be $$k$$-crossing if $$k$$ is the smallest number of crossings possible, that is a path that must cross itself $$k$$ times (an example of a $$3$$-crossing path over $$9$$ points is given in Fig. 2).

## Results

Define $$a_{k}(n)$$ to be the number of configurations of $$n$$ points where the path through them is forced to cross itself $$k$$ times. For $$0$$-crossings on $$n$$ points we have the open meandric numbers, given in the OEIS as A005316

$$a_{0}(n)=1,1,1,2,3,8,14,42,81,262,538,1828,3926,\cdots,\;\;n=0,1,\cdots\\$$

this work has counted this for $$k>0$$ by calculating all $$n!$$ permutations of the $$n$$ integers and checking to see the minimal number of crossings for each, we then have

\begin{align} \begin{matrix}n=&0&1&2&3&4&5&6&7&8&9&10&11\cdots\\ a_{0}(n)=&1,&1,&1,&2,&3,&8,&14,&42,&81,&262,&538,&1828,\cdots\\ a_{1}(n)=&0,&0,&1,&4,&10,&36,&85,&312,&737,&2760,&6604,&25176,\cdots\\ a_{2}(n)=&0,&0,&0,&0,&8,&42,&168,&760,&2418,&10490,&30842,&131676,\cdots\\ a_{3}(n)=&0,&0,&0,&0,&2,&16,&164,&944,&4386,&22240,&83066,&398132,\cdots\\ a_{4}(n)=&0,&0,&0,&0,&1,&18,&146,&1076,&6255,&37250,&168645,&908898,\cdots\\ a_{5}(n)=&0,&0,&0,&0,&0,&0,&96,&960,&7388,&51968,&282122,&1711824,\cdots\\ a_{6}(n)=&0,&0,&0,&0,&0,&0,&30,&440,&6472,&55140,&384065,&2642444,\cdots\\ a_{7}(n)=&0,&0,&0,&0,&0,&0,&14,&368,&5176,&53920,&455944,&3575040,\cdots\\ a_{8}(n)=&0,&0,&0,&0,&0,&0,&2,&66,&3542,&45960,&484058,&4336734,\cdots\\ a_{9}(n)=&0,&0,&0,&0,&0,&0,&1,&72,&2011,&32280,&452504,&4661756,\cdots\\ a_{10}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&1172,&25066,&396493,&4709856,\cdots\\ a_{11}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&420,&11840,&309696,&4291440,\cdots\\ a_{12}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&201,&8930,&225754,&3661348,\cdots\\ a_{13}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&40,&2240,&151849,&2947392,\cdots\\ a_{14}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&18,&2040,&91147,&2103648,\cdots\\ a_{15}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&2,&224,&55030,&1575744,\cdots\\ a_{16}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&1,&270,&26762,&915924,\cdots\\ a_{17}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&0,&0,&14627,&665088,\cdots\\ a_{18}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&0,&0,&5405,&295956,\cdots\\ a_{19}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&0,&0,&2642,&218508,\cdots\\ a_{20}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&0,&0,&641,&63522,\cdots\\ a_{21}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&0,&0,&293,&54672,\cdots\\ a_{22}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&0,&0,&48,&8964,\cdots\\ a_{23}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&0,&0,&22,&9552,\cdots\\ a_{24}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&0,&0,&2,&706,\cdots\\ a_{25}(n)=&0,&0,&0,&0,&0,&0,&0,&0,&0,&0,&1,&972,\cdots\end{matrix}\\ \end{align}

where the vertical sum over columns of terms gives $$n!$$.

## Conjectures

The above information has lead to a few conjectures.

$$\text{Conjecture 1: }a_{n^{2}}(2n)=1\\$$

this can be converted to words as, there is exactly one path through $$2n$$ points that crosses $$n^{2}$$ times. The partitions associated with these paths are

\begin{align} (2,1) \\ (3,1,4,2) \\ (4,1,5,2,6,3) \\ (5,1,6,2,7,3,8,4) \\ (6,1,7,2,8,3,9,4,10,5)\\ \end{align}

and a clear interlaced pattern can be seen (an example is given in Fig. 3).

$$\text{Conjecture 2: }a_{n^{2}-1}(2n)=2,\;n>1\\$$ $$\text{Conjecture 3: }a_{n^{2}-2}(2n)=4n+2,\;n>2\\$$ $$\text{Conjecture 4: }a_{n^{2}-3}(2n)=8n+8,\;n>3\\$$ $$\text{Conjecture 5: }a_{n^{2}}(2n+1)=2(n+1)3^{n-1},\;n>1\\$$

Fig 1. An example of a meandric path (0-crossing path) with $$n=10$$. This path has meandric partition $$(1,2,3,8,5,6,7,4,9,10)$$.

Fig 2. An example of a path that crosses itself $$3$$ times on $$9$$ points. This path has partition $$(1,3,4,2,6,5,7,9,8)$$.