Efficient Counting and Asymptotics of k-Noncrossing Tangled Diagrams

William Y.C. Chen, Jing Qin, C.M. Reidys and D. 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