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

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

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.

\begin{equation} \text{Conjecture 1: }a_{n^{2}}(2n)=1\\ \end{equation}

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

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

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)\).