2

For $n=1000$, the binomial coefficients $\binom{n}{k}$ for $0 \le k \le n$ have on average about 716 bits (represented in binary). For $n=10000$, it's about 7207 bits. So about "$72\%$ of $n$". It seems to approach about $72.14\%$:

    n
        10 => 53.6364%
       100 => 68.6832%
     1,000 => 71.6248%
    10,000 => 72.0673%
   100,000 => 72.1263%
 1,000,000 => 72.1337%
10,000,000 => 72.1346%

Is that correct? Does it converge to something like 72.14%? What is the limit?

Background: It's related to a programming problem, where input size is $n$, and which can be solved with the help of computing all $\binom{n}{k}$ for $0 \le k \le n$. And I'm interested in the runtime complexity, which depends on their sizes.

Code to reproduce the above table

Stefan Pochmann
  • 221
  • Should I include the code in the question? Would be safer in the long run, but it's lengthy and I don't want to clutter. – Stefan Pochmann Apr 03 '22 at 09:13
  • If $D_b(n)$ represents the number of digits of $n$ in base $b$, note that (at least for positive integer bases $b \ge 2$) we have

    $$D_b(n) = \left\lceil \log_b(n+1) \right\rceil$$

    We'll consider $b=2$ and $n$ replaced by $\binom nk$. We ultimately seek the average of $D_2(\binom n k)$ across each $k$, as a proportion of $n$:

    $$M_n := \frac 1 {n^2} \sum_{k=1}^n D_2 \left( \binom n k \right)$$

    and in particular, $\displaystyle \lim_{n \to \infty} M_n$. --- [cont.]

     – PrincessEev Apr 03 '22 at 09:50
  • 1
    If we're ultimately interested in asymptotics we can loosen the ceiling and the $n+1$ to have

    $$M_n \approx \frac 1 {n^2} \log_2 \left( \prod_{k=1}^n \binom n k \right)$$

    in the end. I'm not really getting any meaningful results from here though; I keep trying further approximations to get something I think I can work with, but it never quite works out. Maybe someone else will have some ideas.

     – PrincessEev Apr 03 '22 at 09:51
  • 1
    This is essentially a variation on this question and the answer is $\frac{1}{2}\log_2 e =0.72134752044$. – J.-E. Pin Apr 03 '22 at 10:28
  • 1
    From @EeveeTrainer 's comment, this can be simplified to $$\frac{1}{n^2} \sum_{k=1}^n (2k-n-1) \log_2 k$$ and Wolframalpha says the limit is $1/\ln 4 \approx 0.72134752$. – Saturday Apr 03 '22 at 10:30

0 Answers0