%tangled.tex: Efficient Counting of k-noncrossing tangled diagrams
%%a Plain TeX file by W.illiam Y.C. Chen,
%Jing Qin, Christian Reidys, and Doron Zeilberger (xx pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\N{{\cal N}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\R{{\cal R}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\def\Tilde{\char126\relax}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
Efficient Counting and Asymptotics of k-noncrossing tangled diagrams
}
\rm
\bigskip
\centerline 
{ 
{\it William Y.C. CHEN}\footnote{$^1$}
{
{\eightrm
Supported by 973 Project, the PCSIRT Project of the Ministry
of Education, The Ministry of Science and Technology, and
the National Science Foundation of China
}
},
{\it Jing QIN}{$^1$},
{\it Christian M. REIDYS}{$^1$},
and {\it Doron ZEILBERGER}\footnote{$^2$}
{
{\eightrm
Supported in part by the USA National Science Foundation.
}
}
}

\bigskip

{\bf Important:} This article is accompanied
by a Maple package {\tt TANGLE} downloadable from
the webpage of this article

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/mamarimhtml/tangled.html}  .


\bigskip

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.

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

{\bf Observation 2}: The number of $(k+1)$-noncrossing diagrams
over $[n]$,
(allowing isolated points), equals the number of
simple lattice walks in $x_1 \geq x_2 \geq \dots \geq x_k \geq 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 {\it one} unit step in any (legal) direction,
or else feel energetic and make any {\it 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 \geq x_2 \geq \dots \geq x_k \geq 0$,
from the origin back to the origin, then, as shown in [CQR],
$\tilde D_{k+1}(n)$ the number of $k+1$-noncrossing tangled-
diagrams over $[n]$ without isolated points,
and $D_{k+1}(n)$ the number of such things possibly having
isolated points are given by:
$$
\tilde D_{k+1}(n)=\sum_{i=0}^{n} {{n} \choose {i}} f_k(2n-i) \quad,
$$
$$
D_{k+1}(n)=\sum_{i=0}^{n} {{n} \choose {i}} \tilde D_{k+1} (n-i) \quad.
$$

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 \times k$ determinant, featuring
the hyperbolic Bessel functions $I_m(2x)$:
$$
I_m(2x)=\sum_{j=0}^{\infty} { {x^{m+2j}} \over {j!(m+j)!} } \quad .
$$
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
$\tilde D_{k+1}(n)$ and $D_{k+1}(n)$, by general holonomic nonsense ([Z]).
It follows that for each $k$, these satisfy {\it linear recurrence
equations with polynomial coefficients}, and it is easy to bound
their orders and degrees. Hence, any {\it empirically} derived
recurrence (using the  command {\tt listtorec}
in the Salvy-Zimmerman Maple package {\tt gfun},
that we adapted to our own needs in our own
package {\tt TANGLE}), is {\it 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 \leq n \leq 1000$,
for $k=1,2,3$, and these sequences for $1 \leq n \leq 50$ for
$k=4,5$ (using a variant of the Grabiner-Magyar formula implemented
in our Maple package { \tt 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) \quad \Tilde  \quad 
C_k \, \cdot \, {{(4k^2+2k+1)^n} \over {n^{k^2+k/2} }} \quad.
$$

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).


{\bf References}

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

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

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

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

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

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



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

\medskip
{\bf Jing Qin}, 
Center for Combinatorics, LPMC-TJKLC, Nankai University,
Tianjin 300071, P.R. China.

\medskip
{\bf Christian Reidys}, 
Center for Combinatorics, LPMC-TJKLC, Nankai University,
Tianjin 300071, P.R. China.


\medskip

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

\end

\bigskip







 
 
