Timeline for Given k, what is the minimum n such that n choose n/2 is greater than k? [closed]
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 14, 2019 at 16:56 | vote | accept | David White | ||
| Sep 30, 2015 at 18:55 | comment | added | Douglas Zare | When $n$ is even, ${n \choose n/2}/{n-1 \choose \lfloor (n-1)/2 \rfloor}= 2$. When $n$ is odd, ${n \choose \lfloor n/2 \rfloor} / {n-1 \choose (n-1)/2} = 2n/(n+1) = 2 - 2/(n+1)$ which is close to $2$. So, for large $n$, increasing $n$ by $1$ roughly doubles ${n \choose n/2} \approx 2^n \sqrt{\frac{2}{\pi n}}$. If you choose a real $n \gt 1$ so that $2^n \sqrt{\frac{2}{\pi n}}$ is off by less than a factor of about $2$ from $k$, then you are off by at most $1$. I believe $\log _2 k + 1/2 \log_2 \log_2 k$ works, though I haven't checked small values. | |
| Sep 30, 2015 at 5:33 | history | closed |
Boris Bukh Allen Knutson Felipe Voloch Alexey Ustinov Yoav Kallus |
Not suitable for this site | |
| Sep 29, 2015 at 21:00 | comment | added | Steve Huntsman | The values of $n$ corresponding to $k \in [70]$ are 2,3,4,4,4,5,5,5,5,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9 and this has no matches in OEIS. | |
| Sep 29, 2015 at 20:15 | comment | added | David White | @GHfromMO: could you give a reference for that or sketch an argument? That is probably the answer I'm looking for, but it doesn't appear in either the wikipedia article or Igor's answer | |
| Sep 29, 2015 at 20:07 | comment | added | David White | @Boris: Thanks, I'll check that out. Thanks GH for the even more explicit answer. I'm actually kind of happy that there is no exact formula, since I wasted a fair bit of time today trying to find one. | |
| Sep 29, 2015 at 19:49 | review | Close votes | |||
| Sep 30, 2015 at 5:33 | |||||
| Sep 29, 2015 at 19:36 | comment | added | GH from MO | It is clear from the asymptotic formula for the central binomial coefficient (cf. Boris Bukh's comment above) that the smallest $n$ is $\log_2 k+\frac{1}{2}\log_2\log_2 k+O(1)$. I doubt there is a nice exact formula though. | |
| Sep 29, 2015 at 19:33 | answer | added | Igor Rivin | timeline score: 1 | |
| Sep 29, 2015 at 19:32 | comment | added | Boris Bukh | This is called the "middle binomial coefficient" or "central binomial coefficient". There is even a Wikipedia page devoted to it, which includes asymptotics. The asymptotics in question can be derived from Stirling's approximation to the factorial. (Voting to move to M.SE. as not research-level.) | |
| Sep 29, 2015 at 19:29 | comment | added | David White | My question might be related to this one here, but again I can't seem to read off a formula from that: mathoverflow.net/questions/132263. At the very least, it seems the question could be reformulated to be about blocks in a maximal packing | |
| Sep 29, 2015 at 19:28 | history | asked | David White | CC BY-SA 3.0 |