Counting certain paths Suppose we wish to count the number (say $P(n)$) of lattice paths from $(0,0)$ to $(n,n)$ where at each step  one can make a move $1$ unit to the right or up, with the condition that every point $(k_1,k_2)$ obeys $k_2\geq\left\lceil\dfrac{k_1^2}{n}\right\rceil$, that is, lies inside the parabola passing through $(0,0)$, $(n,n)$ and $(-n,n)$. How does one enumerate these, other than of course bashing with brute force code?
Also, is there a good way (other than simulation) to estimate $\dfrac{P(n)}{\binom{2n}{n}}$, or maybe $\displaystyle\lim_{n\to\infty}\dfrac{P(n)}{\binom{2n}{n}}$? IE the probability that a lattice path from $(0,0)$ to $(n,n)$ lies in the parabola. Is there a nice way to estimate this? Any help is appreciated!
 A: A uniformly random selection from the ${{2n}\choose{n}}$ monotone lattice paths from $(0,0)$ to $(n,n)$ is expected to remain within a distance $O(\sqrt{n})$ from the diagonal, so the middle part of the path (where the parabola's distance from the diagonal is much larger than this) is safe; we expect paths to mostly fail this test near their beginnings and ends.  As such, we might expect $P(n)/{{2n}\choose{n}}$ to converge to a constant independent of $n$.  Direct enumeration is straightforward in $O(n^2)$ operations using dynamic programming: we count the legal paths from $(0,0)$ to $(x,y)$ for $x+y=1,2,\ldots,2n$, in order of increasing $x+y$, with each new count given in terms of one or two counts from the previous $x+y$.  If I'm not making any coding mistakes, this gives a sequence of values that starts with
$$
P(n)=1, 2, 5, 16, 53, 179, 614, 2203, 8718, 31836,\ldots
$$
(for $n=1,2,\ldots,10$). The ratio $P(n)/{{2n}\choose{n}}$ seems to converge to $0.15451$ or so, with the error in the final digit (at $n=10000$ it is $0.154535$, and at $n=20000$ it is $0.154522$).
