6
$\begingroup$

I'm not an expert in combinatorics, but it sometimes comes up in my research with students in computer science (which is already pretty far away from my speciality of abstract homotopy theory). I just managed to reduce a problem to the question in the title, namely: given an integer $k$, what is the smallest $n$ such that

$${n \choose \lfloor n/2\rfloor } > k$$

This term ${n \choose \lfloor n/2\rfloor }$ comes up many places. Obviously, it's the max of the $n$ choose $r$ function. It's also the conclusion of Sperner's Theorem on antichains, and the paper A Sperner Theorem on Unrelated Chains of Subsets by Griggs-Stahl-Trotter relates it to the 2-dimension of a disjoint union of posets. But I can't seem to find a formula anywhere for $n$ as a function of $k$. I really want a precise formula, but currently don't even have a proof of the asymptotics so that could be a place to start.

Sorry if this is too elementary. This question has proven difficult to Google, because of its symbolic nature.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$
    – David White
    Sep 29, 2015 at 19:29
  • 5
    $\begingroup$ 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.) $\endgroup$
    – Boris Bukh
    Sep 29, 2015 at 19:32
  • 3
    $\begingroup$ 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. $\endgroup$
    – GH from MO
    Sep 29, 2015 at 19:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steve Huntsman
    Sep 29, 2015 at 21:00
  • 2
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Sep 30, 2015 at 18:55

1 Answer 1

Reset to default
1
$\begingroup$

This note by Kessler and Schiff gives pretty extensive asymptotics for the central binomial coefficients. I am quite sure that any sort of exact formula is hopeless.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer. I just skimmed through that paper and while it seems to have great asymptotics for ${2n \choose n}$, I could not seem to find much about the inverse of this function (i.e. a bound on $k$ above). Can you see how to use these asymptotics to derive a bound like the one in GH's comment above? Thanks again. $\endgroup$
    – David White
    Sep 29, 2015 at 20:18
  • 1
    $\begingroup$ The way you usually do such things is by Newton's method, with the first step ($n=\log_2 k$) being fairly obvious... $\endgroup$
    – Igor Rivin
    Sep 29, 2015 at 20:42
  • $\begingroup$ Okay, I wrote out an argument using Newton's method. I was going to post it as an answer, but I guess people felt the question was too elementary. I have to say: it was not too elementary to me, and I'm a pretty active mathematician. In fact, I think this is exactly what MO is supposed to be for. Anyway, thanks Igor for your answer and the pointer to Newton's method, and thanks GH for suggesting the target to approximate. $\endgroup$
    – David White
    Sep 30, 2015 at 11:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.