[Math] Combinatorial proof that central binomial coefficients are the largest ones

binomial-coefficientscombinatorial-proofscombinatoricsinequality

We can easily show that the central binomial coefficients in a row of Pascal's triangle, i.e. $\binom{2n}n$ in even rows and $\binom{2n+1}n=\binom{2n+1}{n+1}$ in odd rows, have the largest values – more or less by straightforward computation.

It basically suffices to check that the following inequalities are equivalent to each other:
\begin{align*}
\binom nk &< \binom n{k+1} \\
\frac{n!}{k!(n-k)!} &< \frac{n!}{(k+1)!{(n-k-1)!}} \\
\frac{(k+1)!}{k!} &< \frac{(n-k)!}{(n-k-1)!}\\
k+1 &< n-k \\
2k+1 &< n
\end{align*}

And it works the same way for $\binom nk \le \binom n{k+1}$, $\binom nk \gt \binom n{k+1}$ and $\binom nk \ge \binom n{k+1}$ or even $\binom nk = \binom n{k+1}$. From this we can see that this sequence is first increasing and then decreasing. (Such sequences are sometimes called unimodular.) And we also see that the maximum is attained in the middle.

A few more proofs of this can be found here: How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

I would like to ask specifically about combinatorial proofs which show that we have the largest values in the middle of a row of Pascal's triangle.


EDIT: As pointed out in Michael Lugo's comment, there is in fact a combinatorial proof in one of the answers to the linked question. Still, I'd like to see some other combinatorial approaches, if they are possible.

Best Answer

Let $A$ be a set with $n$ elements. The involution $S \mapsto A\setminus S$ shows that $\binom{n}{k} = \binom{n}{n-k}$ for $0 \leqslant k \leqslant n$, so we can restrict our attention to $k \leqslant m := \bigl\lfloor \frac{n}{2}\bigr\rfloor$.

Suppose we want to select a committee of $m$ people, among which $k$ shall represent the committee to the outside world from a group of $n$ people. We can

  1. Select the $m$ members of the committee first, and then choose the $k$ representatives from the committee members afterwards. That is possible in $\binom{n}{m}\cdot \binom{m}{k}$ ways.
  2. First choose the $k$ representatives from the whole group, and then select the remaining $m-k$ committee members from the remaining $n-k$ group members. That is possible in $\binom{n}{k}\cdot \binom{n-k}{m-k}$ ways.

Using the symmetry of the binomial coefficients, it follows that

$$\binom{n}{m} = \frac{\binom{n-k}{m-k}}{\binom{m}{m-k}}\cdot \binom{n}{k}.\tag{1}$$

Now we note that for $0 \leqslant r \leqslant s \leqslant t$ we have

$$\binom{s}{r} \leqslant \binom{t}{r},\tag{2}$$

with equality if and only if $s = t$ or $r = 0$.

Since $n-k \geqslant n-m \geqslant m$, using the inequality $(2)$ in $(1)$ shows the desired

$$\binom{n}{m} \geqslant \binom{n}{k},$$

with equality if and only if $k = m$.

Related Question