Efficient Counting and Asymptotics of k-noncrossing tangled diagrams

William Y.C. CHEN^{1}, Jing QIN^{1}, Christian M. REIDYS^{1}, and Doron ZEILBERGER^{2}

Important: This article is accompanied by a Maple package TANGLE downloadable from the webpage of this article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/tangled.html .

Motivated by studies of RNA, The first three authors recently studied[CQR] so-called k-noncrossing tangled diagrams. We refer to that article for the definitions.

We first make two interesting observations.

Observation 1: The number of (k + 1)-noncrossing diagrams over [n], without isolated points, equals the number of simple lattice walks in x_{1} ≥ x_{2} ≥ … ≥ x_{k} ≥ 0, from the origin back to the origin, taking n days, where at each day the walker can either make one unit step in any (legal) direction, or else feel energetic and make any two consecutive steps (chosen randomly).

Observation 2: The number of (k + 1)-noncrossing diagrams over [n], (allowing isolated points), equals the number of simple lattice walks in x_{1} ≥ x_{2} ≥ … ≥ x_{k} ≥ 0, from the origin back to the origin, taking n days, where at each day the walker can either feel lazy and stay in place, or make one unit step in any (legal) direction, or else feel energetic and make any two consecutive steps (chosen randomly).

These follow easily from the consideration in [CQR], and are left as amusing exercises for the readers.

Let f_{k}(n) be the number of ways of walking n steps in x_{1} ≥ x_{2} ≥ … ≥ x_{k} ≥ 0, from the origin back to the origin, then, as shown in [CQR], D̃_{k+1}(n) the number of k + 1-noncrossing tangleddiagrams over [n] without isolated points, and D_{k+1}(n) the number of such things possibly having isolated points are given by:

D̃_{k+1}(n) = ∑_{i=0}^{n} \binom{n}{i}f_{k}(2n − i) ,

D_{k+1}(n) = ∑_{i=0}^{n} \binom{n}{i}D̃_{k+1}(n − i) .

1 Supported by 973 Project, the PCSIRT Project of the Ministry of Education, The Ministry of Science and Tech-

nology, and the National Science Foundation of China 2 Supported in part by the USA National Science Foundation.

There is an explicit determinant formula, due to Grabiner and Magyar[GM] (see also [CDDSY] Eq. 9) that expresses the exponential generating function of f_{k}(n), for each fixed k, as a k × k determinant, featuring the hyperbolic Bessel functions I_{m}(2x):

I_{m}(2x) = ∑_{j=0}^{∞} \frac{x^{m+2j}}{j!(m + j)!} .

The exact form of that formula shouldn’t concern us.

Since all the I_{m}’s are D-finite (see [S]), so is any polynomial in them ([S]), in particular the Grabiner-Magyar formula. Hence the f_{k}(n), for each k, are P -recursive (in n), ([S]) and hence so are D̃_{k+1}(n) and D_{k+1}(n), by general holonomic nonsense ([Z]). It follows that for each k, these satisfy linear recurrence equations with polynomial coefficients, and it is easy to bound their orders and degrees. Hence, any empirically derived recurrence (using the command listtorec in the Salvy-Zimmerman Maple package gfun, that we adapted to our own needs in our own package TANGLE), is ipso facto rigorous.

We found the explicit recurrences for k = 1, k = 2, k = 3, and they can be found in the webpage of this article.

Also once recurrences are found, they are very efficient in extending the counting sequences. In the same page one can find the sequences for D_{k+1}(n) for 1 ≤ n ≤ 1000, for k = 1, 2, 3, and these sequences for 1 ≤ n ≤ 50 for k = 4, 5 (using a variant of the Grabiner-Magyar formula implemented in our Maple package TANGLE ).

Using rigorous asymptotics for k = 1, 2, 3, and non-rigorous “series analysis” due to Zinn-Justin, we safely conjecture that, for any fixed k, we have the asymptotics:

D_{k+1}(n) ˜ C_{k} · \frac{(4k^{2} + 2k + 1)^{n}}{n^{k^{2}+k/2}} .

This should be provable using standard asymptotic techniques from the integral representation formulas that can be derived from either the Grabiner-Magyar[GM] formula or directly from the Gessel-Zeilberger formula [GZ] (that the former uses).

References

[CDDSY] W.Y.C. Chen, E.Y.P. Deng, R.R.X. Du, R.P. Stanley and C. H. Yan, Crossings and Nestings of Matchings and Partitions, Trans. Amer. Math. Soc. 359 (2007), 1555-1575.

[CQR] W.Y.C. Chen, J. Qin, and C. M. Reidys, Crossings and Nestings in Tangled Diagrams, preprint. Available from arXiv:0710.4053.

[GZ] I. Gessel and D. Zeilberger, Random Walk in a Weyl chamber, Proc. Amer. Math. Soc. 115, 27-31 (1992).

[GM] D. Grabiner and P. Magyar, Random Walks in a Weyl Chamber and the decomposition of tensor powers, J. Alg. Combinatorics 2 (1993), 239-260.

[S] R. Stanley, Differentiably Finite Power Series, Europ. J. Combinatorics 1 (1980), 175-188.

[Z] D. Zeilberger, A Holonomic systems approach to special functions identities, J. of Computational and Applied Math. 32, 321-368 (1990).

William Y.C. Chen, Center for Combinatorics, LPMC-TJKLC, Nankai University, Tianjin 300071, P.R. China.

Jing Qin, Center for Combinatorics, LPMC-TJKLC, Nankai University, Tianjin 300071, P.R. China.

Christian Reidys, Center for Combinatorics, LPMC-TJKLC, Nankai University, Tianjin 300071, P.R. China.

Doron Zeilberger, Mathematics Department, Rutgers University (New Brunswick), Piscataway, NJ, USA. zeilberg@math.rutgers.edu .