Combinatorial proof that central binomial coefficients are the largest ones

Question

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.

Answer 1

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$.

Answer 2

Letting $S_k$ be the set of subsets of $\{1,2,\dots,n\}$ of size $k$, I will define an injection from $S_k$ to $S_{k+1}$ whenever $2k\le n$, and from $S_{k+1}\to S_k$ whenever $2k\ge n$. This proves that $|S_k|$ is maximized when $k=\lfloor n/2 \rfloor$.

Given a set in $X\in S_k$, make a string of $n$ open and closed paranatheses, where the $i^{th}$ symbol is a ")" if $i\in S$, and is a "(" otherwise. For example, when $n=18$, $k=7$,

X = {1,5,6,8,12,14,15}

)  (  (  (  )  )  (  )  (  (  (  )  (  )  )  (  (  (  
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18

Now, delete any matching parentheses, meaning a ( followed by a ). Continue deleting matching pairs, as deleting a pair may create new pairs, until none remain. The result on the example is

)  (                    (                    (  (  (  
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18

Note there are more (s than )s in what remains; this is because we started with a set whose size was smaller than $n/2$, and the imbalance is maintained when we delete matching pairs. In particular, there will always be at least one (. The mapping is achieved by flipping the leftmost ( to a ), then adding back in the same deleted pairs to get back a set.

)  )  (  (  )  )  (  )  (  (  (  )  (  )  )  (  (  (  
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 

f(X) = {1,2,5,6,8,12,14,15}

If we had instead started with a large set, we would have flipped the rightmost ) to a (.

This is an injection because the process is reversible; making the flip does not affect any of the matching pairs, so we can always tell which symbol was flipped by deleting all the matching pairs and finding the rightmost ) or leftmost (.