\documentclass{article}
\usepackage{fancyhdr}
\usepackage{amsthm}
\usepackage{etoolbox}
\usepackage{verbatim}
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{algorithmicx}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{amssymb}
\usepackage{tikz}
\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

\begin{document}

{\bf Abstract}
\\\\
In this note, we present some empirical data on an old problem in rational Catalan combinatorics. In particular, counting lattice paths that lie to one side of a line with rational slope.

{\bf Maple packages and data files}
\\\\
This article is accompanied by the maple package {\tt RSP.txt}
and several example inputs and outputs available at

{\tt http://www.math.rutgers.edu/\~ajl213/DrZ/RSP.html} 

{\bf Background}
\\\\
There is a rich study of Dyck paths in combinatorics. Some of the most ubiquitous results are for the case that the slope of the line is 1. In particular that the number of paths from (0,0) to (n,n) is counted by the Catalan numbers. When we change it from 1 to another rational number $a/b$, we enter the realm of appropriately named Rational Catalan Combinatorics. For notational convenience, we'll let $A_{a,b,n}$ denote the number of paths from $(0,0)$ to $(b,a)$ staying on or below the line $y=a/bx$. 

It was shown by Duchon in 2000 that for any slope $\frac{a}{b}$, the number of paths below a line of that slope is asymptotically $\Theta\left(\frac{1}{n} \binom{(a+b)n}{an}\right)$ [D1].  However, it's still unknown what the constant out front is. To show the asymptotics, Duchon showed that the content is somewhere between $\frac{1}{a+b}$ and  $\frac{1}{a}$. This upper bound on the number of paths was known at least as far back as 1950 to Grossman. Grossman also had an interesting result, the first proof of which is given by Bizley in 1954 in a now defunt actuarial journal [B]. It gives that gives an exact formula for every $A_{a,b,n}$.Of course, this precision comes at a cost, The formula is given as a sum over a large set of weighted integer partitions. There is no good way to extract estimates from this formula that we know, but it seems powerful and may be useful for this problem in the future. It would be great to have a simpler explanation of the simper problem of determining this value up to a $(1+o(1))$ factor.

It's clear that $A_{a,b,n} = A_{b,a,n}$, so in this paper, we'll assume that we always have $a>b$.

 For the case $b=1$, there is an exact solution known, using Fuss-Catalan numbers $\frac{1}{1+an} \binom{(1+a)n}{an}$.

{\bf This Article}
\\\\
We would like to try and find the coefficient out front, that is, $\alpha$ so that the number of paths is $\left(1+o(1)\right) \frac{\alpha}{n} \binom{(a+b)n}{an}$. In an effort to do this, we first are tasked with computing many terms of the sequence

Through a simple dynamic programming algorithm, we are able to compute the number of paths from (0,0) to (bn,an) for n around a thousand. This gives us enough data to try and find a recurrence relation that it satisfies using the maple package available at {\tt http://www.math.rutgers.edu/~zeilberg/tokhniot/FindRec.txt} However, we were only able to successfully find recurrences for the slopes $3/2$ and $5/2$. Armed with these recurrences we are able to blindingly fast crank out many thousands more terms of this sequence. The recurrence in the data file for slope 3/2 is order 4, whereas the one for 5/2 is order 8 and monstrously long. Though we can't guarantee this is the minimal recurrence, it still gives a massively faster of counting the paths for these two unknown slopes, and potentially for many more slopes that our computer wasn't keen enough to find this time.

Then, once we have exact numbers, we do a statistical fit of the data for many values of n against the model $\left(\frac{\alpha}{n} + \frac{\beta}{n^2}+\frac{\gamma}{n^3}+\frac{\delta}{n^4}\right)\binom{(a+b)n}{an}$ to get our estimate of $\alpha$. Adding more error terms didn't affect the value of $\alpha$ much. We estimate how close this is to the truth by running it for the first 100 values of n, and the first 200 values of n, and seeing how much our estimate stays the same. We can get quite good estimates of these numbers!


\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|}
\hline
a\textbackslash b&2&3&4&5&6&7\\
\hline
\hline
2&&1&&&&\\
3&0.240706636&1&&&&\\
4&0.50000000&0.15972479544&1&&&\\
5&0.1613399969&0.1372518253&0.119952918&1&&\\
6&0.333333333&0.50000000&0.240706636&0.09621264003&1 &\\
7&0.1216701970&0.1073342967&0.09639805178&0.08763172133&0.08039623916&0.999999\\
8&0.250000000&0.09683505915&0.5000000&0.08048157890&0.159724795&0.06908631788\\
\hline
\end{tabular}
\end{center}

There are many more slopes for which we have very exact estimates of $\alpha$, and are availiable online at

{\tt http://www.math.rutgers.edu/\~ajl213/DrZ/RSP.html} in the extra data file.

Though we knew it already with Duchon's result that the value of the coefficient is at most $1/a$, it still seems surprising that the value of the coefficient is not monotone in the value of the slope, that is the actual number $a/b$. We can notice a few simple patterns here, in particular, except in the cases that $a$ and $b$ are not in lowest terms, the value of coefficient decreases as you increase either $a$ or $b$. 

We can investigate this second observation a little further. A similar, but interesting and distinct problem is to try letting something else go to infinity in $A_{a,b,n}$ other than n, as we had before.

Suppose instead that we were to let a go to infinity while b is fixed. There's a nice pattern that appears. In particular, we have the conjecture that it is asymptotically equal to $\frac{gcd(a,b)}{a}$. The $gcd(a,b)$ factor makes sense because it makes the expression only depend on the value of $a/b$.

\begin{figure}[h]
\caption{$a\alpha$ as a function of a for $b=2$}
\includegraphics[height=.4\textwidth,width=.8\textwidth]{a2.jpg}
\end{figure}

\begin{figure}[h]
\caption{$a \alpha$ as a function of a for $b=8$}
\includegraphics[height=.4\textwidth,width=.8\textwidth]{a8.jpg}
\end{figure}

\pagebreak
{\bf References}

[B] M. T. L. Bizley, {\it DERIVATION OF A NEW FORMULA FOR THE NUMBER OF MINIMAL LATTICE PATHS FROM (o, o) TO (km, kn) HAVING JUST t CONTACTS WITH THE LINE my=nx AND HAVING NO POINTS ABOVE THIS LINE; AND A PROOF OF GROSSMAN'S FORMULA FOR THE NUMBER OF PATHS WHICH MAY TOUCH BUT DO NOT RISE ABOVE THIS LINE}, Journal of the Institute of Actuaries {\bf 80} (1954), 55-62.

[D1] Phillipe Duchon, {\it On the enumeration and generation of generalized Dyck words}, Discrete Mathematics {\bf 225} (2000), 121-135

\bigskip
\bigskip
\hrule
\bigskip
Andrew Lohr, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. ajl213 at math dot rutgers dot edu; \quad {\tt http://www.math.rutgers.edu/\~{}ajl213/} \quad .
\bigskip
\hrule
\bigskip
Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill \break
DoronZeil at gmail dot com  \quad ;  \quad {\tt http://www.math.rutgers.edu/\~{}zeilberg/} \quad .
\bigskip
\hrule

\bigskip
\bigskip

{\bf  First Written:  April 14, 2017; This version: April 20, 2017.}.
\end{document}
