6
$\begingroup$

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: \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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Michael Lugo Oct 30 '17 at 17:14
  • $\begingroup$ @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.) $\endgroup$ – Martin Sleziak Oct 30 '17 at 17:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Nate Oct 30 '17 at 20:40
  • $\begingroup$ @Nate: that strengthening seems, to me, "more combinatorial" than the original proof, although it's hard to be precise about exactly why. $\endgroup$ – Michael Lugo Oct 31 '17 at 14:30
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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