Efficient Counting and Asymptotics of $k$-noncrossing tangled-diagrams

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

Efficient Counting and Asymptotics of $k$-noncrossing tangled-diagrams

Authors

Description

In this paper we enumerate $k$-noncrossing tangled-diagrams. A tangled-diagram is a labeled graph whose vertices are $1,...,n$ have degree $\le 2$, and are arranged in increasing order in a horizontal line. Its 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$.
9 pages and 2 figures