Counting certain paths

Solution 1:

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