Skip to main content
3 of 4
Corrected largest possible area to $n^2$
David Galvin
  • 1.1k
  • 8
  • 16

Distribution of the area statistic for Catalan paths

A Catalan path of semilength $n$ is a path from $(0,0)$ to $(2n,0)$ that proceeds by taking northeast (1,1) or southeast (1,-1) steps, and never goes below the $x$-axis. The area of a path $P$ is the area beneath the path and above the $x$-axis. So, for example, the path of semilength 3 that goes $(0,0)-(1,1)-(2,2)-(3,1)-(4,0)-(5,1)-(6,0)$ has area $5$.

The sum of the area of all Catalan paths of semilength $n$ is known to be $4^n - \binom{2n+1}{n}$, so that the average area of a path is on the order of $n^{3/2}$.

In an application I'm working on, I've found that it would be useful to have upper bounds on how many paths have area significantly greater than $n^{3/2}$. The largest possible area is $n^2$, and from Markov's inequality I can say that a vanishing proportion of paths have area greater than $n^2/1000$, say; specifically, there are no more than $O\left(4^n/n^2\right)$ such paths (whereas there are $\Theta\left(4^n/n^{3/2}\right)$ paths in total).

I suspect that there are far fewer paths with large area, and for my application I need a much lower upper bound. Are there quantitative results for this problem?

I can translate the problem into that of estimating the number of partitions of the number $N$ into at most $c\sqrt{N}$ parts each of size at most $c\sqrt{N}$, which in turn becomes a problem of estimating a coefficient of a Gaussian polynomial, but I'm not aware of quantatitive results here, either.

David Galvin
  • 1.1k
  • 8
  • 16