# Combinatorial proof that central binomial coefficients are the largest ones

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.

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.

• The answer at math.stackexchange.com/a/880528/173 appears to be a combinatorial proof of this fact - there the equivalence of the inequalities ${n \choose k} < {n \choose k+1}$ and $k+1 < n-k$ is derived by counting subsets. Perhaps this answers your question; if it doesn't, in what way is it not an answer? (In my experience "combinatorial proof" doesn't mean the same thing to everybody.) Oct 30, 2017 at 17:14
• @MichaelLugo Yes, there is one proof there which is combinatorial. Maybe I should have pointed that out explicitly in the question. Still, I'd like to see some other combinatorial approaches. (For example, I vaguely recall that there seeing a proof of this using lattice paths.) Oct 30, 2017 at 17:59
• I'll note that the proof I gave that @MichaelLugo mentioned can be strengthened (using Hall's matching theorem) to show something a bit stronger: If $k+1 < n-k$ there exists an injective function $f$ from $k$ element subsets to $k+1$ subsets such that $S \subset f(S)$ for all $S$. If anyone has another nice proof of this strengthening I'd love to see it.
– Nate
Oct 30, 2017 at 20:40
• @Nate: that strengthening seems, to me, "more combinatorial" than the original proof, although it's hard to be precise about exactly why. Oct 31, 2017 at 14:30

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

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

• A minor technicality is all, but I believe we should be using $<$ and $>$ rather than $\leq$ and $\geq$ for the injection May 21, 2020 at 17:19