How to count partitioned subsets of a binomial coefficient

Question

I have been reading Dr. Carl Wagner's book Basic Combinatorics, and I cannot wrap my head around a particular theorem. Someone else has asked a very similar question and accepted an answer, but I'm afraid I still don't understand.

As stated, the theorem runs thus:

For all $ n, \; k \in \mathbb{N} $ $ \displaystyle \sum_{j = 0}^{n} \binom{j}{k} = \displaystyle \sum_{j = k}^{n} \binom{j}{k} = \binom{n + 1}{k + 1} $

There follows a proof of the $\binom{n + 1}{k + 1} $ bit using some handy substitutions. What confuses me is the next part:

#2. Clearly $ \binom{n+1}{k+1} $ counts the class of all (k + 1)-element subsets of [n + 1]. But this class of k+1 subsets may be partitioned into subclasses corresponding to j = k, k + 1, . . . , n as follows.

The subclass of subsets with largest element equal to k + 1 is counted by $ \binom{k}{k} $ (why?), the subclass of subsets with largest element equal to k + 2 is counted by $ \binom{k+1}{k} $ (why?), . . ., and the subclass of subsets with largest element equal to n + 1 is counted by $ \binom{n}{k} $ (why?).

I don't understand why at all! Indeed, it makes no sense to me.

It seems to me that the number of subsets of [n+1] with largest element k+1 would be $\binom{k+1}{k+1}$. Sure, that's the same as $ \binom{k}{k} $ since they both equal one, but that just seems to be a coincidence. We're choosing k+1 numbers from a set that runs from 1 to k+1. There can, naturally, be only one set that fits that bill. Yet to use $ \binom{k}{k} $ to represent that one set seems confusing to me, and every example that follows makes less sense.

What am I missing?

Answer 1

The largest element of a set has to be in the set. If you specify that $j+1$ is the largest element of a $(k+1)$-subset, it means that you have only $j$ choices $\{1,\dots,j\}$ for the remaining $k$ elements. The three examples given correspond to $j=k$, $j=k+1$, and $j=n$.

Answer 2

Let's say $n = 10$ and you want a subset of $4$ elements, the largest of which you want to be $6$.

Now that is not the same thing as choosing a subset of $\{1,2,3,4,5,6\}$ with $4$ elements because that would not guarantee that the largest element is $6$, only that the largest element is $6$ or less.

Here are all the $4$ element subsets whose largest element is $6$:

$$1236, 1246, 1256, 1346, 1356, 1456, 2346, 2356, 2456, 3456$$

Additionally, here are the $4$ element subsets of $\{1,2,3,4,5,6\}$ which were not listed already:

$$1234, 1235, 1245, 1345, 2345.$$

The important observation is that if you want $6$ to be in your set and you have no choice about the matter, then you are not choosing $6$. You choose $3$ elements of $\{1,2,3,4,5\}$ and then you get an extra $6$ whether you like it or not. And you will agree that we can pair everything in that first list with:

$$123, 124, 125, 134, 135, 145, 234, 235, 245, 345$$

simply by adding or removing the $6$ that is required to be there (not chosen).

Answer 3

Before I posted this question, I wrote to the author of the text, and to my great surprise, he wrote back! Though RobPratt's answer was enough to get me there, I thought I should share the author's answer here.

Text Author's Response

Perhaps a concrete numerical example will help. Take n=6 and k=3. We want to explain why

$\binom{3}{3} + \binom{4}{3} + \binom{5}{3} + \binom{6}{3} = \binom{7}{3}$

The right-hand side, $\binom{7}{4}$, counts all of the 4-element subsets of the 7-element set [7] = {1,...,7}.

So does the left-hand side, in four disjoint, exhaustive categories (in fancier language, this is called a partition of the set of all 4-element subsets of [7] into four blocks), namely:

(1) the category of all 4-element subsets of [7] with largest element equal to 4. Since it has already been determined that 4 will be an element of any such subset, we need to choose 3 more elements, different from, and smaller than 4, to create a 4-element subset of [7] with largest element equal to 4. So we need to choose 3 elements from the set [3], which can be done in $\binom{3}{3} = 1$ way. And, indeed, there is just one 4-element subset of [7] with largest element equal to 4, namely, {1,2,3,4}

(2) the category of all 4-element subsets of [7] with largest element equal to 5. Since it has already been determined that 5 will be an element of any such subset, we need to choose 3 more elements, different from and smaller than 5, to create a 4-element subset of [7] with largest element equal to 5. So we need to choose 3 elements from the set [4], which can be done in $\binom{4}{3} = 4$ ways. And, indeed, there are four 4-element subsets of [7] with largest element equal to 5, namely, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, and [2,3,4,5}.

If you'd like, carry this out for the remaining categories

(3) the category of all 4-element subsets of [7] with largest element equal to 6.

(4) the category of all 4-element subsets of [7] with largest element equal to 7

and email me the results. And include an explanation of why, among all (k+1)-element subsets of [n+1], if j is an integer in the set {k+1, k+2, ..., n+1}, there are (j-1)C(k) subsets with largest element equal to j.

My Response to the proposed exercise

(3) the category of all 4-element subsets of [7] with largest element equal to 6.

This, as predicted, had $\binom{5}{3}$ subsets: {1, 2, 3, 6}, {1, 2, 4, 6} , {1, 2, 5, 6} , {1, 3, 4, 6}, {1, 3, 5, 6}, {1, 4, 5, 6}, {2, 3, 4, 6}, {2, 3, 5, 6}, {2, 4, 5, 6}, {3, 4, 5, 6},

(4) the category of all 4-element subsets of [7] with largest element equal to 7

Likewise, $\binom{6}{3}$ = 20 subsets. {1, 2, 3, 7}, {1, 2, 4, 7} , {1, 2, 5, 7} , {1, 2, 6, 7} , {1, 3, 4, 7}, {1, 3, 5, 7}, {1, 3, 6, 7}, {1, 4, 5, 7}, {1, 4, 6, 7}, {1, 5, 6, 7}, {2, 3, 4, 7}, {2, 3, 5, 7}, {2, 3, 6, 7}, {2, 4, 5, 7}, {2, 4, 6, 7}, {2, 5, 6, 7}, {3, 4, 5, 7}, {3, 4, 6, 7}, {3, 5, 6, 7}, {4, 5, 6, 7}

And include an explanation of why, among all (k+1)-element subsets of [n+1], if j is an integer in the set {k+1, k+2, ..., n+1}, there are $\binom{j-1}{k}$ subsets with largest element equal to j.

The reason that the number of elements chosen from (let's call them "the candidates") is j-1 is because setting the largest element equal to j effectively removes a choice to be made. It's a forgone conclusion that j will be in the set, and that any elements larger than j will be excluded from candidacy. That naturally leaves only j-1 candidates remaining. The reason that the number of "open seats" is equal to k, even though the set size is k+1, is that we have already decided how one of the k+1 seats will be filled, leaving only k open seats remaining.