Efficient Counting and Asymptotics of k-Noncrossing Tangled Diagrams

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

  Abstract:   In this paper, we enumerate k-noncrossing tangled-diagrams. A tangled-diagram is a labeled graph with vertices 1,..., n, having degree ≤ 2, which are arranged in increasing order in a horizontal line. The arcs are drawn in the upper half-plane with a particular notion of crossings and nestings. Our main result is the asymptotic formula for the number of k-noncrossing tangled-diagrams Tk(n) ~ for some ck > 0.

  AMS Classification:   05A18.


  Download:  pdf