When choosing $k$ elements from $n$, how to count number of subsets of size $m$

Question

Consider a set of $n$ elements. If I choose $k$ elements, where $0\le k\le n$, this will be $\binom{n}{k}$. After making this choice, from the amount $\binom{n}{k}$ I want the number of possible subsets of size $m$, where $0\le m\le\binom{n}{k}$.

Answer 1

Hints: See if the following can be of any help in answering your question.

As an example if we view the $6$ letters $$A\,B\,C\,D\,E\,F$$ as a list that we wish to subdivide into three sets, then there are $6-1=5$ gaps for us to place our dividing line, say as in $$A\,|B\,C\,|D\,E\,F$$ so by dividing into three sets we have had to use $3-1=2$ lines. Hence we can do this in $\tbinom {6-1}{3-1}=\tbinom {5}{2}=10$ ways in total.

In general if we view the $n$ elements as a list, such as for $A\,B\,C\,D\,E\,F$ having $n - 1$ gaps, one between each pair of consecutive letters, then we may, or may not, place a line there such as in $A\,|B$. One has to choose $k - 1$ of them to actually contain a line; therefore there are $\tbinom {n-1}{k-1}$ possible ways of placing these lines.

---

Consider now our $n$ elements. Let us subdivide them into $j$ subsets, $k_i$, where $1\le i\le j$, and $k_1+k_2+\dotsb+k_j=n$. We can choose $k_1$ elements from them in $\binom{n}{k_1}$ ways. From the remaining $n - k_1$ elements we can choose $k_2$ elements in $\binom{n-k_1}{k_2}$, and so on until we reach $k_j$. In total we have \begin{align*} \binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\dots&=\frac{n!}{(n-k_1)!k_1!}\frac{(n-k_1)!}{(n-k_1-k_2)!k_2!}\frac{(n-k_1-k_2)!}{(n-k_1-k_2-k_3)!k_3!}\dots\\ &=\frac{n!}{k_1!\,k_2!\dotsm\,k_j!}\\ &=\binom{n!}{k_1!,\,k_2!,\dotsc,\,k_j!} \end{align*} whereby cancellation gives the last term, called a multinomial coefficient.