Counting crossings

104 Views Asked by At

It is possible to count the number of non-crossing diagrams including $k$ bridges by using Catalan numbers. For instance in Fig 1, I show the 5 possible diagrams obtained for $k = 3$ bridges, which equals $Cat(3)$.

Possible diagrams without crossings with $k$ = 3

In general $$ N_{n.c.} (k) = Cat(k) $$ with $N_{n.c.}(k)$ the number of non-crossing diagrams with $k$ bridges.

My question is: is there a way to count the number of diagrams with a fixed number $\alpha$ of crossings: $N(k, \alpha)$? For instance, for $k=2$, we have $$ N(2, 0) = N_{n.c.}(2) = 2\;, \qquad N(2,1) = 1 $$ which are represented in Fig2. Note that I exclude degenerate cases where more than two bridges cross at the same point. Also starting and ending points of different bridges cannot coincide.

Diagrams with $k=2$ and $\alpha 0 ,1 $ crossings

The total contributions from diagrams with an arbitrary number of crossings $\alpha$ is also easy to compute: $$ N_{tot}(k) = \sum_{\alpha\geq 0} N(k, \alpha) = \frac{(2k)!}{2^k k!} $$

But what about the single coefficients $N(k, \alpha)$?

1

There are 1 best solutions below

2
On BEST ANSWER

In 2002 I gave an expression in alt.math.recreational, translated to your $k$ and $\alpha$ as

$$N(k,\alpha)=\sum_{j} (-1)^j { (k-j)(k-j+1)/2-1-\alpha \choose k-1} \left({2k \choose j}-{2k \choose j-1}\right)$$

where $j$ is such that $0 \le j \le k$ and $(k-j)(k-j+1) \ge 2(k + \alpha)$

OEIS A067311 has more information, as this is equivalent to counting handshakes across a table and the number of crossings as illustrated in

enter image description here