Efficient Counting and Asymptotics of $k$-Noncrossing Tangled Diagrams

  • William Y. C. Chen
  • Jing Qin
  • Christian M. Reidys
  • Doron Zeilberger


In this paper, we enumerate $k$-noncrossing tangled diagrams. A tangled diagram is a labeled graph with vertices $1,\dots,n$, having degree at most two, which are arranged in increasing order in a horizontal line. The arcs are drawn in the upper halfplane with a particular notion of crossings and nestings. Our main result is the asymptotic formula for the number of $k$-noncrossing tangled diagrams $T_{k}(n) \, \sim \,c_k \, n^{-((k-1)^2+(k-1)/2)}\, (4(k-1)^2+2(k-1)+1)^n$ for some $c_k>0$.

Article Number