Asymptotics – Conjecture on Proportion of Numbers in Pascal’s Triangle

asymptoticsbinomial-coefficientsconjectureseulers-number-epi

Consider Pascal's triangle with $30$ rows (the top $1$ is the $0$th row). The centre number is the number in the middle of row $30\times \frac23=20$, which is $\binom{20}{10}=184756$. The proportion of the numbers in the triangle that are less than this centre number is $\frac{364}{496}\approx0.7339$.

In the following graph, the horizontal axis is $n$, the number of rows in the triangle ($n$ is a multiple of $3$). The vertical axis is $P$, the proportion of numbers that are less than the centre number.

enter image description here

It looks like $P$ is approaching some limit. The rightmost data point is $n=138$ and $P=\frac{7078}{9730}\approx0.72744$. I put $0.72744$ into Wolfram, and it suggested $e^{-1/\pi}\approx 0.72738$.

Is the following conjecture true or false:

Conjecture: In Pascal's triangle with $n$ rows, where $n$ is a multiple of $3$, the proportion of numbers less than the centre number approaches $e^{-1/\pi}$ as $n\to\infty$.

I would not be too surprised if this is in fact the limiting proportion, since $e$ is related to Pascal's triangle and so is $\pi$.

My attempt: The numbers in the top $\frac23$ of the triangle are all less than the centre number. So we just need to determine the proportion of numbers in the bottom $\frac13$ that are less than the centre number. I considered the row that is $m$ rows below the centre number: I tried to work out the proportion of numbers in this row that are less than the centre number, to obtain an asympototic boundary curve, but I didn't succeed.

Context: I was trying to approximate the median of the numbers in the first $n$ rows of Pascal's triangle, and in my investigation I stumbled upon this possible result.

Best Answer

We can approximate this by an integral. Fix $N$ (and let it be large). Let $(\alpha, \beta) \in \mathbb{R}^2$, such that $0 \le \beta \le \alpha \le 1$; you're interested in the fraction of this area for which $$ {{\alpha N}\choose{\beta N}} =\frac{(\alpha N)!}{(\beta N)!((\alpha - \beta)N)!} \le \frac{(2N/3)!}{(N/3)!(N/3)!} = {{2N/3}\choose{N/3}}, $$ or $$ (\alpha N)!(N/3)!^2 \le (2N/3)!(\beta N)!((\alpha - \beta)N)!, $$ or (taking the log of both sides), $$ \log(\alpha N)!+2\log(N/3)! \le \log(2N/3)!+\log(\beta N)! + \log((\alpha-\beta)N)!. $$ We can use Stirling's approximation, $\log n! \approx n\log n - n$. For instance, $$ \log(\alpha N)! \approx\alpha N\log(\alpha N)-\alpha N = \alpha N \log\alpha + [(\log N-1)(\alpha N)]. $$ All the second terms (in square brackets) will cancel out entirely, leaving $$ \alpha N \log \alpha + (2N/3)\log(1/3) \le (2N/3)\log(2/3)+\beta N \log \beta + (\alpha-\beta)N\log(\alpha-\beta), $$ or $$ \alpha \log \alpha - \beta \log \beta - (\alpha - \beta)\log (\alpha - \beta) \le (2/3)\log 2 $$ or $$ -\mu \log \mu - (1-\mu)\log (1-\mu)\le\frac{2\log 2}{3\alpha}, $$ where $\mu=\beta / \alpha \in (0,1)$. Note that the left-hand side never exceeds $\log 2$, so when $\alpha \le 2/3$, all values of $\beta$ work (as we already knew). So we want $$ \begin{eqnarray} 2\int_{0}^{1}d\alpha \int_{0}^{\alpha} d\beta \; f(\alpha, \beta/\alpha) &=& 2\int_{0}^{1}\alpha d\alpha \int_{0}^{1} d\mu\; f(\alpha, \mu) \\ &=&2\int_{0}^{2/3}\alpha d\alpha + 2\int_{2/3}^{1}\alpha d\alpha \int_{0}^{1}d\mu\;f(\alpha, \mu) \\ &=& \frac{4}{9} + 2\int_{2/3}^{1}\alpha d\alpha \int_{0}^{1}d\mu\; f(\alpha, \mu), \end{eqnarray} $$ where $f(\alpha, \mu)=0$ if $g(\mu)\equiv-\mu\log \mu - (1-\mu)\log(1-\mu) \le (2\log 2)/(3\alpha)$ and $=1$ otherwise. Finally, noting that $g(\mu)=g(1-\mu)$, we can restrict our attention to $\mu\in(0,1/2)$, where the result further simplifies to $$ \frac{4}{9} + 4 \int_{2/3}^{1} g^{-1}\left(\frac{2\log 2}{3\alpha}\right) \alpha d\alpha. $$ The change of variable $\alpha = (2/3)/v$ gives $$ \frac{4}{9} + \frac{16}{9}\int_{2/3}^{1} \frac{g^{-1}(v \log 2)}{v^3}dv, $$ which may or may not be easier to evaluate.


Update:

If an explicit integral form in terms of $g$ (as opposed to $g^{-1}$) is wanted, then the change of variable $v = g(\mu) / \log2$ achieves that (except that one of the bounds of the integral must still be expressed in terms of $g^{-1}$). Specifically, this yields $$ \frac{4}{9}+\frac{16 \log^2 2}{9}\int_{\mu_0}^{1/2} \frac{\mu g'(\mu) d\mu}{g(\mu)^3}, $$ where $\mu_0 = g^{-1}((2/3)\log 2) \approx 0.17395$. Integrating by parts lets us simplify this even further, to this fairly elegant final expression: $$ 2 \left[\mu_0 + \left(\frac{2 \log 2}{3}\right)^2 \int_{\mu_0}^{1/2} \frac{d\mu}{g(\mu)^2} \right]. $$