Báo cáo toán học: "Efficient Counting and Asymptotics of k-Noncrossing Tangled Diagrams"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Efficient Counting and Asymptotics of k-Noncrossing Tangled Diagrams. | Efficient Counting and Asymptotics of k-Noncrossing Tangled Diagrams William Y. C. Chen1 Jing Qin2 Christian M. Reidys3 Center for Combinatorics LPMC-TJKLC Nankai University Tianjin 300071 P. R. China 1chen@ 2qj@ 3duck@ Doron Zeilberger Mathematics Department Rutgers University New Brunswick Piscataway NJ USA zeilberg@ Submitted Feb 25 2008 Accepted Mar 4 2009 Published Mar 13 2009 Mathematics Subject Classification 05A18 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 halfplane 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 ck n- k-1 2 k-1 2 4 k 1 2 2 k 1 1 n for some ck 0. 1 Tangled diagrams as molecules or walks In this paper we compute the numbers of k-noncrossing tangled diagrams and prove the asymptotic formula Tk n - Ck n- k-1 2 k-1 2 4 k 1 2 2 k 1 1 n Ck 0. This article is accompanied by the Maple package TANGLE which is available at http zeilberg mamarim mamarimhtml . THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R37 1 i j h i jl j2 ij Ì1 Ì2 j i j il i2 jl j2 i j i jl j2 il i2 j2 jl i j Figure 1 Arcs in tangled diagrams a list of all possible arc-configurations. il Í2 j Ạ i k-noncrossing tangled diagrams are motivated by the studies of RNA molecules. They serve as combinatorial frames for searching molecular configurations and were recently studied 5 by the first three authors. Let us recall that a tangled diagram or tangle is a labeled graph over the vertex set n 1 . n with vertices of degree at most two drawn in increasing order in a horizontal line. Their arcs are drawn in the upper halfplane. In general a tangled diagram has isolated points and its types of nonisolated .